2015电子科技大学 图论考试复习题关于图论中的图，以下叙述不正确的是A ．图中点表示研究对象，边或有向边表示研究对象之间的特定关系。

B ．图论中的图，画边时长短曲直无所谓。

C ．图中的边表示研究对象，点表示研究对象之间的特定关系。

D ．图论中的图，可以改变点与点的相互位置，只要不改变点与点的连接关系。

一个图中最长的边一定不包含在最优生成树内。

下面哪个图形不与完全二分图K 3,3同构？ A ． B ． C ． D ．有10条边的5顶单图必与K 5同构。

完全二分图K m ,n 的边数是 A ．m B ．n C ．m +n D ．mn无向完全图K n 的边数为 A ．n B ．n 2 C ．n (n -1) D ．n (n -1)/2若一个无向图有5个顶点，如果它的补图是连通图，那么这个无向图最多有 条边。

对于两个图，如果顶点数目相等，边数相等，次数相等的顶点数目也相等，则这两个图同构。

有15个顶的单图的边数最多是 A ．105 B ．210 C ．21 D ．45图G 如右，则dacbeb A ．是G 中的一条道路 B ．是G 中的一条道路但不是行迹C ．是G 中的一条行迹但不是轨道D ．不是G 的一条道路图G 如右，则befcdef A ．是G 的一个圈 B ．是G 的一条道路但不是行迹C ．是G 的一条行迹但不是轨道D ．是G 的一条轨道但不是圈71464518736432232v 1v 2u 0v 3v 4v 5v 6v 7图G 如右图所示，则ω (G)= A ．1 B ．2 C ．7 D ．8下列图形中与其补图同构的是 A ． B ． C ． D ．求下图中顶u 0到其余各顶点的最短轨长度。

u 0v 1=8，u 0v 2=1，u 0v 3=4，u 0v 4=2，u 0v 5=7，v 1v 2=7，v 1v 3=2，v 1v 6=4，v 2v 4=2，v 2v 7=3，v 3v 5=3，v 3v 6=6，v 4v 5=5，v 4v 7=1，v 5v 6=4，v 5v 7=3，v 6v 7=6，请画出6阶3正则图。

请画出4个顶，3条边的所有非同构的无向简单图。

设图G ={V (G )，E (G )}其中V ={a 1, a 2, a 3, a 4, a 5}，E (G )={(a 1, a 2)，(a 2, a 4)，(a 3, a 1)，(a 4, a 5)，(a 5, a 2)}，试给出G 的图形表示并画出其补图的图形。

一个图的生成子图必是唯一的。

不同构的有2条边，4个顶的无向简单图的个数为 A ．1 B ．2 C ．3 D ．4画出5个具有5个结点5条边的非同构的无向连通简单图。

u 0到v 1的最短轨长度为6，u 0到v 2的最短轨长度为1，u 0到v 3的最短轨长度为4，u 0到v 4的最短轨长度为2，u 0到v 5的最短轨长度为6，u 0到v 6的最短轨长度为9，u 0到v 7的最短轨长度为3。

v 111074用Dijkstra 算法求下图中从v 1点到其他任意一点的最短路。

v 1v 3v 1v 2v 1v 2v 5 v 1v 3v 4 v 1v 2v 5v 6 v 1v 2v 5v 6v 7设有城市v 1，v 2，v 3，v 4，v 5，v 6，各城市之间的距离如下表。

使用Dijkstra 算法求城市v 1到其他各城市的最短路径以及最短距离。

要求说明求解过程（提示：应将城市之间的道路图解：下面的表格给出了求解v最后得到v 1到其他各城市的最短路径及最短距离为：v 1到v 2的最短路径是：v 1v 2 长度为1 v 1到v 3的最短路径是：v 1v 2v 3 长度为3 v 1到v 4的最短路径是：v 1v 2v 3v 5v 4 长度为7 v 1到v 5的最短路径是：v 1v 2v 3v 5 长度为4 v 1到v 6的最短路径是：v 1v 2v 3v 5v 4v 6 长度为9求下图中顶v 1到v 11的最短轨及最短距离。

L100个顶点的星的最大顶点次数是 。

做一个图G ，使其顶的次序列为(5,5,4,4,3,3,2,2,2)。

v 67下列哪个序列不可能构成一个图的顶点次数序列？A．(2,2,2,2,2) B．(3,3,3,3) C．(1,2,3,4,5) D．(2,2,3,4,5)已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G的边数是．任取n个人组成的人群，n≥2，证明至少有两位，他们在人群中的朋友一样多。

证明：把n个人看做n个点，如果两个人是朋友，则在这两个点之间连一条边，这样可以得到一个含n个顶的单图。

显然顶的最大次数为n-1，如果这n个顶的次数不一样，则它们必为0,1,2,…,n-1，而次为0的顶与各顶都不相邻，因此不可能有顶的次为n-1，出现矛盾。

因此n个顶的次数必至少有两个是相等的。

所以至少有两位，他们在人群中的朋友一样多。

设G是一个含n个顶点的无向简单图，n是大于等于2的奇数．证明图G与它的补图G C中的奇数次顶点个数相等。

E(G C)是由完全图K n的边删去E(G)所得到的．所以对于任意结点u∈V(G)，u在G和G C中的次数之和等于u在K n中的次数．由于n是大于等于2的奇数，从而K n的每个顶点都是偶数度的（n−1≥(2)度），于是若u∈V(G)在G中是奇数次顶点，则它在G C中也是奇数次顶点．故图G与它的补图G C的奇数次顶点个数相等。

具有m条边的树有几个顶点？A ．mB ．1mC ．m 1D ．2m 完全二分图K m,n 的边数是： A ．m B ．n C ．m+n D ．mn有n 个顶的图中，圈的长度最大值为 A ．2n B ．n C ．n+1 D ．n −1含5个顶、3条边的不同构的无向图有 A ．2个 B ．3个 C ．4个 D ．5个图G 如右所示，与G 同构的图是 A ． B ．C ．D ．v 1，v 2，v 3，v 4，v 5，v 6是6个城市，下面矩阵的（i ，j ）号元素是v i 到v j 的机票票价，试为一个旅行者制作一张由v 1到各城去旅游的最便宜的航行路线图。

050402510500152025150102040201001025252010055102525550完全图K 4的生成树的数目为 。

一棵树有2个2度顶点，1 个3度顶点，3个4度顶点，则其1度顶点的个数是 A ．5 B ．7 C ．8 D ．9有6个顶的不同构的树共有 棵。

设图G 是有6个顶点的连通图，顶点的总度数为18，则可从G 中删去 条边后使之变成树。

4已知一棵无向树T 中有8个顶点，4度、3度、2度的顶点各一个，T 的树叶数为 。

有n（n>1）个顶的树T，下面说法不正确的是A．T是二分图B．T是可平面图C．T中存在完美匹配D．T中任意两点间有唯一轨道相连接设G是有n个结点，m条边的连通图，为了得到G的一棵生成树，必须从G中删去的边数是A．m−n+1 B．m−n C．m+n+1 D．n−m+1无向简单图G是棵树，当且仅当A．G连通且边数比顶点数少1 B．G连通且顶点数比边数少1C．G的边数比顶点数少1 D．G中没有圈下面给出的集合中，哪一个是前缀码A．{0，10，110，101111} B．{01，001，000，1}C．{b，c，aa，ab，aba} D．{1，11，101，001，0011}给定一个序列集合{1，01，10，11，001，000}，若去掉其中的元素，则该序列集合构成前缀码。

若一棵典型有序二元树有2n-1个顶点，则它的树叶数是A．n B．2n C．n-1 D．2下面那种描述的单图不一定是树。

A．无回路的连通图B．有n个顶点，n-1条边的图C．每对顶点都有通路的图D．连通但删去一条边则不连通的图下列无向图一定是树的是A．连通图B．无圈但添加一条边后有圈的图C．每对顶点间都有路的图D．连通且E(G)=V(G)-1求生成树个数时，将一个树对应一个Prufer序列，如果树T的对应Prufer序列为(2,3,2,3)，则标号为2的顶点的次数是A．1 B．2 C．3 D．4右图是二分图。

一个有13个顶的简单图G中有3个顶的次数是4，4个顶的次数是3，6个顶的次数是1，则图G一定是树。

设树T中有2个3度顶点和3个4度顶点，其余的顶点都是树叶，则T中有片树叶。

10若T 是图G 的生成树，则 A ．T 必唯一 B ．G 不一定是连通图 C ．T 中必不含圈 D ．G 中不含圈若G 是一个含p 个顶点，q 条边的图，若q ≥p ，则G 中必有圈。

有4个连通片组成的17个顶的森林的边数为 A ．16 B ．15 C ．14 D ．13设G 是一个满足|E (G )|≥|V (G )|的图，则G 中必有圈。

在下图中，用Kruskal 算法构造最小生成树，写出边添加到生成树的边序列，并画出生成树。

答：求下图的最优树T （不要求中间过程，只要求画出最小生成树, 并给出T 的权和）。

答：权和为17。

求下图的最小生成树，并给出权值(只给结果，不要过程)a答：权和为28。

求下图的最小生成树，并给出权值。

权和为16。

假设用于通信的电文仅由8个字母 {a , b , c , d , e , f , g , h } 构成，它们在电文中出现的概率分别为{ 0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10}，试为这8个字母设计哈夫曼编码。

解：a , 1100；b , 00；c , 11110；d , 1110；e ,10；f , 11111；g , 01；h ,1101画出带权0,2，0.17，0.13，0.1，0.1，0.08，0.06，0.06，0.07，0.03的Huffman 树。

画出带权0.1，0.1，0.1，0.1，0.15，0.2，0.25的Huffman 树。

0.020.030.060.050.070.100.40.60.170.280.190.320.110.211.001.000.100.100.130.130.200.200.340.260.600.400.170.080.170.090.060.070.030.06v 365v 365假定通信中出现的字母为a , b , c , d , e , f , g , h ，其出现的频率如下表。

试画出这组字母（权）的设T 是树叶权为1，2，3，4，5的Huffman 树，那么树T 的带权路径长为 。

33有99个顶点的典型有序二元树的叶子数是 。

一个出城汽车队行驶时不得超车，但每车都可以进入路过的一个胡同里去加油，再在某时刻退出胡同插队继续开行，共有5辆不同的汽车。

则开出城的不同车队种数是 。

行餐后姊妹去洗碗，洗前已把5个不同花色的碗摞成一摞。