发布时间 : 星期二 文章2013四川师范大学 图论期末考试复习题更新完毕开始阅读11b01ceeaef8941ea76e05cb
{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的顶色数是 。