解得x ≥3。G至少有2 + 2 + 3 = 7个顶点，这时度数列为 2、 2、 2、 3、 3、 4 4），而??(G) = 4，??(G) = 2。
5、设无向图G有10条边，3度与4度顶点各2个，其余顶点的度数均小于3，问G至少有
?(G)。 多少个顶点？在最少顶点的情况下，写出度数列、?(G)、 解：由握手定理图G的度数之和为：2?10?20
3度与4度顶点各2个，这4个顶点的度数之和为14度。 其余顶点的度数共有6度。
其余顶点的度数均小于3，欲使G的顶点最少，其余顶点的度数应都取2,
所以，G至少有7个顶点, 出度数列为3,3,4,4,2,2,2,?(G)?4,?(G)?2. 6(1)设n阶图G中有m条边、 证明： ?(G) ≤2m/n ≤?(G)。(2) n 阶非连通
的简单图的边数最多可为多少?最少呢吗？(1)设V(G) = {v1、 v2、......，v n}，由握手定理得 n ↖d (v) ? (1) i 我 ?1 ??又 n ↖d （v)≤得 ?????(G) ≤n?(G) ? (2) i 我 (2)
2m/n (2) ≤?(G) 设G ?1 ??由(1) = 〈V，E〉是n阶
1) V2 = V
不连通的 (无向) 简单图。令V1是G的一个连通分支的顶点集，k = |V1 |(≥? V1。注意V2 ≠?(?) |V2 |= |V|?|V1 |= n ?k ≥1。V1的顶点与V2的顶点
之间没有G的边(?)、 而G的边关联的顶点都是V1的顶点或者都是V2的顶点，即 E = E (G [V1]) ∪ E (G [V1])。要使G的边数最大，G [V1] 和G [V2] 都要含尽可能多的边、 这时它们都是完全图，分别有k(k ?G有|E|= k(k ?1)/2 + (n ?1)/2条边和(n ?k ?k) (n ?k ?1) / 2条边，而
k)(n ?1)/2条边。下面证明当k = 1 (或n ?1) 布置 |E|最大。2 2 n ?n ? 2 n ?尽可能远。当k = 1或n ?阶不连通的简单图由K n ? ? 2? 4 要使?E?最大、 k要离n/2
1)(n ?2)/2。边数最多的n
1)(n ?2)/2
1时 |E|取得最大值 (n ?1和K1 (平凡图) 两个连通分支组成，有 (n ?条边。边数最少的n阶不连通的简单图显然是n阶零图N n = ?K n，边数为0。QEI 另解: n阶连通的简单图中，K n的边数最多、 有n(n ?少(?)要删除关联某个顶点的 (n ?得，它的边数 = K n ?1)/2条边、 要破坏K n的连通性、 至
1和一个孤立点 (K1) 获
1) 条边，所得图由K n ?1)(n ?1的边数 = (n ?2)/2条边。这是 n阶非连通的简单
图的边数最多的情况。
7、设有向图D的度数列为2，3，2，3，出度列为1，2，1，1，求D的入度列，并求?(D),?(D)，
??(D),??(D),??(D),??(D).
解：D的度数列为2，3，2，3，出度列为1，2，1，1，D的入度列为1,1,1,2.
?(D)?3,?(D)?2,??(D)?2,??(D)?1,??(D)?2,??(D)?1
8、设无向图中有6条边，3度与5度顶点各1个，其余顶点都是2度点，问该图有多少个顶点？
解：由握手定理图G的度数之和为：2?6?12
设2度点x个，则3?1?5?1?2x?12，x?2，该图有4个顶点.
14、下面给出的两个正整数数列中哪个是可图化的？对可图化的数列，试给出3种非同构的无向图，其中至少有两个时简单图。
(1) 2,2,3,3,4,4,5 (2) 2,2,2,2,3,3,4,4 解：(1) 2+2+3+3+4+4+5=23 是奇数，不可图化； (2) 2＋2+2+2+3+3+4+4=16, 是偶数，可图化；
18、设有3个4阶4条边的无向简单图G1、G2、G3，证明它们至少有两个是同构的。
证明：4阶4条边的无向简单图的顶点的最大度数为3，度数之和为8，因而度数列为2，2，2，2；3，2，2，1；3，3，1，1。但3，3，1，1对应的图不是简单图。所以从同构的观点看，4阶4条边的无向简单图只有两个：
所以，G1、G2、G3至少有两个是同构的。
20、已知n阶无向简单图G有m条边，试求G的补图G的边数m?。
解：m??n(n?1)?m 221、无向图G如下图
(1)求G的全部点割集与边割集，指出其中的割点和桥； (2) 求G的点连通度k(G)与边连通度?(G)。
ae2be3解：点割集: {a,b},(d)
e1de5ee4c
边割集{e2,e3},{e3,e4},{e1,e2},{e1,e4}{e1,e3},{e2,e4},{e5}
k(G)=?(G)=1
23、求G的点连通度k(G)、边连通度?(G)与最小度数?(G)。
解：k(G)?2、?(G)?3 、?(G)?4
28、设n阶无向简单图为3-正则图，且边数m与n满足2n-3=m问这样的无向图有几种非同构的情况？
解：??3n?2m 得n=6,m=9.
2n?3?m? 31、设图G和它的部图G的边数分别为m和m，试确定G的阶数。
解：m?m??1?1?8(m?m)n(n?1) 得n? 2245、有向图D如图
(1)求v2到v5长度为1，2，3，4的通路数；
(2)求v5到v5长度为1，2，3，4的回路数； (3)求D中长度为4的通路数； (4)求D中长度小于或等于4的回路数； (5)写出D的可达矩阵。
v1v4v5v2v3
解：有向图D的邻接矩阵为：
??00001??010??2?10100???01?00002???A???00001?，A2????0010A3????10100???01?0002???2??01010???0?20200???0?0??00004??012?40400???5A4???0??520004 A?A2?A3?A4??2??40400???21?45?04040???2?252(1)v2到v5长度为1，2，3，4的通路数为0,2,0,0； (2)v5到v5长度为1，2，3，4的回路数为0,0,4,0； (3)D中长度为4的通路数为32； (4)D中长度小于或等于4的回路数10；
??11111??11111??(4)出D的可达矩阵P???11111?
??11111???11111??第十六章部分课后习题参考答案
02020202020200015?22??15?22?
?54??0?0??0?0??4??
1、画出所有5阶和7阶非同构的无向树.
2、一棵无向树T有5片树叶，3个2度分支点，其余的分支点都是3度顶点，问T有几个顶点?
解：设3度分支点x个，则
5?1?3?2?3x?2?(5?3?x?1)，解得x?3
T有11个顶点
3、无向树T有8个树叶，2个3度分支点，其余的分支点都是4度顶点，问T有几个4度分支点？根据T的度数列，请至少画出4棵非同构的无向树。
解：设4度分支点x个，则
8?1?2?3?4x?2?(8?2?x?1)，解得x?2
度数列111111113344
4、棵无向树T有ni (i=2，3，?，k)个i度分支点，其余顶点都是树叶，问T应该有几片树叶?
解：设树叶x片，则
ni?i?x?1?2?(ni?x?1)，解得x?(i?2)ni?2