文档介绍：离散数学图论部分期末复习辅导
一、单项选择题
=<V, E>,vÎV,则下列结论成立的是( ) .
(v)=2½E½ (v)=½E½
C. D.
解根据握手定理(图中所有结点的度数之和等于边数的两倍)知,答案C成立。
答 C
,
则G的边数为( ).
解由邻接矩阵的定义知,,结点vj与vi也相邻,所以连接结点vi与vj的一条边在邻接矩阵的第i行第j列处和第j行第i列处各有一个1,题中给出的邻接矩阵中共有10个1,故有10¸2=5条边。
答 B
,
则G有( ).
,8边 ,7边
,8边 ,7边
解由邻接矩阵的定义知,矩阵是5阶方阵,所以图G有5个结点,矩阵元素有14个1,14÷2=7,图G有7条边。
答 D
o
o
o
o
a
b
c
d
图一
o
e
,以下说法正确的是( ) .
A.{(a, e)}是割边
B.{(a, e)}是边割集
C.{(a, e) ,(b, c)}是边割集
D.{(d, e)}是边割集
设无向图G=<V,E>为连通图,若有边集E1ÌE,使图G删除了E1的所有边后,所得的子图是不连通图,而删除了E1的任何真子集后,所得的子图仍是连通图,{e},则称边e为割边(或桥).
解割边首先是一条边,因为答案A中的是边集,不可能是割边,,得到的图是还是连通图,因此答案B、,删去(d, e)边,图就不连通了,所以答案D正确.
答 D
注:如果该题只给出图的结点和边,没有图示,:
若图G=<V, E>,其中V={ a, b, c, d, e },E={ (a, b), (a, c) , (a, e) , (b, c) , (b, e) , (c, e) , (e, d)},则该图中的割边是什么?
,以下说法正确的是( ).
o
o
o
a
b
c
d
图二
o
B.{b, c}是点割集
C.{b, d}是点割集
D.{c}是点割集
设无向图G=<V,E>为连通图,若有点集V1ÌV,使图G删除了V1的所有结点后,所得的子图是不连通图,而删除了V1的任何真子集后,所得的子图仍是连通图,{v},则称结点v为割点.
解在图二中,删去结点a或删去结点c或删去结点b和d图还是连通的,所以答案A、C、,得到的子图是不连通图,而只删除结点
b或结点c,得到的子图仍然是连通的,由定义可以知道,{b, c}.
答 B
o
o
o
a
b
c
d
图三
o
,以下说法正确的是( ) .
A.{(a, d)}是割边
B.{(a, d)}是边割集
C.{(a, d) ,(b, d)}是边割集
D.{(b, d)}是边割集
解割边首先是一条边,{(a, d)}是边集,,删除答案B或D中的边后,、B、,删去(a, d)边和(b, d)边,图就不连通了,而只是删除(a, d)边或(b, d)边,图还是连通的,所以答案C正确.
(a)、(b)、(c)与(d)如图四所示,则下列结论成立的是( ).
图四
A.(a)是强连通的 B.(b)是强连通的
C.(c)是强连通的 D.(d)是强连通的
复习: 在简单有向图中,若在任何结点偶对中,至少从一个结点到另一个结点可达的,则称图G是单向(侧)连通的;
若在任何结点偶对中,两结点对互相可达,则称图G是强连通的;
若图G的底图,即在图G中略去边的方向,得到的无向图是连通的,则称图G是弱连通的.
显然,强连通的一定是单向连通和弱连通的,单向连通的一定是弱连通,但其逆均不真.
一个有向图是强连通的,当且仅当G中有一个回路,其至少包含每个结点一次.
单侧连通图判别法:若有向图G中存在一条经过每个结点至少一次的路,则G是单侧连通的。
答 A(有一条经过每个结点的回路)
问:上面的图中,哪个仅为弱连通的?
答:图(d)是仅为弱连通的
请大家要复习“弱连通”的概念.
(n³2),m条边,当( )时