V1→1、V2→2、V3→4、V4→3、V5→2
2．图G=
（1）画出G的图形； （2）写出G的邻接矩阵； （3）求出G权最小的生成树及其权值．
解：(1) (2)
G?(gij)5?5?0?1???1??0??11101?0011??0011??
1101?1110??(3)
四、问答题
G图最小生成树的权值为2+1+1+3=8。
1、设无向图G=
的度数均小于3。问G中至少有多少个顶点？ 解：∵有6个3度顶点
∴它们的度数之和为6×3=18.
又∵所有点的度数之和为?d(v)?2E?24，
v?V∴度数均小于3的其余顶点的度数之和为24-18=6. ∴其余顶点的度数均为2时，G的顶点最少 ∴其余顶点有6/2=3个
∴G中至少有6+3=9个顶点
2、判断下列图是否为欧拉图？说明理由，存在是否哈密尔顿回路。
? ? ?
? ?
解：
（1）、是欧拉图。
理由：欧拉图判断条件：图中所有节度点均为偶数 （2）、不存在哈密尔顿回路。
理由：哈密顿图是基本回路（点不能重复）。哈密顿图遍历顶点。
3、下列各组数中，哪些能构成无向图①的度数列？哪些能构成无向 简单图②的度数列？
（1）1，1，1，2，3 ①√②√ （2）2，2，2，2，2 ①√②√ （3）3，3，3，3 ①√②√ （4）1，2，3，4，5 ①
②
（5）1，3，3，3 ①√②
解：1、构成图的度数列的条件： 度数（次）之和
?d(v)?2E为偶数，并且奇点有偶数个。
v?V∵(1)、(2)、(3)、(4)、(5)的度数（次）之和分别为8、10、12、15、10
又∵奇点的个数分别为4、0、4、3、4
∴(4)不符合。也不满足无向简单图。
∴(1)，(2)，(3)，(5)都能构成无向图的度数列
2、(5)虽然能构成无向图的度数列，但不能构成无向简单图的度数列。 若G是无向简单图，设G中顶点为a、b、c、d且d(a)=1、d(b)=d(c)=d(d)=3显然，a只能与b、c、d其中一个顶点相邻，若设a与b相邻，则除b可以是3度顶点，c、d都不能是3度顶点，这是矛盾的。所以(5)中的度数列不能构成不是无向简单图。
4、[1] 哥尼斯堡的居民能否通过建一座新桥来找一条可接受的路线？如果可以，该怎么作？
[2] 哥尼斯堡的居民能否通过建两座新桥来找一条可接受的路线？如果可以，该怎么作？
[3] 哥尼斯堡的居民能否通过拆一座桥来找一条可接受的路线？如果可以，该怎么作？
[4] 哥尼斯堡的居民能否通过拆两座桥来找一条可接受的路线？ 如果可以，该怎么作？
解：∵七桥示意图的每个节点度为奇数 ∴它不是欧拉图，不能遍历边
∵连通无向图G有n个奇点成为欧拉图的充要条件：
在G中至少要添加或删掉n/2条边
假设桥为图中的边，解答如下： （1）、（2）
∵图中有4个奇点
∴要使其变为欧拉回路，即可以在G中添加4/2=2条边 ∴（1）不满足条件，路线不被接受，（2）的建议则被接受 （3）、（4）
∵图中有4个奇点
∴要使其变为欧拉回路，即可以在G中删掉4/2=2条边 ∴（3）不满足条件，路线不被接受，（4）的建议则被接受
五．画图
? 画出一个无向欧拉图，使它具有： （1）偶数个顶点，偶数条边； （2）奇数个顶点，奇数条边； （3）偶数个顶点，奇数条边； （4）奇数个顶点，偶数条边
? 画出一个有向欧拉图，要求：
按数字顺序走遍所有的边，点可以重复。 蓝点是起点。
（1）偶数个顶点，偶数条边； （2）奇数个顶点，奇数条边； （3）偶数个顶点，奇数条边； （4）奇数个顶点，偶数条边。
3. 根据如下的相邻矩阵，画出它所对应的图G。
? 0
? ? 1 ? 0
A ( G ) ? ?
? 1 ? 1 ? ?? 1
1 0 1 1 1 1
0 1 0 1 1 1
1 1 1 0 1 0
1 1 1 1 0 1
1 ?
? 1 ? 1 ? ? 0 ? 1 ? ? 0 ??
4、已知无向图G有12条边，6个3度顶点，其余顶点的 度数均小于3，问图G至少有几个顶点？并画出符合
条件的图形？
解：∵无向图G的|E|=12
∴图G的度数之和为?d(v)?2E?24
v?V又∵6个3度顶点
∴这6个3度顶点的度数之和为6×3=18 ∴度数均小于3的其余顶点的度数之和为24-18=6
当其余顶点的度数均为2时，图G的顶点最少 ∴其余顶点数为6/2=3 ∴图G至少有6+3=9个顶点。
5、在有7个结点的无向图G中，2度、3度、4度、5度 顶点的个数分别是1、3、2、1，求G的边数，试画 出满足条件的图形？ 解：由题可知，
7个顶点的度数之和为1×2+3×3+2×4+1×5=24 ∵所有次之和为边数的两倍 ∴G图的边数为24/2=12
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库图论复习题(2)在线全文阅读。
相关推荐：