图论中有图题目 一、 4个结点、6个结点和8个结点的三次正则图没有一个简单的办法能确定图的色数以及用尽可能少的颜色给图的节点着色。Welch-Powell给出了一个使颜色数尽可能少（不一定最少）的结点着色方法，在实际使用中比较有效： 第1步、 将图的结点按度数的非增顺序排列；第2步、用第1种颜色给第1个结点着色，并按照结点排列顺序，用同一种颜色给每个与前面已着色的结点不邻接的结点着色；第3步、换一种颜色对尚未着色的结点按上述方法着色，如此下去，直到所有结点全部着色为止。 例1 分别求右面两图的色数

（1）由于（1）中图G中无奇数长的基本回路，由定理可知??G??2。 （2）由于（2）中图G含子图轮图W4，由于??W4??4，故??G??4。又因

为此图的最大度??G??4，G不是完全图，也不是奇数长的基本回路，由定理可知（对n阶轮图Wn，n为奇数时有??Wn??3，n为偶??G????G??4，因而??G??4。

数时有??Wn??4；对n阶零图Nn，有??Nn??1；完全图Kn，有??Kn??n；对于二部图G??V1,V2,E?,E??时即??Nn??1，E??时即??G??2；在彼得森图G中，存在奇数长的基本回路，因而??G??3，又彼得森图既不是完全图也不是长度为奇数的基本回路，且??G??3，由定理??G??3，故??G??3） 例2 给右边三个图的顶点正常着

色，每个图至少需要几种颜色。 答案：（1）

(1)(2)??G??2；（2）

（3）??G??4 ??G??3；

例3 有8种化学品A,B,C,D,P,R,S,T

(2)(1)(3)要放进贮藏室保管。出于安全原因，

下列各组药品不能贮在同一个室内：A-R, A-C, A-T, R-P, P-S, S-T, T-B, B-D, D-C, R-S, R-B,

P-D, S-C ,S-D，问贮藏这8种药品至少需要多少个房间？

TR解 以8种药品作为结点，若两种药品不能贮在同一个室RPPCDD内，则它们之间有一条边，这样得右图，转化为图的正常着

BB色问题。（1）对各结点按度数的递减顺序排列为SRDPCTAB；A（2）对S及不与之相邻点A，B着c1色；（3）对R及不与之

K9K1K2K3K4K6K5J1SSCAJ2J3J4T相邻点D着c2色；（4）对P和C着c3色。故着色数??G??3；K8K7又因为因S,D,P为K3子图，故着色数

??G??3，从而

B1B2B3B4B5??G??3。因此贮藏这8种药品至少需要3个房间。贮藏方式之一为SAB, RDT, PC。

(考试排考或老师排课让选修的学生避免冲突的问题类似处理！)

二、强连通一定单向连通，单向连通一定弱连通！

弱连通图单向连通图单向连通图强连通图强连通图强连通图

弱连通图、单向连通图和强连通图三、

哈密顿图欧拉图同构的无向图欧拉图哈密顿图均不是同构的有向图

1、设G为无向欧拉图，求G中一条欧拉回路的Fleury算法如下：第1步，任取G中的一

个结点v0，令P0?v0；第2步，假设Pi?v0e1v1e2Lviei已选好，按下面方法从（1）ei?1与ei相关联，（2）除非无别的边可供选择，否则ei?1不E??e1,e2,L,ei?中选ei?1：

应该是Gi?G??e1,e2,L,ei?的断边；第3步，当第2步不能执行时，算法停止。 （有向欧拉图的欧拉回路可类似求出，可用于解决邮路问题）

邮路问题用图论的概念描述如下：在一个带权图G中，怎样找到一条回路C，使得C包含G中的每一条边至少一次，而且回路C具有最小权。C分以下三种情况：（1）如果G是欧拉图，必定有欧拉回路，C即可找到；（2）如果G是具有从vi到vj的欧拉通路的半欧拉图，C的构造如下：找到从vi到vj的欧拉通路及vi到vj的最小权通路（即最短路径）--这两条通路和并在一起就是最小权回路；（3）如果G不是半欧拉图，一般说来，G中包含多条边的回路，其中夫的边数与奇数结点数目有关，若奇数结点多于2，则回路中会出现更多的重复的边。问题是怎样使重复边的权综合最小。在理论上已证明：一条包括G的所有边的回路C具有最小权当且仅当：（1，每条边最多重复一次，（2，在G的每个回路上，有重复边的权之和小于回路权的一半。 例：求右图所示的带权图中最优投递路线，邮局40在D点。 506358解 先观察奇度结点，此图中有E,F两个。用标

1912号法求出其间最短路径EGF，其权为28。然后23BEAG将最短路径上的边重复一次，于是得欧拉图G，

*

30D1020C求从D出的一条欧拉回路，如

DEGFGEBACBDCFD，其权为281=35+8+20+20+8+40+50+30+19+6+12+10+23。

2、求接近最小权哈密顿回路的“最邻近”算法：设G??V,E,W?是有n个顶点的无向完全图，（1）任取v0?V作为始点，令L为v0，k?0；（2）令（3）若w?vk,x??min?w?vk,v?v不在L中?，置vk?1?x。置L?v0v1Lvk?1,k?k?1；；（4）置L?v0v1Lvkv0，结束。（可近似解决货郎担问题） k?n?1，转（2）

例1 用最邻近算法求下图的最短哈密尔顿回路。

Fa146b561478ae57ae586bc1456b7e5c10ddc10d

所得长度为14+6+5+5+7=37，与最短7+8+5+10+6=36很接近了！

例2 求下图的最短哈密尔顿回路。

b1018127141118b127101811b710b1412cadcadcadca1114d

三条比较，最小权为47。

例3 已知A,B,C,D,E,F,G7个人中，A会讲英语，B会讲英语和汉语，C会讲英语、意大利语和俄语，D会讲日语和汉语，E会讲意大利语和德语，F会讲俄语，G会讲俄语、日语和法语。能否将他们的座位安排在圆桌旁，使得每个人都能与他身边的人交谈？ （按哈密尔顿回路安排就是了！）

例4 11个学生要共进晚餐，他们将坐成一个圆桌，计划要求每次晚

BAGF111098765CDE1234餐上每个学生有完全不同的邻座，这样能攻进晚餐几天？（K11共有

11?11?1??55条边，每条哈密尔顿回路有11条边，因而共有5条没有公2共边的哈密尔顿回路，可吃5天！分别用2，3，4，5与11互素，以它们为步长能找到！） 半哈密顿图与哈密顿图补例：

彼德森图

补充内容：

设G是无向完全图，若对G的每条边指定一个方向，所得的图称为竞赛图。证明：在无又向回路（或有向圈）的竞赛图D??V?D?,E?D??中，对任意u,v?V?D?,d??u??d??v?

（用反证法，见于《离散数学习题与解析》胡辛启清华第2版）

可以证明：对于每个竞赛图D，至多改变一条边的方向后就可以变成哈密尔顿图。

四、求最小生成树 1、破圈法过程演示

(1)令E??E；(2)选取E?中的一条简单回路C, 设C中权最大的边为e，令E??E??{e}；(3)重复步骤(2), 直到E??V?1为止。

12910题目

2118574136 最后结果

2981356

2910118574136910211857610139211813569211856

132、Kruskal算法过程演示

(1)首先将边按权值由小到大排成序列S, 令i?1,E??{S[1]}；(2)令i?i?1,选取边S[i]与 E?中的边不构成简单回路，则令E??E?U{S[i]}；(3)重复步骤(2), 直到E??V?1为止。

212212135135613821356

3、Prim算法过程演示

(1)从V中任意选取结点v0，令V??{v0}；(2)在V?与V?V?之间选一条权最小的边

e?(vi,vj)，其中vi?V?,vj?V?V?并且令E??E?U{e},V??V?U{vj}；(3)重复步骤(2),

直到V??V为止。

9998988521598159821359821356

增加破圈法一例演示：