离散数学第7章 图论 习题23页PPT

最短路径问题
实现方法：使用 队列数据结构， 将起始节点入队， 然后依次处理队 列中的每个节点， 直到找到目标节
点或队列为空
Dijkstra算法和Prim算法
Dijkstra算法：用于 求解单源最短路径问 题，通过不断更新最 短路径来寻找最短路 径。
Prim算法：用于求解 最小生成树问题，通过 不断寻找最小权重的边 来构建最小生成树。
图的矩阵表示
邻接矩阵的定义和性质
定义：邻接矩阵是一个n*n的矩阵，其 中n是图的顶点数，矩阵中的元素表示 图中顶点之间的连接关系。
性质：邻接矩阵中的元素只有0和1， 其中0表示两个顶点之间没有边相连， 1表示两个顶点之间有一条边相连。
应用：邻接矩阵可以用于表示图的连通 性、路径长度等信息，是图论中常用的 表示方法之一。
图像处理：优化图像分割， 提高图像质量
物流配送：优化配送路径， 降低配送成本
社交网络：优化社交网络 结构，提高用户活跃度
感谢您的观看
汇报人：PPT
数学：用于图论、组合数 学、代数拓扑等领域
物理学：用于量子力学、 统计力学等领域
生物学：用于蛋白质结构、 基因调控等领域
社会科学：用于社会网络 分析、经济模型等领域
图的基本概念
图的定义和表示方法
图的定义：由节点和边组成的数学结构，节点表示对象，边表示对象之间的关系
节点表示方法：用点或圆圈表示 边表示方法：用线或弧线表示 图的表示方法：可以用邻接矩阵、邻接表、关联矩阵等方式表示
顶点和边的基本概念
顶点：图中的基本元素，表示一个对象或事件 边：连接两个顶点的线，表示两个对象或事件之间的关系 度：一个顶点的度是指与其相连的边的数量 路径：从一个顶点到另一个顶点的边的序列 连通图：图中任意两个顶点之间都存在路径 强连通图：图中任意两个顶点之间都存在双向路径

结点的次数
2020/1/17
问题1：是否存在这种情况：25个人中，由于意见不同，每 个人恰好与其他5个人意见一致？
在建立一个图模型时，一个基本问题是决定这个图是什么 —— 什么是结点？什么是边？ 在这个问题里，我们用结点表示对象——人； 边通常表示两个结点间的关系——表示2个人意见一致。 也就是说，意见一致的2个人（结点）间存在一条边。
第七章 图论基础
Graphs
第一节 图的基本概念
2020/1/17
一个图G定义为一个三元组：G=<V, E, Φ>
V —— 非空有限集合，V中的元素称为结点 (node)或 顶点(vertex)
E —— 有限集合（可以为空），E中的元素称为边(edge)
Φ —— 从E到V的有序对或无序对的关联映射
以v为起始结点的弧的条数，称为出度(out-degree) （引出次数），记为d+(v)
以v为终结点的弧的条数，称为入度(in-degree)
（引入次数），记为d-(v)
v3
v的出度和入度的和，称为v的度数(degree)
（次数），记为d(v) = d+(v) + d-(v)
v1 (a) v2
结点的次数
(associative mapping)
v3
v3
v3
v1 (a) v2
v1
v2
(b)
v1
v2
(c)
图的基本概念
2020/1/17
图G=<V, E, Φ>中的每条边都与图中的无序对或有序对联系
若边e E 与无序对结点[va, vb]相联系，即Φ(e)= [va, vb] （va, vb V）则称e是无向边（或边、棱）

有环和平行边，u至多与其余n-1个结点中每一个 有一条边相连接，即deg(u)≤n-1，因此，⊿ (G) ＝maxdeg(u)≤n-1。
24
设G是一个n阶无向简单图，n是大于等于3的 奇数。证明图G与它的补图中度数为奇数的结 点个数相等。
证明： 因为G是n阶无向简单图，且n是大于等于3的奇数，
故无向图的结点数为奇数，则所对应的n阶完全图 中每个结点的度数为n-1即为偶数， 利用奇数+奇数=偶数，偶数+偶数=偶数，所以， 在G中结点度数为奇数的结点，在其补图中的度 数也应为奇数，故G和其补图的奇数结点个数也 是相同的。
25
P286 1、在无向图G中，从结点u到结点v有一条长度为 偶数的通路，从结点u到结点v又有一条长度为奇 数的通路，则在G中必有一条长度为奇数的回路。
(4) D中长度为4的回路有多少条？ 答： 长度为4的回路为11条。
(5) D中长度4的通路有多少条？其中有几条是回路？ 答：长度4的通路88条，其中22条为回路。
(6) 写出D的可达矩阵。 44的全1矩阵。
17
简单无向图 G 必有2结点同度数。
证: 令 G={v1,…,vn}，
(2) n阶非连通的简单图的边数最多可为n-1阶连通图 加上一个孤立点，所以边数为(n-1)(n-2)/2，最少为0。
20
一个图如果同构于它的补图，则该图称为自补图。
1)一个图是自补图，其对应的完全图的边数必为偶数; 2)证明：若n阶无向简单图是自补图，则n=4k或n=4k+1
（k为正整数）。 解：
平面图的对偶图
无向树及其性质 根树及其应用
地图着色与平 面图着色
3
4
一、无向图与有向图

例：把下面的m叉树改写为二叉树。
14
第七章 图论
信 息 科 学 与 工 程 学 院
练习：把下面的有序树改写为二叉树。
。 。 。。 。 。。 。 。 。 知识点提示：
。 。。
。 。 。
。
课下自学
此方法可推广至有序森林到二叉树的转换。 此方法具有可逆性。
15
第七章 图论
信 息 科 学 与 工 程 学 院
给定一棵2叉树T，设它有t片树叶。设v为T的一个分枝点， 则v至少有一个儿子，最多有两个儿子。若v有两个儿 子，在由v引出的两条边上，左边的标上0，右边的标 上1；若v有一个儿子，在由v引出的边上可标上0，也
可标上1。设vi为T的任一片树叶，从树根到vi的通路
上各边的标号组成的0，1串组成的符号串放在vi处，t 片树叶处的t个符号串组成的集合为一个二元前缀码。
定义7-8.5
在根树中， 科 一个结点的通路长度为从树根到此结点的通路中的边 学 数。 与 分枝点的通路长度称为内部通路长度。 树叶的通路长度称为外部通路长度。
工 程 学 院
。 。 。 。。 A 。 。 。。
18
第七章 图论
信 息 科
定理7-8.2
若完全二叉树有n个分枝点，且内部通路长度总和为L，外 部通路长度总和为E，则 E=L+2n。 证明：
学 与 工 程 学 院
对分枝点数目n进行归纳证明。
。
当n=1时，如右图所示，
L=0， E=2，
。
。
显然， E=L+2n成立。
19
第七章 图论
信 息 科 学
定理7-8.2 若完全二叉树有n个分枝点，且内部通路长度总 和为L，外部通路长度总和为E，则 E=L+2n。 证明：

图7-1.9 不同构的图
作业
P279 (1) (4)
如图7-1.6中的(a)和(b)互为补图。
[定义] 子图(subgraph) 设图G=<V,E>，如果有图G’= <V’,E’>，若有 V’ V ，E’ E，则称图G’是图G的子图。 [定义] 生成子图(spanning subgraph) 如果图G的子图G’包含G的所有结点,则称该图 G’为G的生成子图。如图7-1.8中G'和G"都是 G的生成子图。
[定义] 相对于图G的补图 设图G'＝〈V',E'〉是图G＝〈V,E〉的子图,若 给定另外一个图G"＝〈V",E"〉使得E"＝EE', 且 V" 中仅包含 E"的边所关联的结点。则 称G"是子图G'的相对于图G的补图。
图7-1.7 (c )为(b)相对于(a)的补图
如图 7-1.7 中的图 (c) 是图 (b) 相对于图 (a) 的补 图。而图 (b) 不是图 (c) 相对于图 (a) 的补图 , 因为图(b)中有结点c。在上面的一些基本概 念中,一个图由一个图形表示,由于图形的结 点的位置和连线长度都可任意选择 , 故一个 图的图形表示并不是唯一的。下面我们讨 论图的同构的概念。
表7-1.1
结 点 出 度 入 度
a 2 0
b 1 1
c 0 2
d 1 1
结 点 出 度
入 度
v1 1 1
v2 0 2
v3 2 0
v4 1 1
分析本例还可以知道 , 此两图结点的度数也 分别对应相等,如表7-1.1所示。
两图同构的一些必要条件: 1.结点数目相等; 3.边数相等; 3.度数相等的结点数目相等。 需要指出的是这几个条件不是两个图同构的 充分条件,例如图7-1.9中的(a)和(b)满足上 述的三个条件,但此两个图并不同构。

4.无向图的连通性
若无向图G中任何两顶点都连通,则称G是连通图.
对于任意的无向图G.设V1,V2,…,Vk是顶点之间连通关系的 等价类,则称他们的导出子图为G的连通分支.用p(G)表示G 的连通分支数.
V1 e1
e2 e3
V3
e4 V2
V4
a
de
h
i
b
c
f
g
5.有向图的连通性
若略去有向图D中各边的键头,所得无向图是无向连通图,则 称D是弱连通图(或称D是连通图).
(2) mij d (vi )(i 1,2,..., n)
j 1
mn
nm
n
(3) mij mij d(vi ) 2m
j1 i1
i1 j1
i 1
m
(4) mij 0 vi是孤立点 j 1
(5)若第j列与第k列相同, 则说明e j与ek为平行边.
2.有向图的关联矩阵
设有向图D=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em} 1, vi为ej的始点
e1,e2,e3},{e1,e2,
e2
e4},{e9}等边割集 ,e9是桥.
e3 V4
e5 e6
V5 e4
V6
e9
V7
7.3 图的矩阵表示
1.无向图的关联矩阵
设无向图G=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em}
令mij为顶点vi与ej的关联次数, 则称(mij)n×m为G的关联矩阵.记为M(G)
若Γ 满足:vi-1,vi为ei的端点(若G为有向图,vi-1是ei的始 点,vi是ei的终点)i=1,2,…,k,则称Γ 为G中通路,v0,vk分 别称为通路的始点和终点,Γ 中边的数目k称为通路长度.

科学中的许多问题。
03
例如，利用图论中的最短路径算法和最小生成树算法
等，可以优化网络通信和数据存储等问题。
运筹学中的应用
01
运筹学是一门应用数学学科， 主要研究如何在有限资源下做 出最优决策，离散数学在运筹 学中有着广泛的应用。
02
利用离散数学中的线性规划、 整数规划和非线性规划等理论 ，可以解决运筹学中的许多问 题。
并集是将两个集合中的所有元素合 并在一起，形成一个新的集合。
详细描述
例如，{1, 2, 3}和{2, 3, 4}的并集是 {1, 2, 3, 4}。
总结词
补集是取一个集合中除了某个子集 以外的所有元素组成的集合。
详细描述
例如，对于集合{1, 2, 3}，{1, 2}的 补集是{3}。
集合的基数
总结词
）的数学分支。
离散数学的学科特点
03
离散数学主要研究对象的结构、性质和关系，强调推
理和证明的方法。
离散数学的应用领域
计算机科学
01
离散数学是计重要的工具和方法。
通信工程
02
离散数学在通信工程中广泛应用于编码理论、密码学、信道容
量估计等领域。
集合的基数是指集合中元素的数量。
详细描述
例如，集合{1, 2, 3}的基数是3，即它包含三个元素。
03 图论
图的基本概念
顶点
图中的点称为顶点或节点。
边
连接两个顶点的线段称为边。
无向图
边没有方向，即连接两个顶点的线段可以是双向 的。
有向图
边有方向，即连接两个顶点的线段只能是从一个顶 点指向另一个顶点。
研究模态算子（如necessity、possibility）的语义和语法。

3 v1e1v2e5v5e6v4e4v2e5v5e7v6
…………
初级通路 简单通路 复杂通路
第38页/共94页
例1、(2)
图(2)中过v2的回路 (从 v2 到 v2 )有：
1 v2e4v4e3v3e2v2
长度3
2 v2e5v5e6v4e3v3e2v2
长度4
3 v2e4v4e3v3e2v2e5v5e6v4e3v3e2v2 长度7
第34页/共94页
一、通路，回路。 2、简单通路，简单回路。 简单通路 (迹) 简单回路 (闭迹) 复杂通路 (回路)
第35页/共94页
一、通路，回路。 3、初级通路，初级回路。 初级通路 (路径) 初级回路 (圈)
初级通路 (回路) 简单通路 (回路)，
但反之不真。
4、通路，回路的长度—— 中边的数目。
补图的概念， 5、图的同构的定义。
第4页/共94页
一、图的概念。 1、定义。
无序积 A & B (a,b) a A b B
无向图 G V , E
E V &V ， E 中元素为无向边，简称边。
有向图 D V, E
E V V ， E 中元素为有向边，简称边。
第5页/共94页
一、图的概念。 1、定义。
2、握手定理。
定理1： 设图 G V , E 为无向图或有向图，
V v1,v1,
则
,vn，E m ( m为边数)，
n
d (vi ) 2m
i 1
第20页/共94页
n
2、握手定理 d (vi ) 2m i 1
推论：任何图中，度为奇数的顶点个数为偶数。
定理2： 设D V, E 为有向图，
第36页/共94页

第七章 图论 7.1 图的基本概念
完全图：任意两个不同的结点都是邻接的简单图称为
完全图。n个结点的无向完全图记为Kn。
图7.1.5给出了K3和K4。从图中可以看出K3有３条边，
K4有６条边。容易证明Kn有条边。
n(n 1) 2
图7.1.5K3与K4示意图
图7.1.6
第七章 图论 7.1 图的基本概念
一个图G可用一个图形来表示且表示是不唯一的。
第七章 图论 7.1 图的基本概念
【例7.1.2】设G=〈V(G),E(G)〉,其中
V(G)={a,b,c,d},E(G)={e1,e2,e3,e4,e5,e6,e7},e1=(a,b), e2=(a,c),e3=(b,d),e4=(b,c),e5=(d,c),e6=(a,d),e7=(b,b) 。
1)若e1，e2，…，ek都不相同， 则称路μ为迹；
2)若v0，v1，…，vk都不相同， 则称路μ为通路；
3)长度大于２的闭的通路（即 除v0＝vk外，其余结点均不相同的 路）μ称作圈。
图7.1.1
第七章 图论
7.2 路与回路
例如在图7.2.1中，有连接v5 到v3的路v5e8v4e5v2e6v5e7v3，这 也是一条迹；路v1e1v2e3v3是一 条通路；路v1e1v2e3v3e4v2e1v1是 一条回路，但不是圈；路 v1e1v2e3v3e2v1是一条回路，也是 圈。
定 义 7.2.1 给 定 图 G ＝ 〈V,E〉, 设 v0,v1,…,vk∈V ， e1 ， e2，…，ek∈E，其中ei是关联于结点vi-1和vi的边，称 交替序列v0e1v1e2…ekvk为连接v0到vk的路，v0和vk分别 称为路的起点与终点。路中边的数目k称作路的长度。 当v0=vk时,这条路称为回路。

2018/7/1 数学学院 34--6
例2
在图 a 给出了一个偶图，它的互补结点子集为 V1和V2， 图b是从V1到V2的一个匹配。 图c中的偶图虽然满足条件|V1|≤|V2|，但是却 没有匹配。
2018/7/1 数学学院 34--7
霍尔定理
定理 11.4.2 在偶图 G ＝ <V1,E,V2> 中存在从 V1 到V2的匹配，当且仅当V1中任意k个结点至少与
组。
V2＝{s1,s2,s3,s4,s5}
以 V 1 ， V 2 为互补结点子集，若 s i 在 c j 中，则
(si,cj)在E中。
2018/7/1
数学学院
34--11
1) G1＝<V1,E1,V2>如图a所示。
在G1中，V1中的每个结点至少关联2条边，而 V2中的每个结点至多关联2条边，因此满足t条件， 故存在从V1到V2的匹配。事实上，选s2为物理组 的组长，选s3为化学组的组长，选s5为生物组的 组长，它们对应的匹配如,…,|V1|。
这个定理中的条件通常称为相异性条件。 判断一个偶图是否满足相异性条件通常比较复 杂，下面给出一个判断偶图是否存在匹配的一 个充分条件，对于任何偶图来说，都很容易确
定这些条件。因此，在考察相异性条件之前，
应首先试用这个充分条件。
2018/7/1 数学学院 34--8
2018/7/1 数学学院 34--3
充分性： 设G中每条回路的长度均为偶数，若G是 连通图，任选v0∈V，定义V的两个子集如下： V1＝{vi|d(v0,vi)为偶数} V2＝V-V1 现证明 V1中任两结点间无边存在。假若存在 一条边 (vi,vj)∈E，其中 vi,vj∈V1 ，则由 v0 到 vi 间的短程线（长度为偶数）以及边(vi,vj)，再加 上 vj 到 v0间的短程线（长度为偶数）所组成的回 路的长度为奇数，与假设矛盾。 同理可证V2中任两结点间无边存在。