设G=＜ V,E＞为连通图,且e∈E.证明当且仅当e是G的割边时,e才在G的每棵生成树中。

A.G中至少有一条通路

B.G中至少有一条回路

C.G中有通过每个结点至少二次的通路

D.G中有通过每个结点至少一次的回路

A.E＞为有向图,#图片0$#是().

B.强连通图

C.单向连通图

D.弱连通图

E.不连通图

A.v+e-r=2

B. r+v-e=2

C. v+e-r=4

D. v+e-r=-4

设G=＜V,E＞为无环的无向图则G是().

A.完全图

B.零图

C.简单图

D.重图

设图G连通，并设S是N的非空真子集，证明边割是G的割集当且仅当点导出子图G[S]和都连通。

证明定理15.8.

定理15.8：设u,v为n阶无向图简单图G中两个不相邻的顶点,且d(u)+d(v)≥n,则G为哈密顿图GU(u,v)为哈密顿图((u,v)是加的新边.