离散数学图论与系中有图题目————————————————————————————————作者：————————————————————————————————日期：图论中有图题目 一、 没有一个简单的办法能确定图的色数以及用尽可能少的颜色给图的节点着色。

Welch-Powell 给出了一个使颜色数尽可能少（不一定最少）的结点着色方法，在实际使用中比较有效： 第1步、 将图的结点按度数的非增顺序排列；第2步、用第1种颜色给第1个结点着色，并按照结点排列顺序，用同一种颜色给每个与前面已着色的结点不邻接的结点着色；第3步、换一种颜色对尚未着色的结点按上述方法着色，如此下去，直到所有结点全部着色为止。

例1 分别求右面两图的色数（1）由于（1）中图G 中无奇数长的基本回路，由定理可知()2G χ=。

（2）由于（2）中图G 含子图轮图4W ，由于()44W χ=，故()4G χ≥。

又因为此图的最大度()4G ∆=，G 不是完全图，也不是奇数长的基本回路，由定理可知()()4G G χ≤∆=，因而()4G χ=。

（对n 阶轮图n W ，n 为奇数时有()3n W χ=，n 为偶数时有()4n W χ=；对n 阶零图n N ，有()1n N χ=；完全图n K ，有()n K n χ=；对于二部图12,,,G V V E E =<>=Φ时即()1n N χ=，E ≠Φ时即()2G χ=；在彼得森图G 中，存在奇数长的基本回路，因而()3G χ≥，又彼得森图既不是完全图也不是长度为奇数的基本回路，且()3G ∆=，由定理()3G χ≤，故()3G χ=） 例 2 给右边三个图的顶点正常着色，每个图至少需要几种颜色。

答案：（1）()2G χ=；（2）()3G χ=；（3）()4G χ= 例3 有8种化学品A,B,C,D,P,R,S,T要放进贮藏室保管。

出于安全原因，下列各组药品不能贮在同一个室内：A-R, A-C, A-T, R-P, P-S, S-T, T-B, B-D, D-C, R-S, R-B,4个结点、6个结点和8个结点的三次正则图(2)(1)(3)(2)(1)P-D, S-C ,S-D ，问贮藏这8种药品至少需要多少个房间？解 以8种药品作为结点，若两种药品不能贮在同一个室内，则它们之间有一条边，这样得右图，转化为图的正常着色问题。

（1）对各结点按度数的递减顺序排列为SRDPCTAB ；（2）对S 及不与之相邻点A ，B 着1c 色；（3）对R 及不与之相邻点D 着2c 色；（4）对P 和C 着3c 色。

故着色数()3G χ≤；又因为因S,D,P 为3K 子图，故着色数()3G χ≥，从而()3G χ=。

因此贮藏这8种药品至少需要3个房间。

贮藏方式之一为SAB, RDT, PC 。

(考试排考或老师排课让选修的学生避免冲突的问题类似处理！)二、强连通一定单向连通，单向连通一定弱连通！强连通图强连通图强连通图单向连通图单向连通图弱连通图弱连通图、单向连通图和强连通图三、均不是哈密顿图哈密顿图欧拉图欧拉图同构的有向图同构的无向图1、设G 为无向欧拉图，求G 中一条欧拉回路的Fleury 算法如下：第1步，任取G 中的一SR D P CT B A AB TC P DR S K 1K 2K 3K 9K 7K 4K 8K 5K 6J 1B 1B 3J 2B 4B 2J 3B 5J 4个结点0v ，令00P v =；第2步，假设0112i i i P v e v e v e =L 已选好，按下面方法从{}12,,,i E e e e -L 中选1i e +：（1）1i e +与i e 相关联，（2）除非无别的边可供选择，否则1i e +不应该是{}12,,,i i G G e e e =-L 的断边；第3步，当第2步不能执行时，算法停止。

（有向欧拉图的欧拉回路可类似求出，可用于解决邮路问题）邮路问题用图论的概念描述如下：在一个带权图G 中，怎样找到一条回路C ，使得C 包含G 中的每一条边至少一次，而且回路C 具有最小权。

C 分以下三种情况：（1）如果G 是欧拉图，必定有欧拉回路，C 即可找到；（2）如果G 是具有从i v 到j v 的欧拉通路的半欧拉图，C 的构造如下：找到从i v 到j v 的欧拉通路及i v 到j v 的最小权通路（即最短路径）--这两条通路和并在一起就是最小权回路；（3）如果G 不是半欧拉图，一般说来，G 中包含多条边的回路，其中夫的边数与奇数结点数目有关，若奇数结点多于2，则回路中会出现更多的重复的边。

问题是怎样使重复边的权综合最小。

在理论上已证明：一条包括G 的所有边的回路C 具有最小权当且仅当：（1，每条边最多重复一次，（2，在G 的每个回路上，有重复边的权之和小于回路权的一半。

例：求右图所示的带权图中最优投递路线，邮局在D 点。

解 先观察奇度结点，此图中有E,F 两个。

用标号法求出其间最短路径EGF ，其权为28。

然后将最短路径上的边重复一次，于是得欧拉图*G ，求从D 出的一条欧拉回路，如DEGFGEBACBDCFD ，其权为281=35+8+20+20+8+40+50+30+19+6+12+10+23。

2、求接近最小权哈密顿回路的“最邻近”算法：设,,G V E W =<>是有n 个顶点的无向完全图，（1）任取0v V ∈作为始点，令L 为0v ，0k =；（2）令()(){},min ,k k w v x w v v v L =不在中，置1k v x +=。

置011,1k L v v v k k +==+L ；（3）若1k n <-，转（2）；（4）置010k L v v v v =L ，结束。

（可近似解决货郎担问题） 例1 用最邻近算法求下图的最短哈密尔顿回路。

105566148714abcd e147655edcb a107865edcba所得长度为14+6+5+5+7=37，与最短7+8+5+10+6=36很接近了！10408202335126193050AB CFEGD例2 求下图的最短哈密尔顿回路。

1112141018147101112187ad cbad cbadcb三条比较，最小权为47。

例3 已知A,B,C,D,E,F,G7个人中，A 会讲英语，B 会讲英语和汉语，C 会讲英语、意大利语和俄语，D 会讲日语和汉语，E 会讲意大利语和德语，F 会讲俄语，G 会讲俄语、日语和法语。

能否将他们的座位安排在圆桌旁，使得每个人都能与他身边的人交谈？ （按哈密尔顿回路安排就是了！）例4 11个学生要共进晚餐，他们将坐成一个圆桌，计划要求每次晚餐上每个学生有完全不同的邻座，这样能攻进晚餐几天？（11K 共有()11111552-=条边，每条哈密尔顿回路有11条边，因而共有5条没有公共边的哈密尔顿回路，可吃5天！分别用2，3，4，5与11互素，以它们为步长能找到！） 半哈密顿图与哈密顿图补例：补充内容：设G 是无向完全图，若对G 的每条边指定一个方向，所得的图称为竞赛图。

证明：在无又向回路（或有向圈）的竞赛图()(),D V D E D =<>中，对任意()()(),,u v V D du d v ++∈≠（用反证法，见于《离散数学习题与解析》胡辛启清华第2版）可以证明：对于每个竞赛图D ，至多改变一条边的方向后就可以变成哈密尔顿图。

四、求最小生成树 1、破圈法过程演示(1)令E E '=；(2)选取E '中的一条简单回路C, 设C 中权最大的边为e ，令{}E E e ''=-；(3)重复步骤(2), 直到1E V '=-为止。

10714181211bcd aA B C FG ED 1092468135711彼德森图题目108765431119122 最后结果29135688653111922911135681010876531119229111345678102、Kruskal 算法过程演示(1)首先将边按权值由小到大排成序列S, 令1,{[1]}i E S '==；(2)令1,i i =+选取边[]S i 与E '中的边不构成简单回路，则令{[]}E E S i ''=U ；(3)重复步骤(2), 直到1E V '=-为止。

8213566531253123121213、Prim 算法过程演示(1)从V 中任意选取结点0v ，令0{}V v '=；(2)在V '与V V '-之间选一条权最小的边(,)i j e v v =，其中,i j v V v V V ''∈∈-并且令{},{}j E E e V V v ''''==U U ；(3)重复步骤(2),直到V V '=为止。

8653192853192851928519859899增加破圈法一例演示：1253345216125433452716618725434、求下列最小生成树的权值24231C(T)=1+2+3=656413312C(T)=1+2+3+1=72015317232836916841C(T)=1+3+4+8+9+23=4897638105421C(T)=1+2+3+5+7=18716681231361717C(T)=3+6+6+7=226816613491157C(T)=4+5+6+7=2267108323121154910v 2v 3v 4v 1v 5v 6v 7C(T)=2+3+4+5+6+10=30233476510021C(T)=2+2+3+5+6+100=1182015121098874C(T)=8+9+4+7=285576412331C(T)=1+3+3+2+1=1081612949785555879491216812663354455445336621C(T)=1+2+3+5+7=18102457893611111163987542105、在右图所示的带权图中，共有多少棵生成树，他们的权各为多少？，其中哪些是图中的最小生成树？43221adcb五、求最优二叉树对给定的实数序列12t w w w ≤≤≤L ，构造最优r 元树的递归算法：1、求最优二元树的Huffman 算法：第一步，连接以12,w w 为权的两片树叶，得一个分支点及其所带的权12w w +；第二步，在123,,,t w w w w +L 中选出两个最小的权，连接它们对应的结点（不一定都是树叶），又得分支结点及其所带的权；重复第二步，直到形成1t -个分支点，t 片树叶为止。