2013四川师范大学 图论考试复习题
关于图论中的图，以下叙述不正确的是
A．图中点表示研究对象，边或有向边表示研究对象之间的特定关系。 B．图论中的图，画边时长短曲直无所谓。
C．图中的边表示研究对象，点表示研究对象之间的特定关系。
D．图论中的图，可以改变点与点的相互位置，只要不改变点与点的连接关系。
一个图中最长的边一定不包含在最优生成树内。
下面哪个图形不与完全二分图K3,3同构？ A． B． C． D．
有10条边的5顶单图必与K5同构。
完全二分图Km,n的边数是 A．m B．n C．m?n D．mn
无向完全图Kn的边数为 A．n B．n2 C．n(n?1) D．n(n?1)/2
若一个无向图有5个顶点，如果它的补图是连通图，那么这个无向图最多有 条边。
对于两个图，如果顶点数目相等，边数相等，次数相等的顶点数目也相等，则这两个图同构。
有15个顶的单图的边数最多是 A．105 B．210 C．21 D．45
图G如右，则dacbeb
A．是G中的一条道路 baB．是G中的一条道路但不是行迹
gef C．是G中的一条行迹但不是轨道
dcD．不是G的一条道路
图G如右，则befcdef A．是G的一个圈 baB．是G的一条道路但不是行迹
gefC．是G的一条行迹但不是轨道
dcD．是G的一条轨道但不是圈
图G如右图所示，则??(G)?
A．1 B．2
C．7 D．8
下列图形中与其补图同构的是 A． B． C． D．
求下图中顶u0到其余各顶点的最短轨长度。
u0v1=8，u0v2=1，u0v3=4，u0v4=2，u0v5=7，v1v2=7，v1v3=2，v1v6=4，v2v4=2，v2v7=3，v3v5=3，v3v6=6，v4v5=5，v4v7=1，v5v6=4，v5v7=3，v6v7=6，
v2v42
7121 3758v1v7 u0v533446请画出6阶3正则图。 24 v3v66
请画出4个顶，3条边的所有非同构的无向简单图。
设图G={V(G)，E(G)}其中V={a1, a2, a3, a4, a5}，E(G)={(a1, a2)，(a2, a4)，(a3, a1)，(a4, a5)，(a5, a2)}，试给出G的图形表示并画出其补图的图形。
一个图的生成子图必是唯一的。
不同构的有2条边，4个顶的无向简单图的个数为 A．1 B．2 C．3 D．4
画出5个具有5个结点5条边的非同构的无向连通简单图。
u0到v1的最短轨长度为6，u0到v2的最短轨长度为1，u0到v3的最短轨长度为4，u0到v4的最短轨长度为2，u0到v5的最短轨长度为6，u0到v6的最短轨长度为9，u0到v7的最短轨长度为3。
用Dijkstra算法求下图中从v1点到其他任意一点的最短路。
v21v5v1v3
209109v1v2
13v3v7v1v2v5 v14v1v3v4 15843v1v2v5v6 v37v6v1v2v5v6v7
设有城市v1，v2，v3，v4，v5，v6，各城市之间的距离如下表。使用Dijkstra算法求城市v1到其他各城市的最短路径以及最短距离。要求说明求解过程（提示：应将城市之间的道路图看作是无向图）。 道路 距离 步骤 v1v2 1 v1 0 v1v3 4 v2 1/(v1) ①/(v1) v2v3 2 v2v4 7 v3 4/(v1) 3/(v2) ③/(v2) v2v5 5 v4 ∞ 8/(v2) 8/(v2) 7/(v5) ⑦/(v5) v3v5 1 v4v5 3 v5 ∞ 6/(v2) 4/(v3) ④/(v3) v4v6 2 v6 ∞ ∞ ∞ 10/(v5) 9/(v4) ⑨/(v4) v5v6 6 解：下面的表格给出了求解v1到其他各顶点之间的最短距离的Dijkstra算法执行过程：
最后得到v1到其他各城市的最短路径及最短距离为：
v1到v2的最短路径是：v1v2 长度为1 v1到v3的最短路径是：v1v2v3 长度为3 v1到v4的最短路径是：v1v2v3v5v4 长度为7 v1到v5的最短路径是：v1v2v3v5 长度为4 v1到v6的最短路径是：v1v2v3v5v4v6 长度为9
求下图中顶v1到v11的最短轨及最短距离。 v52v2v81
265 3979v66v9281L v1v11v3 4321471
v49v71v10
100个顶点的星的最大顶点次数是 。
做一个图G，使其顶的次序列为(5,5,4,4,3,3,2,2,2)。
下列哪个序列不可能构成一个图的顶点次数序列？ 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与它的补图GC中的奇数次顶点个数相等。
E(GC)是由完全图Kn的边删去E(G)所得到的．所以对于任意结点u∈V(G)，u在G和GC中的次数之和等于u在Kn中的次数．由于n是大于等于2的奇数，从而Kn的每个顶点都是偶数度的（n?1≥(2)度），于是若u∈V(G)在G中是奇数次顶点，则它在GC中也是奇数次顶点．故图G与它的补图GC的奇数次顶点个数相等。
具有m条边的树有几个顶点？
A．m B．m-1 C．m?1 D．
m 2完全二分图Km,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．
v1，v2，v3，v4，v5，v6是6个城市，下面矩阵的（i，j）号元素是vi到vj的机票票价，试为一个旅行者制作一张由v1到各城去旅游的最便宜的航行路线图。 轾0犏犏50犏犏ゥ犏犏40犏犏25犏犏10犏臌5001520￥25￥1501020￥4020100102525￥2010055102525550
完全图K4的生成树的数目为 。
一棵树有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连通且顶点数比边数少1 C．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算法构造最小生成树，写出边添加到生成树的边序列，并画出生成树。
f2e 5867 1gad
6563
b4c
f2e答：
5
1ga d 53 b4c
求下图的最优树T（不要求中间过程，只要求画出最小生成树, 并给出T的权和）。
16 46234 7255 13
答： 14 242
13
权和为17。
求下图的最小生成树，并给出权值(只给结果，不要过程)
47 466139 512 1054125169 答：
权和为28。
求下图的最小生成树，并给出权值。
v2v42 1344 7535v1v6 v1v7683234
4v3v5 v2v42 143v1v6权和为16。 v81v7 32 v3v5
假设用于通信的电文仅由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
1.00 0.40.6
0.190.210.320.28
0.110.17
0.070.100.060.05
画出带权0,2，0.17，0.13，0.1，0.1，0.08，0.06，0.06，
0.020.030.07，0.03的Huffman树。
1.00
0.400.60 0.200.200.260.34 0.100.100.130.130.170.17画出带权0.1，0.1，0.1，0.1，0.15，0.2，0.25
0.060.070.080.09的Huffman树。
0.030.061.000.40.20.60.20.250.10.10.350.150.20.10.1
假定通信中出现的字母为a, b, c, d, e, f, g, h，其出现的频率如下表。试画出这组字母（权）的Huffman树，要求给出求解过程。 字母 频率 a 25% b 20% c 15% d 15% e 10% f 5% g 5% h 5%
1
0.550.45
ab0.25 0.3
c0.1d0.15
ghef
设T是树叶权为1，2，3，4，5的Huffman树，那么树T的带权路径长为 。33
有99个顶点的典型有序二元树的叶子数是 。
一个出城汽车队行驶时不得超车，但每车都可以进入路过的一个胡同里去加油，再在某时刻退出胡同插队继续开行，共有5辆不同的汽车。则开出城的不同车队种数是 。
行餐后姊妹去洗碗，洗前已把5个不同花色的碗摞成一摞。妹妹把姐姐洗过的碗每次拿一个放入消毒柜，也摞成一摞。由于小妹贪玩，碗被放入消毒柜可能不及时，姐姐则把洗过的碗摞在旁边，则小妹摞起的碗摞可能的种数是 。 答：42
对一个括号序列进行检测，从左向右数到第99个括号时，记录了右括号 个，因此得出结论为坏括号序列。 50
对一个好括号序列进行检测，从左向右至少数到第 个括号时，会记录下50个右括号。 100
画出所有不同构的5顶点树。
以下说法错误的是
A. 同构的图具有相同的顶点数和边数 B. 同胚的图边数相同，但顶点数不同 C. 如果一个图是可平面的，那么与它同构的图也是可平面的 D. 如果一个图是可平面的，那么与它同胚的图也是可平面的
如果一个3－正则简单平面图的每个面都有3条边，则这个图的边数是 A．3 B．4 C．5 D．6
图H是下面平面图G的一个平面嵌入，则图H的面数是 A．5 B．6 C．7 D．8
如果平面图G有v个顶点，e条边和f个平面，则 A．v?e?f?2 B．e?v?f?2 C．v?e?f?2 D．e?v?f?2
具有6 个顶点，12条边的连通简单平面图中，每个面的边数是 A．2 B．3 C．4 D．5
设G为一个连通的平面图，G有5个顶点和9条边，则G有 个面。6
n(n≥3)阶极大平面图的面数等于 。 2n?4
n(n≥3)阶极大平面图的边数等于 。 3n?6
100个顶点的极大连通平面图中最多有 个面。 196 100个面的极大连通平面图中最多有 个顶点。 52
画出面数最多的5顶点连通平面图的平面嵌入，并指出它有几个面。
6个面。
如果单图G是平面图，那么它一定有一个次数不超过5的顶。 不妨设G是连通的，否则考虑它的每一个连通分支。
设G有n个顶，m条边，f个面。因为G是单图，每个面至少有三条边，所以3f≤2m。 如果每个顶的次数都不小于6，那么有6n≤2m。
由欧拉公式得2?n?m?f≤m/3?m?2m/3?0，矛盾。 所以至少一个顶次数不超过5。
证明不存在7条棱的多面体。
若有7条棱的多面体，因为每个面上至少三条边，所以2? (G) ≥3??(G)，??(G)≤14/3，所以??(G)＝4。代入Euler公式得??(G)＝5，但??(G)＝4的多面体是惟一的，它有四个顶，与??(G)＝5矛盾。故无七棱多面体。
若简单平面图G的顶数不少于11个，则GC不是平面图。
画出面数最多的6顶点连通二分平面图的平面嵌入，并指出它有几个面。 4个面
完全图K2n能够分解为_______个边不相交的1因子之并。 n?1
完全图K2n+1能够分解为_______个边不相交的2因子之并。 n
下列图中可1因子分解的是
A． B． C． D．
给5位同学各写好一封信的信笺，又写好了给这5位同学的信封，把信笺都插错了信封的方法数为 A．48 B．44 C．36 D．24
有n把钥匙和n把锁混在一起，确定知道每把锁都能有一把钥匙打开，锁匠想把它们一对对的分开，那么有多少种分法是每对中的钥匙都无法打开锁的。（1）给出求解上述问题的递归公式，并证明之；（2）算出n=6时问题的解。
（1）设第i把钥匙为xi，第i把锁为yi，X={x1,x2, …,xn}，Y={y1,y2, …,yn}。把xi和yi视为顶点，当且仅当i≠j时，xi和yj相邻，得到二分图G。图G是n?1次正则的二分图，G有完备匹配。问题转化为求G的完备匹配个数b(n)。 如果钥匙x1错配给锁y2时，
（1）x2错配给y1，则可能的G中的完备匹配之个数为b(n?2)。 （2）x2不错配给y1，则可能的G中的完备匹配之个数为b(n?1)。 而x1错配的可能有n?1种。所以b(n)=(n?1)[b(n?1)+b(n?2)]。 （2）显然，b(1)=0，b(2)=1，
所以b(3)=2，b(4)=9，b(5)=44，b(6)=265。
给n位同学各写好一封信的信笺，又写好了给这5位同学的信封，把信笺都插错了信封的方法数设为b(n)，则b(n)
A．b(n?1)?b(n?2) B．(n?1)[b(n?1)?b(n?2)] C．n[b(n?1)?b(n?2)] D．2(n?1)[b(n?1)?b(n?2)]
给6位同学各写好一封信的信笺，又写好了给这6位同学的信封，把信笺都插错了信封的方法数为 A．120 B．240 C．265 D．288
下列哪个图无完备匹配 A．k次正则2分图 B．Petersen图（单星妖怪） C．K2n D．K2,4
r=5,当s= 时，完全二部图Kr,s才可能存在完美匹配。5 K10,10有 种完美匹配。 10
右图G的覆盖数??(G)＝ A．2 B．3 C．4 D．5
K3,5的覆盖数??(K3,5)＝ A．2 B．3 C．4 D．5
某公司有5名工作人员x1,x2,x3,x4,x5，他们每人承担y1,y2,y3,y4,y5这5项工作中的一项，
每人对每项工作创造的价值用下边的矩阵表示，公司领导根据每个人的特长如何合理分工，使得这5个工作人员对公司创造的总价值最大？
y1 y2 y3 y4 y5
x1轾35541犏
x2犏22022犏
x3犏24410犏
x4犏01100犏
x5犏12133犏臌
答：最佳匹配是{x1y4，x2y1，x3y3，x4y2，x5y5}
用匈牙利算法求下图的最大匹配。 x1x2x3x4x5 y1y2y3y4y5
{x1y1，x2y2，x3y5，x4y3，x5y4}
用匈牙利算法求下图的最大匹配。
x1x2x3x4x5
y1y2y3y4y5
{x1y2，x2y1，x3y3，x5y5}
今有赵、钱、孙、李、周五位教师，要承担语文、数学、物理、化学、英语五门课程。已知赵熟悉数学、物理、化学三门课程，钱熟悉语文、数学、物理、英语四门课程，孙、李、周都只熟悉数学、物理两门课程。问能否安排他们都只上他们熟悉的一门课程，使得每门课程都有人教（用图论方法求解）。
解：用x1,x2,x3,x4,x5表示赵、钱、孙、李、周五位教师，用y1,y2,y3,y4,y5表示语文、数学、物理、化学、英语五门课程。某位教师熟悉某门课程，则在两点之间连一条边，因此得到下面的二分图。
x1x2x3x4x5取S={x3,x4,x5}，则N(S)={y1,y2}，故|N(S)|<|S|。
由Hall定理知，不存在把x1,x2,x3,x4,x5皆许配的匹配，
因此不能安排他们都只上他们熟悉的一门课程，使得每门课程都有人
y1y2y3y4y5教。
对于下面的二分图，图中虚线给出了初始匹配M={x1y1，x2y4，x3y2，x4y3，x6y5}，从该初始匹配开始，利用匈牙利算法求其最大匹配。要求写出求解过程。（提示：虚线和实线都是该二分图的边）
x1x2x3x4x5x6
y1y2y3y4y5y6
解：由不饱和点x5出发构造增广路径P：x5y2x3y1x1y3x4y6，构造新的匹配：
M’={x5y2，x3y1，x1y3，x4y6，x2y4，x6y5}，M’是一个最大匹配，如下图虚线所示。
x1x2x3x4x5x6
y1y2y3y4y5y6
从下图中给定的M={x1y1，x3y5，x5y3}开始，用匈牙利算法求下图中
x1x2x3x4x5的完备匹配。
取未被M许配的顶x2，由x2出发得可增广轨x2y3x5y5x3y2， 构造新的匹配：M’={x1y1，x2y3，x5y5，x3y2}。
再取未被M’许配的顶x4，由x4出发得可增广轨x4y3x2y2x3y5x5y4，构
y1y2y3y4y5造新的匹配：M’’={x1y1，x4y3，x2y2，x3y5，x5y4}。
分派甲、乙、丙、丁、戊五人去完成五项工作，每人完成一项工作，每人完成各项任务时间如下表，试确定总花费时间为最少的指派问题。 任务 人 A B C D E 甲 乙 丙 丁 戊 12 8 7 15 4 7 9 17 14 10 9 6 12 6 7 7 6 14 6 10 9 6 9 10 9 用x1,x2,x3,x4,x5表示甲、乙、丙、丁、戊五个人，y1,y2,y3,y4,y5表示A、B、C、D、E五项工作，对应的权取20?工作时间，得权矩阵为
y1 y2 y3 y4 y5
x1x2x3x4x5 x1轾813111311犏 x2犏1211141414犏 x3犏1338611犏 x4犏56141410犏y1y2y3y4y5犏 x5犏1610131011臌取正常初始顶标l(yi)=0，l(x1)=13，l(x2)=14，l(x3)=13，l(x4)=14，l(x5)=16，构作G1如图， 用匈牙利算法求得最大匹配M={x1y2，x2y4，x3y5，x4y3，x5y1}，这是个完备匹配，因此即为最佳匹配。
因此甲完成B工作，乙完成D工作，丙完成E工作，丁完成C工作，戊完成A工作，总花费时间最少为7+6+7+6+4=30。
平面图的对偶图是连通图。
下图G是平面图。
设连通平面图G有6个面，8个顶点，则G 条边。 12
关于平面图G和其几何对偶图G*的关系，下列说法中不正确的是 A．平面图G的面数等于其对偶图的顶点数 B．平面图G的边数等于其对偶图的边数
C．平面图(G*)*≌G，其中G*表示G的对偶图 D．平面图的对偶图是连通平面图。
下列哪个图是极大平面图
A．顶为7，边数为15的单图 B．K5 C．K3,3 D．正方体
把平面分为α个区域，使任两个区域相邻，则α的最大值为 A．5 B．4 C．3 D．2
下列哪个图不是极大平面图
A．正四面体 B．正六面体 C．正八面体 D．正二十面体
下面哪个图是平面图 A．K5 B．K2,3 C．K6 D．K3,3
Kuratowsky认为可作为判定图的可平面性依据的基本不可平面图之一是 A．K3 A．K4 A．K5 A．K6
以下说法错误的是
A．同构的图具有相同的顶点数和边数 B．同胚的图边数相同，但顶点数不同
C．如果一个图是可平面的，那么与它同构的图也是可平面的 D．如果一个图是可平面的，那么与它同胚的图也是可平面的
下列图中哪个的对偶图是自身？ A．K3 B．K4 C．K5 D．K6
15阶圈C15的顶色数是 A．2 B．3 C．6 D．15
设G为n顶m条边的无向连通单图，下列命题为假的是 A．G一定有生成树 B．m一定大于n C．G的边色数?'(G)≥Δ(G) D．G的最大度Δ(G)≤n?1
完全图K15的顶色数是 A．2 B．3 C．6 D．15
完全图G的色多项式P(G，t)是 A．t(t?1)2 B．t(t?1)(t?2) C．t3 D．t(t?1)(t??)
图G的色多项式P(G，t)是t4?4t3?6t2?3t，则图G的边数是 A．3 B．4 C．5 D．6
图G的色多项式P(G，t)是t4?4t3?6t2?3t，则图G的顶数是 A．3 B．4 C．5 D．6
完全图K15的边色数是 A．2 B．3 C．6 D．15
15阶圈C15的边色数是 A．2 B．3 C．6 D．15
完全图K8的边色数是 A．2 B．3 C．7 D．8
求下图G的色多项式P(G，k)
答：P(G，k)=k(k?1)(k?2)(k?3)(k?4)+3k(k?1)(k?2)(k?3)+k(k?1)(k?2)
=k5?7k4+18k3?20k2+8k
求下图G的色多项式P(G，k)
答：P(G，k)=k(k?1)(k?2)(k?3)(k?4)+3k(k?1)(k?2)(k?3)+2k(k?1)(k?2)
=k5?7k4+20k3?26k2+10k
求下图G的色多项式P(G，k)
答：P(G，k)=k(k?1)(k?2)(k?3)(k?4)+2k(k?1)(k?2)(k?3)+k(k?1)(k?2)
=k5?8k4+24k3?31k2+14k
求下图G的色多项式P(G，k)
答：P(G，k)=k(k?1)(k?2)(k?3)(k?4)+2k(k?1)(k?2)(k?3)
=k5?8k4+23k3?28k2+12k
K3,4的边色数为 。
Petersen图（单星妖怪）的边色数为 。
下图的点色数为_______；边色数为_______
有8个顶的轮，其顶色数是 。 有8个顶的轮，其顶色数是 。 顶大于2的树T的顶色数是 。
右图G的独立数??(G)＝ A．1 B．2 C．3 D．4
右图G的支配数??(G)＝ A．1 B．2 C．3 D．4
右图G的独立数??(G)＝ A．1 B．2 C．3 D．4
右图G的支配数???(G)＝ A．1 B．2 C．3 D．4
任意一个p阶图，总有K3子图或4个点的独立集，则p的最小值为 A．6 B．7 C．8 D．9
一群人中，总有3个人互相认识或者彼此不认识，则这群人的人数至少是 A．5 B．6 C．7 D．8
任意一个p阶图，总有K3子图或3个点的独立集，则p的最小值为( ) A．4 B．5 C．6 D．7
有8种化学品a，b，c，d，e，f，g，h要放进贮藏室保管。出于安全原因，下列各组药品不能贮在同一个室内：a-f，a-c，a-h，e-f，e-g，g-h，b-h，b-d，c-d，f-g，b-f，d-e，c-g，d-g，问贮藏这8种药品至少需要多少个房间？ 以8种药品作为顶点，若两种药品不能贮在同一个室内，则它们之间有一条边，这样得右图，转化为图的正常顶着色问题。
g（1）对各顶点按次数的递减顺序排列为gfdechab；
（2）对g及不与之相邻点a、b着1色；
e（3）对f及不与之相邻点d、h着2色； fch（4）对e和c着3色。 d故?(G)≤3；又因为e，f，g为K3子图，故着色数?(G)≥3，从而?(G)=3。
ba因此贮藏这8种药品至少需要3个房间。贮藏方式之一为gab，dfh，
ce。
以下说法错误的是
A．欧拉回路必经过图中所有的边 B. 欧拉回路必经过图中所有的顶点 C. 哈密顿回路必经过图中所有的边 D. 哈密顿回路必经过图中所有的顶点
无向图G存在欧拉行迹，当且仅当 A．G中所有结点的度数全为偶数 B．G中至多有两个奇数度结点
C．G连通且所有结点的度数全为偶数 D．G连通且至多有两个奇数度结点
以下必为欧拉图的是
A．顶点度数全为偶数的连通图 B．奇数顶点只有2个的图 C．存在欧拉迹的图 D．没有回路的连通图。
下图中是Euler图的是
A． B． C． D．
下列图中为欧拉图的是
A． B． C． D．
下图中既是欧拉图又是哈密顿图的是 A．K9 B．K10 C．K2,3 D．K3,3
设G为完全二部图K2,3，下面命题中为真的是 A．G为Euler图 B．G为Hamilton图 C．G为平面图 D．G为正则图
在Petersen图（单星妖怪）中至少添加 条边才能构成欧拉图。5
有4个顶的无向连通图G是欧拉图，则它的顶次数序列可能是 A．1,2,3,4 B．2,4,6,8 C．1,2,4,6 D．5,2,3,4
设m≥1，n≥3，下面命题中，为真的是 A．完全图Kn都是Euler图 B．完全二分图Kn,m都是Euler图 C．完全图Kn都是Hamilton图 D．完全二分图Kn,m都是Hamilton图
构造Euler图，其顶点数p和边数q满足p，q的奇偶性相反。
有四个村庄的地下各有一个防空洞甲、乙、丙、丁，相邻两个防空洞之间有地道相通，且每个防空洞各有一条地道与地面相通，如下图所示（图中◎表示地道）。问能否从某一个防空洞开始，每个地道走一次且仅走一次后回到该防空洞。要求有一定的分析过程。 甲乙
丁丙
求下图的中国邮路问题，设vi为邮局。（1）写出“倍边”的过程；（2）列出最后所得的从v1出发的中国邮路。
v6v23 2412
v1v33v7 243 v5v47
（1）图中，奇次顶集为{v1,v2,v4,v3}。计算出每对顶的距离：
d(v1,v2)=4，d(v1,v3)=5，d(v1,v4)=7，d(v2,v3)=2，d(v2,v4)=5，d(v3,v4)=3， 求出{v1,v2,v4,v3}构成的完全加权图的最佳匹配M={v1v2,v3v4}，
P(v1,v2)=v1v7v2，P(v3,v4)=v3v4，在G中沿P(v1,v2)与P(v3,v4)变成同权“倍边”。 （2）v1v7v2v3v4v5v1v6v2v7v3v4v7v1。
一个连通的无向图G，如果它的所有顶点的度数都是偶数，那么它具有一条 A．Hamilton回路 B．Euler回路 C．Hamilton轨 D．含所有顶的圈
设完全图Kn有n个顶点(n≥2)，m条边，Kn中存在欧拉回路的条件是
A．m为奇数 B．n为偶数 C．n为奇数 D．m为偶数
K7中两两无公共边的Hamilton圈有 A．2 B．3 C．4 D．7
下面哪个图不是Hamilton图
A． B． C． D．
Petersen图（单星妖怪）是Hamilton图。
若G是一个Hamilton图，则G一定是( )． A．平面图 B．自对偶图 C．欧拉图 D．连通图
若G是一个Euler图，则G一定是( )． A．平面图 B．Hamilton图 C．连通图 D．自对偶图
Petersen图（单星妖怪）是 A．Hamilton图 B．Euler图 C．平面图 D．非平面图
K11中有 条边不重的Hamilton回路。5
若图G的任一对顶u，v皆有d(u)?d(v)≥V(G)，则G是Hamilton图。
若G是Hamilton图，则对于V(G)的任意子集S都有??(G?S)≤|S|。
在下列图中，既是Euler图又是Hamilton图的是
A． B． C． D．
设G是n(n≥3)阶单图，则其顶的最小次数?≥n/2是G为哈密尔顿图的 A．必要条件 B．充分条件 C．充分必要条件 D．既不充分也不必要条件
设G是有10个顶点的无向图，对于G中任意两个不邻接的顶点u和v，均有d(u)+d(v)≥9，则G是Hamilton图。
作一个图，使其是Euler图但非Hamilton图。
画出两个具有8条边、6个顶的无向简单图，并使其是Euler图。 画出两个具有7条边、6个顶的无向简单图，并使其是Euler图。
下列图中，v2可达v4的是 v1v1v4v4v1v4v4v1 v2v2v3v2v3v3v2v3A． B． C． D．
下列有向图中是强连通图的是
A． B． C． D．
对具有m条边的单图定向能得到______个不同的有向图。2m
设有向图G有16条边，则所有顶点的出度之和为 。
下列有向图中是强连通图的是
A． B． C． D．
4个顶的不同竞赛图共有 A．6个 B．16个 C．32个 D．64个
把单星妖怪定向成强连通有向图。
若一个有向图G是单向连通的，则它必是弱连通图的。 若一个有向图G是单向连通的，则它必是强连通图的。 每个竞赛图都有有向Hamilton轨。
竞赛图G中v为惟一王的充要条件是v得分为|V(G)?1|。 强连通竞赛图是有向Hamilton图。
有向Hamilton图是强连通图。
若有向图的底图为G，则此有向图中有长?(G)的轨。
在任何有向图中，所有顶点的入度之和等于所有顶点的出度之和。 若竞赛图不是有向Hamilton图，则它有惟一的王。 作一个5个顶的竞赛图，使它的王不惟一。
写出下面竞赛图中的王： 。v1,v2,v3,v5
v1 v5v2 v3v4
求下图中的最大流，其中s是源，t是汇，并指出此网络的一个最小截。（括弧旁第一个数字
表示容量，第二个数字表示当前弧中的流量） v1v3(6,3) (5,3)(7,4) (4,1)st(6,1)
(8,5)(3,1)(8,4)
v2(7,6)v4
求下图中的最大流，其中s是源，t是汇，并指出此网络的一个最小截。（括弧旁第一个数字表示容量，第二个数字表示当前弧中的流量）
v1v3(4,3)
(5,3)(3,3)
(1,1)st(3,0) (1,1) (5,1)(2,1) v2(2,2)v4
在如下网络N中，每条弧旁边的数对(x,y)分别表示该弧的容量为x、一个可行流f在相应弧的流量为y。（1）写出该网络中一条从源s到汇t的可改进流量最大的路P；（2）基于P，构造流f的修改流；（3）继续修改，求出从s到t的最大流。
v1v2(1,1) (7,6)(4,3)(3,2)(4,3) (3,2)t(2,2)sv3(5,3)
(3,2)(8,3)(10,4)
(4,2)v4v5
求下图中从s到t的最大流。
v1(1,1)v2 (4,3)(3,2)(7,6)(4,3)
sv3(2,2)t(3,2)
(5,3)(10,4)(8,3) (3,2)v1(1,1)v2
v4(4,2)v5 (4,4)(3,3)(7,7)(4,4)
sv3(2,2)t
(3,3) (5,5)(10,7)(8,7) (3,3)
v4(4,4)v5
v4v1v635
求下图中从s到t的最大流。
72698 2
4sv2v7t4v31531537v84v5
v1(9,2)s(4,4)(1,0)(3,0)(7,2)(6,2)v2v4(5,0)(2,2)v7(5,4)v6(8,2)t(7,4)v8(4,4)(2,2)(4,0)(1,0)(3,0)v3(5,4)v5(3,0)
存在割顶的连通图其顶连通度必为
1。
有桥的连通图其边连通度必为1。
下图的点连通度等于 ，边连通度等于_________。
?(Kn)=
A．n
B．n?1
C．2
D．1
?'(Kn)=
A．n B．n?1 C．2 D．1
图G如右，ef边不是图G的桥是因为 A．e的次数是3 baB．ef边平行于cd边
gefC．G是3次正则图
dcD．G??ef是连通图
下图中的顶连通度为 。下图中的边连通度为 。 3 3