2013四川师范大学 图论期末考试复习题(3)

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

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库2013四川师范大学 图论期末考试复习题(3)在线全文阅读。