图论及其应用讲义ppt6

例6 通信网络中的组播树 在单播模型中，数据包通过网络沿着单一路径从源主机向
目标主机传递，但在组播模型中，组播源向某一组地址传递数 据包，而这一地址却代表一个主机组。为了向所有接收者传 递数据，一般采用组播分布树描述IP组播在网络里经过的路 径。组播分布树有四种基本类型：泛洪法、有源树、有核树 和Steiner树 。
证明：“必要性”
若不然，设P1与P2是连接u与v的两条不同的路。则
9
由这两条路的全部或部分将构成一个圈，这与G是 树相矛盾。
“充分性” 首先，因G的任意两点均由唯一路相连，所以G是 连通的。 其次，若G中存在圈，则在圈中任取点u与v，可得 到连接u与v的两条不同的路，与条件矛盾。 定理3 设T是(n, m)树，则：
k
m(G) m(Ti ) n k i 1
定理4 每个n阶连通图的边数至少为n-1.
证明：如果n阶连通图没有一度顶点，那么由握手定理
有： m(G) 1
d (v) n
2 vV (G )
13
如果G有一度顶点。对顶点数作数学归纳。
当n=1时，结论显然
设当n=k时，结论成立。 当n=k+1时，设u是G的一度顶点，则G-u为具有k个顶
定理5 任意树T的两个不邻接顶点之间添加一条边后， 可以得到唯一圈。
证明：设u与v是树T的任意两个不邻接顶点，由定理2 知：有唯一路P连接u与v.于是P∪｛u v｝是一个圈。 显然，由P的唯一性也就决定了P∪｛u v｝的唯一性。
例9 设G是树且Δ≧k,则G至少有k个一度顶点。 证明：若不然，设G有n个顶点，至多k-1个一度顶点， 由于Δ≧k，于是，由握手定理得：
根树
5
实际上，根树是许多问题的模型，如社会结构，

∴
c' (v) c(v)
v V v V
，

这与C为最优矛盾。

图论及其应用
6
6.1 边色数


定理6.1 设G为偶图，则 = 。 证明： （Wilson）对 进行归纳。当 = 1 时显然成立。假设
对 < k( 2) 都成立，而 (G)= k 。任取G的一边 e = uv ， 考虑 G’ = G - e 。

(a) 利用Vizing定理证明：(G×K2）= (G×K2) 。 (b) 试证：若H是非平凡的，且(H) = (H)，则(G×H) = (G×H)。

6.2.7 叙述求简单图G的正常(+1)-边着色的好算法。 6.2.8*证明 ≥2的简单图G有一(-1)-边着色，使得所有-1种色在每个顶点上都表现 6.2.9 设简单图G有割点，则 = + 1 。
图论及其应用
11
6.2 Vizing定理——习题





6.2.1* 找出适当的边着色以证明(K2N-1) = (K2N) = 2n-1 。 6.2.2 为奇数的非空正则简单图G有 = + 1 。 6.2.3(a) 设简单图G中 = 2n+1且 >n ，则 = +1 ； (b) 利用(a)证明： ① 若G是从有偶数个顶点的简单图中剖分一条边所得的图，则 = +1 ； ② 若G是从有奇数个顶点的简单k正则图中删去少于k/2条边所得的图，则=+1 6.2.4 (a) 证明： 任一无环图G都有-正则无环母图。（注：不一定为生成母图） (b) 利用(a)及习题5.2.3(b)证明：若G 是无环图且 是偶数，则 3 /2。 6.2.5 称G为唯一k-边可着色的，如果G的任意两个k-边着色都导致E有相同的划分。 证明：每个唯一3-边可着色的3-正则图都是Hamilton 图 。 6.2.6 简单图的积图是指顶点集为V(G)×V(H)的简单图G×H，其中 (u,v)与(u’,v’)相邻 u = u’且v’ E(H)； 或 v = v’且uu’ E(G)

χ（G）表示。若χ（G）=k，就称G是k-点可 色图。
顶点染色
定理：对于任何一个图χ（G）≤ω（G）。 ω（G）为图G的团数，用来描述χ（G）的下 界，其中ω（G）=max{k|Kk属于G}。
顶点染色
给定图G=（V，E）的一个k-点染色。用Vi表示G中染以 第i色的顶点集合（i=1,2，…，k），则每个Vi都是G 的独立集。因而G的每一个K-点染色对应V(G)的一个划 分[V1,V2,…,Vk]，其中每一个Vi是一个独立集。反之 ，给出V(G)的这样一个划分（V1,V2,…,Vk），其中每 一个Vi均是独立集（1≤i≤k），则相应得到G的一个k点染色，称V(G)的这样一个划分为G的一个色划分，每 一个Vi称为色类。因此，G的色数χ(G)就是使这种划 分成为可能最小自然数k。
推论：若G是p(G) 3且g(G) 3的平图，则 q(G) g(G) ( p(G) 2)。 g(G) 2
平面图的性质
推论：任何一个简单平面图G，有 q(G)≤3p(G)-6
推论：设G是简单平面图，则δ(G)≥6.
定理：仅存在5种正多面体，即正四面体、正 方体、正八面体、正十二面体和正二十面体。
定理：每一个平面的色数不超过5
边染色
定义：无环图G的一个正常染色k-边染色（简 称k-边染色）是指一个映射φ：E(G)→{1,2， …，k}，使对G中任意两条相邻的边e1和e2，有 φ(e1)≠φ(e2)。若G有一个正常k-边染色，则 称G是k-边染色的。G的边色数是指G为k-边染 色的最小整数k的值，记为
χ'(G)。若χ'(G)=k，则称G是k-边可色的。
边染色
设G有一个正常k-边染色，置Ei为G中所有染 以第i种颜色的边的全体，则E1，E2，…，Ek 是G的k个边不相交的对集，并且

第19页/共93页
• 完全图：一个（n,m）图G，其n个结点中每个结点均与其它n-1个结点相邻接，记为Kn。 • 无向完全图：m=n(n-1)/2 • 有向完全图：m=n(n-1) • 举例说明以上几种图。
第20页/共93页
定义补图
• 设图G=<V,E> ， G’=<V,E’> ，若G’’=<V,E∪E’> 是完全图，且E∩E’= 空集，则称G’是G的补图。 • 事实上，G与G’互为补图。
正则图
• 所有结点均有相同次数d的图称为d次正则图。 • 如4阶的完全图是3次正则图，是对角线相连的四边形。 • 试画出两个2次正则图。
第27页/共93页
两图同构需满足的条件
• 若两个图同构，必须满足下列条件： （1）结点个数相同 （2）边数相同 （3）次数相同的结点个数相同
• 例子
第28页/共93页
• 图是人们日常生活中常见的一种信息载体，其突出的特点是直观、形象。图论，顾 名思义是运用数学手段研究图的性质的理论，但这里的图不是平面坐标系中的函数， 而是由一些点和连接这些点的线组成的结构 。
第8页/共93页
• 在图形中，只关心点与点之间是否有连线，而不关心点具体代表哪些对象，也不关 心连线的长短曲直，这就是图的概念。
定义图的子图
• 子图：设G=<V,E> ， G’=<V’,E’> ，若V’是V的子集， E’是E的子集，则 G’是G的子图。 • 真子图：若V’是V的子集，E’是E的真子集。 • 生成子图：V’=V，E’是E的子集。 • 举例说明一个图的子图。
第18页/共93页
定义（n,m）图
• (n,m)图：由n个结点，m条边组成的图。 • 零图：m=0。即（n,0）图，有n个孤立点。 • 平凡图：n=1,m=0。即只有一个孤立点。

学习方法
目的明确
态度端正 理论和实践相结合
充分利用资源
逐步实现从知识到能力到素质的深化和
升华
课程考核
平时成绩 （30%-40%）
闭卷考试 （60%-70%）
图论模型
为了抽象和简化现实世界，常建立数学模型。图是关 系的数学表示，为了深刻理解事物之间的联系，图 是常用的数学模型。 (1) 化学中的图论模型 19世纪，化学家凯莱用图论研究简单烃——即碳氢 化合物 用点抽象分子式中的碳原子和氢原子，用边抽象原子间 的化学键。
E={w1r1, w1r2, w2r2, w2r3, w2r4, w3r3, w3r5}代表每个仓库和每个 零售店间的关联。则图模型图形为： w1 w2 w3
r1
r2
r3
r4
r5
29
(3) 最短航线问题 用点表示城市，两点连线当且仅当两城市有航线。为了 求出两城市间最短航线，需要在线的旁边注明距离值。 例如：令V={a, b, c, d, e}代表5个城市} E={a b, ad, b c , be, de}代表城市间的直达航线 则航线图的图形为： a 320 500 d 370 b 140 430 e c

图论学科简介 （2）
19世纪末期，图论应用于电网络方程组
和有机化学中的分子结构 20世纪中叶，由于计算机的发展，图论 用来求解生产管理、军事、交通运输、 计算机和网络通信等领域中的离散性问 题 物理学、化学、运筹学、计算机科学、 电子学、信息论、控制论、网络理论、 社会科学、管理科学等领域应用
七桥问题
近代图论的历史可追溯到18世纪的七桥问题:
穿过Kö nigsberg城的七座桥，要求每座桥通过 一次且仅通过一次。

W (P) =
e∈ ( P) W (P
∑W(e)
则称W 为路径P(u, v) 的权或长度(距离). 长度(距离) 则称 (P)为路径 为路径 定义2：若P0 (u, v) 是G 中连接u, v的路径 且对任 定义 ： 中连接 的路径, 的路径 意在G 中连接u, 的路径 的路径P 意在 中连接 v的路径 (u, v)都有 都有 W(P0)≤W(P), ≤ 则称P 中连接u, 的最短路. 则称 0 (u, v) 是G 中连接 v的最短路
解:
表示设备在第i 年年初的购买费, 设bi 表示设备在第 年年初的购买费 ci 表示设备使用 年后的维修费 表示设备使用i 年后的维修费, V={v1, v2, … , v6},点vi表示第 年年 表示第i 点 表示第 初购进一台新设备,虚设一个点 虚设一个点v6表 初购进一台新设备 虚设一个点 表 示第5年年底 年年底. 示第 年年底 E ={vivj | 1≤i＜j≤6}. ＜
如果E的每一条边都是无向边 则称G为 如果 的每一条边都是无向边, 则称 为无向 的每一条边都是无向边 如图1) 如果E的每一条边都是有向边 1); 的每一条边都是有向边, 图(如图1) 如果 的每一条边都是有向边 则称 G为有向图(如图2) 否则 称G为混合图 2); 为有向图(如图2) 否则, 为混合图.
图论在数学建模中的应用
• • • • 第一部分 第二部分 第三部分 第四部分概念
图论中的“ 图论中的“图”并不是通常意义下的几何图 形或物体的形状图, 形或物体的形状图, 而是以一种抽象的形式来表 达一些确定的事物之间的联系的一个数学系统. 达一些确定的事物之间的联系的一个数学系统. 称为一个图, 定义1 :一个有序二元组 一个有序二元组( 定义1 :一个有序二元组(V, E ) 称为一个图, 记为G = (V, E ), 其中 的顶点集, 其元素称为顶点, ① V 称为G的顶点集, V≠φ, 其元素称为顶点, 简称点; 简称点; 的边集, 其元素称为边, ② E 称为G的边集, 其元素称为边, 它联结V 中的两个点, 如果这两个点是无序的, 中的两个点, 如果这两个点是无序的, 则称该边 为无向边, 否则, 称为有向边. 为无向边, 否则, 称为有向边.

添加副标题
图论的介绍
汇报人：
目录
PART One
添加目录标题
PART Three
图论的应用领域
PART Two
图论的基本概念
PART Four
图论的基本问题
PART Five
图论的算法和数据 结构
PART Six
图论的扩展知识
单击添加章节标题
图论的基本概念
图论的发展历程
18世纪末，欧拉提出“七桥问题”，开启了图论的先河
匹配问题
匹配问题定义：在图论中，匹配问 题是指在图中找到一组边，使得每 个顶点恰好有一条边。
最小匹配问题：在图中找到一组边， 使得边的数量最少。
添加标题
添加标题
添加标题
添加标题
最大匹配问题：在图中找到一组边， 使得边的数量最多。
完美匹配问题：在图中找到一组边， 使得每个顶点恰好有一条边，并且 边的数量最多。
图论的扩展知识
欧拉路径和欧拉回路
欧拉路径：通过图中所有边且仅通过一次的路径
欧拉回路：通过图中所有边且仅通过一次的回路
欧拉定理：一个无向图存在欧拉回路当且仅当每个顶点的度数都是偶数
应用：欧拉路径和欧拉回路在计算机科学、数学、物理等领域有广泛应用，如电路设计、网络 拓扑、图论算法等
哈密顿路径和哈密顿回路
应用
生物技术：图 论在生物工程、 生物制造和生 物能源等领域
的应用
图论的发展趋势和未来展望
应用领域：图 论在计算机科 学、物理学、 生物学等领域 的应用越来越
广泛
研究方向：图 论在算法设计、 网络优化、数 据挖掘等领域 的研究不断深
入
技术发展：图 论与机器学习、 深度学习等技 术的结合越来

4
5
4 9 8
v1
v3
2
v6
[8,v2]
v8
5 33
1
[2,v1]
v4
v7
[10,v4]
33
Dijkstra算法示例1
3）迭代计算(c)—更新与永久标号节点v2相连的节 (d2+w25=3+7=)10< ∞ (=d5) 点的临时标号。
[3,v1]
v2
[0,-]
7
v5
[10,v2]
2 [+∞,v1] 6
v4
v7
[+∞,v1]
22
Dijkstra算法示例1
2）迭代计算(a)—从临时标号中找到距离上界dk最 小的节点v4，d4=min{dk}，将其变换为永久编号。
[3,v1] [+∞,v1]
v2
[0,-]
7
v5
2 [+∞,v1] 6 1 2 [+∞,v1]
3
5 2 [5,v1]
4
5
4 9 8
v1
v3

最小树问题不一定有唯一解。
10
10
最小支撑树问题的解法

破圈法 算法


初始化 将图G的边按权值从大到小的次序排列，从 原图开始迭代； 迭代


第1步(删边) 从排列中顺序选择一条与图中剩余边构成圈 的边，则将此边从图中删除，进入第2步(结束判断)； 第2步(结束判断) 若图中剩下n-1条边，则已经得到最小支 撑树；否则，进入下一轮迭代，返回第1步(加边)；

柯尼斯堡七桥问题

柯尼斯堡市区横跨普雷格尔河两岸，在河中心有两 个小岛。小岛的两岸共有七座桥将岛与岛、岛与河 岸连接起来。一个人怎样才能一次走遍七座桥，每 座桥只走过一次，并最后回到出发点？

-
6
8.判别一个二部图中存在完备匹配的相异性条件和t条 件分别是充要条件和充分条件,但t条件对任一二部图能 极容易地进行检验,因而在考虑用较为复杂的相异性条 件之前,可首先用t条件判断,如果t条件不成立,再用相异 性条件判断。
9.图是点（边或面）k-可着色的，是指能用k种颜色给 图的结点（边或面）着色，但k不一定是最少的颜色数。 图是点（边或面）k-色的，是指最少要用k种颜色绘图 的结点（边或面）着色。平面图的面着色问题一般化 为对其偶图的点着色问题。Welch-Powell算法是近似 算法，它给出的结点着色的颜色数不一定是最少的， 而是较少的。
6.掌握最小点覆盖、最小边覆盖、最大点独立集、最 大边独立集（匹配）、最大匹配、完美匹配、完备匹 配、可增广路径等概念，能够利用相异性条件和t条件
-
2
判定二部图中是否存在完备匹配，了解可增广路径求 完备匹配的方法和思想。
7.掌握结点着色、边着色、面着色等概念及有关性质， 能够用Welch—power算法确定一个使图的颜色数尽可 能少的结点着色。
数目。
3.掌握求图中某个结点到其他任一结点的最短路径的 Dijkstra算法，以及求图中任意两个结点的最短路径的
-
1
Warshsll算法。
4.掌握欧拉图和哈密尔顿图的概念及其判别方法，能 够利用fleury
算法求欧拉回路，了解邮路问题，能够用近邻法求哈 密尔顿回路。
5.掌握平面图、面、边界、极大平面图、同胚等概念 及有关性质，能够判定一个图是否为平面图。
-
7
§6.3基本题
§6.3.1选择题
1.设D=<V，E>为有向图，则有（
A. E ∈ V*V
B.EV*V