文档介绍：离散数学图论部分期末复习辅导
一、单项选择题
设图G=<V,E>, vgV,则下列结论成立的是().
deg(v)=2 | E \ B. deg(v)= | E |
C. £deg(v) = 2IEI D. ^deg(v) =\E\面，则r=（ ）.
A. e —v + 2 B. v+e —2
C. e — v — 2 D. e + v+2
答A （：欧拉公式v-e+r = 2 ）
问：如果连通平面图G有4个结点，7条边，那么图G有几个面？
无向树T有8个结点，则T的边数为（）.
A. 6 B. 7 C. 8 D. 9 答 B
无向简单图G是棵树，当且仅当（）.
G连通且边数比结点数少1
G连通且结点数比边数少1
G的边数比结点数少1
G中没有回路.
答A （ （树的等价定义））
已知一棵无向树T中有8个顶点，4度、
为（）•
3度、2度的分支点各一个，T的树叶数
A. 8
B. 5
C. 4
D. 3
解 这棵无向树T有7条边，所有结点的度数之和为14,而4度、3度、2度的分支点 各一个共3个结点占用了 9度，所以剩下的5个结点占用5度，即这5个结点每个都 是1度结点，故有5片树叶.
答B
设G是有〃个结点，m条边的连通图，必须删去。的（ ）条边，才能确定G的
一棵生成树.
A. m-n + 1 B. m-n
C. m + n + l D. n-m + 1
答A （〃个结点的连通图的生成树有"-1条边，必须删去m - （« -1）条边）
设无向图G的邻接矩阵为
0 1111
10 0 11
1 0 0 0 0
110 0 1
110 10
则G的边数为（）.
A. 1 B. 6 C. 7
D. 14
如图二（下图）所示,
以下说法正确的是（）.
A. e是割点
C. {b,e}是点割集
{a,e}是点割集
{d}是点割集
图二
设有向图（a）、（。）、（c）与（d）如图六（下图）所示，则下列结论成立的是（）.
A. （a）只是弱连通的
（c）只是弱连通的
图六
（。）只是弱连通的
D. （d）只是弱连通的
无向完全图曲是（ ）.
以下结论正确的是（）.
无向完全图都是欧拉图
有〃个结点n — 1条边的无向图都是树
无向完全图都是平面图
树的每条边都是割边 答D 二、填空题
已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G
的边数是.
解 设G有x条边，则由握手定理，
Ixl + 2x2 + 3x3 + 4x4 = 2i, x = 15
答15
设给定图G（如右由图所示），则图G的点割集 叭 Ab
是 \z_l（
解从图G中删除结点/■，得到的子图是不连通图，
即结点集撬是点割集;从图G中删除结点c和e, '一 得到的子图是不连通图，而只删除c或e,得到的子图仍然是连通的，所以结点集｛c, e｝，所以应该填写：｛/｝、｛c, e]
答｛f｝、｛c,e｝
提示：若/•是图G的割点，则｛/｝是图G的点割集，删除/•点后图G是连通吗？
设G是一个图，结点集合为V,边集合为E,则G的结点 等于边
数的两倍.
答的度数之和
无向图G存在欧拉回路，当且仅当G连通且.
答G的结点度数都是偶数（定理4. 1. 1的推论）
设G=<V, E>是具有n个结点的简单图，若在G中每一对结点度数之和大于等 于,则在G中存在一条汉密尔顿路.
答 n-1 （定理 ）
若图G=<V, E>中具有一条汉密尔顿回路，则对于结点集V的每个非空子集S,在 G中删除S中的所有结点得到的连通分支数为W,则S中结点数ISI与W满足的关系 W< ISI （. 1）
设完全图K”有〃个结点（〃22）, m条边,当 时，K “中存在欧拉回路.
答n为奇数（同一、8题）
结点数v与边数e满足 关系的无向连通图就是树.
答e=v-l （ （树的等价定义））
设图G是有6个结点的连通图，结点的总度数为18,则可从G中删去 条边
后使之变成树.
解 由握手定理（）知道图G有18+2=9条边，又由定理5. 为树的等价定义之一是“图T连通且e=vT”，可以知道图G的生成树有5条边，从 而要删去4条边.
答4
,（： （m-l）i=t-l）
三、判断说明题（判断下列各题，并说明理由.）
如