2015电子科技大学 - 图论期末考试复习题

2015电子科技大学 图论考试复习题

关于图论中的图，以下叙述不正确的是

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的树叶数为 。

由欧拉公式得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

本文来源：https://www.bwwdw.com/article/z8i8.html