第2章图论

目录第一章图的基本概念 (1)二路和连通性 (3)第二章树 (3)第三章图的连通度 (4)第四章欧拉图与哈密尔顿图 (5)一，欧拉图 (5)二．哈密尔顿图 (6)第五章匹配与因子分解 (9)一．匹配 (9)二．偶图的覆盖于匹配 (10)三．因子分解 (11)第六章平面图 (14)二．对偶图 (16)三．平面图的判定 (17)四．平面性算法 (20)第七章图的着色 (24)一．边着色 (24)二．顶点着色 (25)第九章有向图 (30)二有向树 (30)第一章图的基本概念1.点集与边集均为有限集合的图称为有限图。

2.只有一个顶点而无边的图称为平凡图。

3.边集为空的图称为空图。

4.既没有环也没有重边的图称为简单图。

5.其他所有的图都称为复合图。

6.具有二分类（X, Y）的偶图（或二部图）：是指该图的点集可以分解为两个（非空）子集X 和Y ，使得每条边的一个端点在X 中，另一个端点在Y 中。

7.完全偶图：是指具有二分类（X, Y）的简单偶图，其中X的每个顶点与Y 的每个顶点相连，若|X|=m，|Y|=n，则这样的偶图记为Km,n8. 定理1 若n 阶图G 是自补的（即），则n = 0, 1（mod 4）9. 图G 的顶点的最小度。

10. 图G 的顶点的最大度。

11. k-正则图: 每个点的度均为 k 的简单图。

例如,完全图和完全偶图Kn,n 均是正则图。

12. 推论1 任意图中，奇点的个数为偶数。

13.14. 频序列：定理4 一个简单图G 的n 个点的度数不能互不相同。

15. 定理5 一个n 阶图G 相和它的补图有相同的频序列。

16.17.18. 对称差：G1△G2 = (G1∪G2) - (G1∩G2) = (G1-G2)∪(G2-G1)19. 定义： 联图 在不相交的G1和G2的并图G1+G2中，把G1的每个顶点和G2的每个顶点连接起来所得到的图称为G1和G2的联图，记为G1∨G220. 积图：积图 设G1= (V1, E1)，G2 = (V2, E2)，对点集V = V1×V2中的任意两个点u =(u1,u2)和v = (v1,v2)，当(u1 = v1和 u2 adj v2) 或 (u2 = v2 和 u1 adj v1) 时就把 u 和 v 连接起来所得到的图G 称为G1和G2积图。

最短路课程设计一、课程目标知识目标：1. 学生能理解最短路径问题的基本概念，掌握其在现实生活中的应用。

2. 学生掌握图的基本表示方法，能够建立问题的图模型。

3. 学生能够阐述Dijkstra算法和Floyd算法的基本原理，并理解其适用场景。

技能目标：1. 学生能够运用图的相关知识建立实际问题模型，解决最短路径问题。

2. 学生通过案例学习和实践操作，掌握Dijkstra算法和Floyd算法的具体步骤，具备运用算法解决问题的能力。

3. 学生能够运用所学知识，对实际生活中的最短路径问题进行合理分析和有效解决。

情感态度价值观目标：1. 培养学生对图论和算法的兴趣，激发他们探究问题的热情。

2. 培养学生面对复杂问题时，运用所学知识进行分析和解决的能力，增强自信心。

3. 通过团队合作解决问题，培养学生的团队协作能力和沟通能力，提高他们的集体荣誉感。

本课程针对学生年级特点，结合图论和算法知识，以实际问题为载体，引导学生通过自主学习、合作探究和实际操作，培养解决问题的能力。

课程目标具体、可衡量，旨在使学生在掌握知识、技能的同时，培养积极的情感态度和价值观。

二、教学内容1. 图的基本概念：图、顶点、边、权、路径、最短路径等。

相关教材章节：第二章 图论基础2. 图的表示方法：邻接矩阵、邻接表、关联矩阵等。

相关教材章节：第二章 图论基础3. 最短路径问题：介绍最短路径问题的背景和应用。

相关教材章节：第三章 最短路径问题4. Dijkstra算法：算法原理、步骤、示例。

相关教材章节：第三章 最短路径问题5. Floyd算法：算法原理、步骤、示例。

相关教材章节：第三章 最短路径问题6. 实践案例分析：结合实际案例，运用Dijkstra和Floyd算法解决最短路径问题。

相关教材章节：第三章 最短路径问题教学内容安排和进度：第一课时：图的基本概念及表示方法。

第二课时：最短路径问题引入，介绍Dijkstra算法。

第三课时：Dijkstra算法实践操作。

第1章 图论预备知识1.1解：(1) p={φ,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}(2) p={,{a},{{b,c}},{a,{b,c}}} (3) p={,{}}(4) p={,{},{{}},{,{}}}(5)p={,{{a,b}},{{a,a,b}},{{a,b,a,b}},{{a,b},{a,a,b}},{{a,b},{a,b,a,b}},{{a,b},{a,a,b},{a,b,a,b}}} 1.2 解：(1) 真 (2) 假 (3)假 (4)假 1.3 解：(1) 不成立，A={1} B={1,2} C={2} (2) 不成立，A={1} B={1,2} C={1,3}1.4 证明：设(x,y)∈(A ∩B)X(C ∩D) 说明x ∈A ∩B,y ∈C ∩D 由于 x ∈A,y ∈C 所以 (x,y) ∈A X C 由于x ∈B,y ∈D 所以 (x,y) ∈B X D 所以 (x,y) ∈（A X C ）∩（B X D ） 反过来，如果（x,y ）∈(A X C) ∩（B X D ） 由于 (x,y) ∈（A X C ）所以 x ∈A,y ∈C 由于 (x,y) ∈（B X D ）所以x ∈B,y ∈D 所以x ∈(A ∩B) y ∈(C ∩D) 所以 (x,y) ∈(A ∩B)X(C ∩D)所以(A ∩B)X(C ∩D)= (A X C) ∩（B X D ） 1.5 解：Hasse 图φφφφφφφφφ极大元{9,24,10,7} 极小元{3,2,5,7} 最大元{24} 最小元{2}1.6 解(2)关系图为：(3)不存在最大元，最小元为{2}1.7 解：(1)R={<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<2,1>,<2,3>,<3,2>} (2)略(3)I A ⊆R 故R 是自反的。

)3( 题属中国邮路问题除第欧拉图与哈密尔顿图<1.>给定一个由16条线段构成的图形（见下图）.证明：不能引一条折线与每一线段恰好相交一次（折线可以是不封闭的和自由相交的，但他的顶点不在给定的线段上）证明：建立一个图G ：顶点i v 代表图形的区域(1,2,3,4,5,6)i X i ，顶点i v 与j v 之间连接的边数等于区域i X 与j X 公共线段的数目.于是，将上图的区域和边可转化成下图：由顶点度数知不存在欧拉路，从1X 到6X 只能相交于外面的两条线段.<2.>下列图形中哪些能一笔画成.解：只需考虑该图是否有欧拉路（即有两个奇点或者无奇点），故第一个和第三个可以一笔画成，第二个不能一笔画成.<4.>下图是某个展览馆的平面图，其中每个相邻的展览室有门相通.证明：不存在一条从A 进入，经过每个展览室恰好一次再从A 处出来的参观路线.证：用顶点代表展览室，两顶点相邻当且仅当这两点所对应的展览室有门相通，则可得一个连通简单图G （见下图）.因此，只要证明G 中不存在H —回路即可.具体理由如下：令}{1216,,,S y y y = ，则显然S 是G 的真子集，而()1816G S S ω-=>=（x 共18个，y 共16个），故由讲义中定理2.3知不存在H —回路.<5.>某次会议有20人参加，其中每个人都至少有10个朋友.这20人围一桌入座，要想使与每个人相邻的两位都是朋友是否可能？解:用顶点代表人，两人是朋友时相应顶点间连一边，得到一个无向图(,)G V E =.只要证明G 中存在H —回路即可. G 是10阶连通图，对于20n =，且()10,()10G G d u d v ≥≥，可得：()()20G G d u d v n +≥=，故由讲义中定理2.4知G 中存在H —回路.<6.>已知,,,,,,a b c d e f g 七个人中，a 会讲英语，b 会讲英语和汉语，c 会讲英语、意大利语和俄语，d 会讲汉语和日语，e 会讲意大利语和德语，f 会讲俄语、日语和法语，g 会讲德语和法语.能否将他们的座位安排在圆桌旁，使得每个人都能与他身边的人交谈.解：用七个顶点表示这七个人.若两人能交谈（会讲同一种语言），就在这两顶点之间连一条边，得到图G .只要证明图G 中存在H -回路即可. 具体结果如下：c e g f d b a c 意大利语德语法语日语汉语英语英语 .<7.>设G 是分划为,X Y 的二部图，且X Y ≠，则G 一定不是H —图。

第7章 图论图论是建立和处理离散型数学模型的重要数学工具，它已发展成具有广泛应用的一个数学分支。

图论的发展已有200多年的历史，它最早起源于一些数学游戏的难题研究。

1736年瑞士数学家欧拉（L.Eluer ）发表了关于解决哥尼斯堡七桥问题的一篇文章，标志着图论的正式诞生。

从19世纪中叶到20世纪中叶，图论问题大量出现，如汉密尔顿图问题、四色猜想等。

这些问题的出现进一步促进了图论的发展。

1847年，克希霍夫（Kirchhoff ）用图论分析电网络，这是图论最早应用于工程科学的一个例子。

随着计算机科学的迅猛发展，在现实生活中的许多问题，如交通网络问题，运输的优化问题，社会学中某类关系的研究，都可以用图论进行研究和处理。

图论在计算机领域中，诸如算法、语言、数据库、网络理论、数据结构、操作系统、人工智能等方面都有重大贡献。

本章主要介绍图论的基本概念、基本性质和一些典型应用。

7.1 图的基本概念7.1.1 图的基本概念1.图的定义图在现实生活中随处可见，如交通运输图、旅游图、流程图等。

此处我们只考虑由点和线所组成的图。

这种图能够描述现实世界的很多事情。

例如，用点表示球队，两队之间的连线代表二者之间进行比赛，这样，各支球队的比赛情况就可以用一个图清楚地表示出来。

到底什么是图呢？可用一句话概括：图是用点和线来刻划离散事物集合中的每对事物间以某种方式相联系的数学模型。

因为上述描述太过于抽象，难于理解，因此下面给出图作为代数结构的一个定义。

定义7.1.1 一个图（Graph ）是一个三元组〈)(G V ，)(G E ，G ϕ〉，其中)(G V 是一个非空的节点集合，)(G E 是有限的边集合，G ϕ是从边集合E 到点集合V 中的有序偶或无序偶的映射。

例7.1.1 图G =〈)(G V ，)(G E ，G ϕ〉，其中)(G V =},,,{d c b a ，)(G E =},,,,,{654321e e e e e e ，),()(1b a e G =ϕ，),()(2c a e G =ϕ，),()(3d b e G =ϕ，),()(4c b e G =ϕ，),()(5c d e G =ϕ，),()(6d a e G =ϕ。

第二章 图的连通性在第一章中已经定义连通图是任二顶点间都有路相连的图。

对于连通图，其连通的程度也有高有低。

例如，下列三个图都是连通图。

对于图G 1，删除一条边或一个顶点便可使其变得不连通；而对于图G 2，至少需要删除两条边才能使其不连通，也可以删除一个顶点使其不连通；对于图G 3，要破坏其连通性，则至少需要删除三条边或三个顶点。

本章主要讨论如何通过图的顶点集、边集和不交的路集合的结构性质来获知图的连通性程度。

通过研究割边和割点来刻画1连通图的特性；定义连通度和边连通度来度量连通图连通程度的高低；通过不交路结构和元素的共圈性质来反映图的2连通和k 连通性。

§2.1 割点和割边定义2.1.1 设)(G V v ∈，如果)()(G w v G w >−，则称v 为G 的一个割点。

（注：该定义与某些著作中的定义有所不同，主要是在环边的顶点是否算作割点上有区别）。

例如，下图中u , v 两点是其割点。

定理2.1.1 如果点v 是简单图G 的一个割点，则边集E (G)可划分为两个非空子集1E 和2E ，使得][1E G 和][2E G 恰好有一个公共顶点v 。

证明留作习题。

推论2.1.1 对连通图G ，顶点v 是G 的割点当且仅当v G −不连通。

定理2.1.2 设v 是树T 的顶点，则v 是T 的割点当且仅当1)(>v d 。

证明：必要性：设v 是T 的割点，下面用反证法证明1)(>v d 。

若0)(=v d ，则1K T ≅，显然v 不是割点。

若1)(=v d ，则v T −是有1)(−−v T ν条边的无圈图，故是树。

从而)(1)(T w v T w ==−。

因此v 不是割点。

以上均与条件矛盾。

充分性：设1)(>v d ，则v 至少有两个邻点u ,w 。

路uvw 是T 中一条),(w u 路。

因T 是树，uvw 是T 中唯一的),(w u 路，从而)(1)(T w v T w =>−。