离散数学 通路、回路与图的连通性43页PPT

(1) 若i(1il), vi1, vi是ei的端点(对于有向图, 要求vi1是始点,
vi是终点), 则称为通路, v0是通路的起点, vl是通路的终点, l为通路的长度. 又若v0=vl，则称为回路.
(2) 若通路(回路)中所有顶点(对于回路, 除v0=vl)各异，则称为 初级通路(初级回路).初级通路又称作路径, 初级回路又称 作圈.
32
通路与回路(续)
定理 在n阶图G中，若从顶点u到v（uv）存在通 路，则从u到v存在长度小于等于n1的通路. 推论 在n阶图G中，若从顶点u到v（uv）存在通 路，则从u到v存在长度小于等于n1的初级通路.
定理 在一个n阶图G中，若存在v到自身的回路，则 一定存在v到自身长度小于等于n的回路. 推论 在一个n阶图G中，若存在v到自身的简单回 路，则存在v到自身长度小于等于n的初级回路.
D
D[{e1,e3}]
D[{v1,v2}]
26
补图
定义 设G=<V,E>为n阶无向简单图，以V为顶点集, 所有使G成为完全图Kn的添加边组成的集合为边集 的图，称为G的补图，记作 G . 若G G , 则称G是自补图.
例 对K4的所有非同构子图, 指出互为补图的每一对 子图, 并指出哪些是自补图.
图论
1
图论部分
第5章 图的基本概念 第6章 特殊的图 第7章 树
2
第5章 图的基本概念
5.1 无向图及有向图 5.2 通路, 回路和图的连通性 5.3 图的矩阵表示 5.4 最短路径, 关键路径和着色
3
5.1 无向图及有向图
▪ 无向图与有向图 ▪ 顶点的度数 ▪ 握手定理 ▪ 简单图 ▪ 完全图 ▪ 子图 ▪ 补图
27
5.2 通路、回路、图的连通性

一个顶点是可达的； 有向图是弱连通的，有向边被看作无向边时是连通的。
连通图 不连通图 强连通图 单向ቤተ መጻሕፍቲ ባይዱ通图 弱连通图
第18讲 路径、回路及连通性
-9-
连通分支
定义：在无向图G中，若至少存在两个节点是不可达的，则 G是不连通的；如果G是不连通的，G’是G的子图，G’是连 通的，并且不存在G的真子图G’’，使G’’是连通的，且G’’ 以G’为真子图， 则称G’是G的一个极大连通子图，或称是 G的一个连通分支
PowerPoint Template_Sub
1 图的基础知识 2 路径、回路及连通性 3 欧拉图与哈密顿图 4 图的矩阵表示
《离散数学》第18讲 路径、回路及连通性 Page 112 to 117
拟路径及长度
定义：图G的顶点v1到顶点vl的拟路径是指以下顶点与边的序列： v1 , e1, v2, e2, v3, …, vl-1, el-1, vl v1 ,v2 ,v3 ,… ,vl-1 ,vl为G的顶点，e1 ,e2 ,… ,el-1 为G的边 ei( i= 1,2, … ,l-1 )以vi及vi+1为端点 对有向图G，ei以vi为起点，以vi+1为终点
称有向图G是单向连通的，如果G的任何两个顶点中， 至少从一个顶点到另一个顶点是可达的；
称有向图G是弱连通的，如果G的有向边被看作无向 边时是连通的。
第18讲 路径、回路及连通性
-8-
连通
u到v是可达的，如果有一条u到v的路径，或者u =v。 无向图是连通的，任何两个顶点u到v都是可达的。 有向图是强连通，任何两个顶点都是相互可达的； 有向图是单向连通的，任何两个顶点中，至少从一个顶点到另
然后重复上述讨论，直至没有边重复出现、没有顶点重 复出现，从而得到从u到v的路径和长度不超过n – 1的通 路。

第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。即只有一个孤立点。

connected graph
边割集
若存在边集子集E' E, 使G删除E'(将E'中的边从G中全删除)后, 所得子图的连通分支数与G的连通分支数 满足p(G-E')＞p(G), 而删除E'的任何真子集E''后,p(G-E'')＝p(G), 则称E'是G的一个边割集. 若边割集中只有一条边e,则称e为割边或桥. 注：完全图没有割边和割点.
当v0＝vl时,此通路称为回路.
connected graph
简单通路或迹
若Γ中的所有边e1,e2,···,el互不相同, 则称Γ为简单通路或一条迹. 若回路中的所有边互不相同,称此回 路为简单回路或一条闭迹.
connected graph
初级通路
若通路的所有顶点v0,v1···,vl互不相 同(从而所有边互不相同),则称此通 路为初级通路或一条路径. 若回路中,除v0＝vl外,其余顶点各不 相同,所有边也各不相同,则称此回 路为初级回路或圈. 长度为奇(偶)数的圈称为奇(偶)圈
通路
connected graph
给定图G＝<V,E>.
设G中顶点和边的交替序列为
Γ＝v0e1v1e2…elvl,若Γ满足如下条件: vi-1和vi是ei的端点(在G是有向图时,要求vi-1是ei 的始点,vi是ei的终点),i＝1,2,…,l,则称Γ为顶点v0 到vl的通路. v0和vl分别称为此通路的起点和终点,Γ中边的数 目l称为Γ的长度.
connected graph
有向图的连通性
易见:强连通性 单向连通性 弱连通性; 但反之 不真.反例如下:
a
c
a
强连通
d

• 相关点
– 长度为0的通路由单个顶点组成。 – 不必区分多重边时，可以用相应顶点的序列表示通路。 – 回路：起点与终点相同，长度大于0。 – 简单通路： 边不重复，即， i, j, i j ei ej
通路（举例）
a
b
c
d
e
f
• 简单通路：a, d, c, f, e。 长度为4。 • 通路：a, b, e, d, a, b。 长度为5。 • 回路：b, c, f, e, b。长度为4。 • 不是通路：d, e, c, b。
路)
• u,v VD,均存在 (u,v)-有向通路和(v,u)-有向通路，则D
称为强连通有u向图。 (见下左u 图)
u
v
v
v
强连通的充分必要条件
• 有向图D是强连通的当且仅当D中的所有顶点在同
一个有向回路上。
– 证明： 显然 设VD={v1,v2,…,vn}，令 i是vi到vi+1的有向通路 (i=1,…,n-1)，令 n是vn到v1的有向通路，则 1，
假设这样的公共点中距离v最近的
是x(不妨假设它在P上)，则Q+wv 边以及P上的ux-段+P’上的xv-段是u
u,v之间两条中间点不相交的通路。
P
x
v
w Q
连通性的一般性质
• Menger定理（Whitney定理的推广）
– 图G是k-连通图 当且仅当 G中任意两点被至少k条除端
点外顶点不相交的路径所连接。
则称v是割
割点
(注意：只需考虑割点所在的连通分支，以下讨论不妨只 考虑连通图)
关于割点的三个等价命题
• 对于连通图，以下三个命题等价：
(1) v是割点。 (2) 存在V-{v}的划分{V1, V2}, 使 u∈V1, w∈V2, uw-通路均包含v。 (3) 存在顶点u,w(u≠v, w≠v)，使得任意的uw-通路均包含v。 – 证明： (1) (2): ∵v是割点，G-v至少存在两个连通分支，设其中一个的

一个简单命题.
13
联结词与复合命题(续)
3.析取式与析取联结词“∨” 定义 设 p,q为二命题，复合命题“p或q”称作p与q 的析取式，记作p∨q. ∨称作析取联结词，并规 定p∨q为假当且仅当p与q同时为假.
例 将下列命题符号化 (1) 2或4是素数. (2) 2或3是素数. (3) 4或6是素数. (4) 小元元只能拿一个苹果或一个梨. (5) 王晓红生于1975年或1976年.
15
联结词与复合命题(续)
4.蕴涵式与蕴涵联结词“” 定义 设 p,q为二命题，复合命题 “如果p,则q” 称 作p与q的蕴涵式，记作pq，并称p是蕴涵式的 前件，q为蕴涵式的后件. 称作蕴涵联结词，并 规定，pq为假当且仅当 p 为真 q 为假.
16
联结词与复合命题(续)
pq 的逻辑关系：q 为 p 的必要条件 “如果 p，则 q ” 的不同表述法很多：
19
例 求下列复合命题的真值 (1) 2 + 2 ＝ 4 当且仅当 3 + 3 ＝ 6. (2) 2 + 2 ＝ 4 当且仅当 3 是偶数. (3) 2 + 2 ＝ 4 当且仅当 太阳从东方升起. (4) 2 + 2 ＝ 4 当且仅当 美国位于非洲. (5) 函数 f (x) 在x0 可导的充要条件是它在 x0
解 令 p：王晓用功，q：王晓聪明，则 (1) p∧q (2) p∧q (3) p∧q.
12
例 (续)
令 r : 张辉是三好学生，s :王丽是三好学生 (4) r∧s. (5) 令 t : 张辉与王丽是同学，t 是简单命题 .
说明: (1)~(4)说明描述合取式的灵活性与多样性. (5) 中“与”联结的是两个名词，整个句子是
若 p，就 q 只要 p，就 q p 仅当 q 只有 q 才 p 除非 q, 才 p 或 除非 q, 否则非 p. 当 p 为假时，pq 为真 常出现的错误：不分充分与必要条件

2)有向图关联矩阵的性质 （1） ∑mij= 0，j＝1，2，…，m，从而∑∑mij = 0，这说明M(D)中所有元 素之和为0． (2) M(D)中，负1的个数等于正1的个数，都等于边数m，这正是有向图握手定 理的内容（入度之和等于出度之和）． （3）第i行中，正1的个数等于d+(vi)（结点的入度），负1的个数等于d-(vi) （结点的出度）． （4）平行边所对应的列相同 3、有向图的邻接矩阵 1）定义：设有向图D＝<V，E>，V＝{v1，v2，…，vn}，E＝{e1，e2，…，em} 令： aij为顶点vi邻接到顶点vj边的条数 称(aij))nxn为D的邻接矩阵，记作A(D)，或简记为A． 2）邻接矩阵的性质 （1）每列元素之和为结点的入度，即 ∑aij ＝ d+(vi)，i＝1，2，…，n 所有列的和 ∑∑aij ＝ ∑d+(vi) ＝ m ，等于边数 每行元素之和为结点的出度，所有行的和也等于边数 （2）邻接矩阵中元素 aij 反映了有向图中结点vi到vj通路长度为1的条数
§14.4
图的矩阵表示
一、图的矩阵表示 用矩阵表示图之前，必须将图的顶点或边标定成顺序，使其成为标定图 1、无向图的关联矩阵 1）定义14．24 设无向图G＝<V，E>，V＝{v1,v2,…，vn}。 E={e1,e2,e3，…em}，令mij为顶点vi与边ej的关联次数，则称(mij)nxm为G的 关联矩阵，记作 M(G)． 2）关联矩阵的性质: 关联矩阵是n行（结点数）m列（边数）的矩阵
2、结点的相互可达 若vi → vj 且vj → vi 则称vi与vj是相互可达的，记作: vi ↔ vj 规定vi ↔ vi ． 3、 结点的可达关系为V上的二元关系，但不是等价关系（不满足对称性）。 相互可达关系为V上的二元关系，且是V上的等价关系． 有向图中顶点之间的可达关系既无对称性，也无反对称性 4、有向图中结点的距离 定义：设D＝<V，E>为有向图 ∀ vi,vj ∈V，若 vi → vj，称vi到vi长度最短的通路为vi到vj的短程线 短程线的长度为vi到vj的距离，记作d<vi，vj> 注：该定义与无向图中顶点vi与vj之间的距离d(vi，vj)的区别：无对称性 一般地：d<vi，vj> ≠ d<vj，vi> （可能d<vi，vj> 不存在） 5、弱连通图、单向连通图和强连通图 定义1 设D＝{V，E)为一个有向图． 若D的作为无向图是连通图，则称D是弱连通图，简称为连通图． 定义2 设D＝{V，E)为一个有向图， 若∀ vi,vj ∈V , vi → vj与vj→ vi至少成立其一，则称D是单向连通图． 若∀ vi,vj ∈V，均有vi ↔ vj，则称D是强连通图 注：三种图的关系：强连通图一定是单向连通图，反之不成立 单向连通图一定是弱连通图．反之不成立

第18页/共26页
7.2.3 图的连通度
定义7-2.4 设无向图G =<V,E>是连通图,若有结点集V1V,使图 G中删除了 V1的所有结点后,所得到的子图是不连通图,而删除了V1的任何真子集后,所
得到的子图仍是连通图,则称V1是G的一个点割集(cut-set of nodes) 。
k(G)=min{|V1|| 是G的点割集} 称为图G的点连通度(nodeconnectivity) 。
现对G的每一条边e＝(u1,u2)，若u1,u2都在 V1上 ，则存 在两条 路P1与P2分别 连接u与 u1和u与u2， 且P1、 P2的长 度均为 偶数， 闭路P1∪P2∪ {e}的 长度为 奇数， 则不难 看出G中 有一条 长为奇 数的圈 ，矛盾 。同样 u1和u2不能同 时含在 V2中。 故e的 两个端 点分别 在V1和 V2中。 因此G是二分 图。
G 定理7.2.1 非平凡图 是二分图当且仅当 中不含长为奇数的回路。
G
证明 必要性是明显的。
充分性：不妨设G中每一对顶点之间有路连接（否则
只需考虑G的每个每一对顶点之间有路连接的极大子
图）。任取G的一个顶点u，由G的假设，对G的每个顶
点v，在G中存在u-v路。现利用u对G的顶点进行分类。
设
第24页/共26页
3 v1e1v2e5v5e6v4e4v2e5v5e7v6
…………
初级通路 简单通路 复杂通路
7.2.1 路
例1、(2)
图(2)中过 v2 的回路 (从 v2 到 v2 )有：
第7页/共26页
1 v2e4v4e3v3e2v2
长度3
2 v2e5v5e6v4e3v3e2v2
长度4
3 v2e4v4e3v3e2v2e5v5e6v4e3v3e2v2 长度7

离散概率分布的定义
离散概率分布是描述随机事件在有限或可数无限的可 能结果集合中发生的概率的数学工具。
离散概率分布的种类
常见的离散概率分布包括二项分布、泊松分布、几何 分布等。
离散概率分布的应用
离散概率分布在统计学、计算机科学、物理学等领域 都有广泛的应用。
参数估计和假设检验
参数估计
参数估计是根据样本数据推断总体参数的过 程，包括点估计和区间估计两种方法。
假设检验
假设检验是用来判断一个假设是否成立的统计方法 ，包括参数检验和非参数检验两种类型。
参数估计和假设检验的应 用
在统计学中，参数估计和假设检验是常用的 数据分析方法，用于推断总体特征和比较不 同总体的差异。
方差分析和回归分析
方差分析
方差分析是一种用来比较不同组数据的平均值是否存在显著差异 的统计方法。
《离散数学讲义》ppt课件
目 录
• 离散数学简介 • 集合论 • 图论 • 离散概率论 • 逻辑学 • 离散统计学 • 应用案例分析
01
离散数学简介
离散数学的起源和定义
起源
离散数学起源于17世纪欧洲的数学研 究，最初是为了解决当时的一些实际 问题，如组合计数和图论问题。
定义
离散数学是研究离散对象（如集合、 图、树、逻辑等）的数学分支，它不 涉及连续的变量或函数。
联结词：如与(&&)、或(||)、非(!)等，用 于组合简单命题。
03
04
命题公式：由简单命题通过联结词组合而 成的复合命题。
命题逻辑的推理规则
05
06
肯定前件、否定后件、析取三段论、合取 三段论等推理规则。
谓词逻辑
个体词
表示具体事物的符号。

PowerPoint Template_Sub
1 图的基础知识 2 路径、回路及连通性 3 欧拉图与哈密顿图 4 图的矩阵表示
《离散数学》第18讲 路径、回路及连通性 Page 112 to 117
拟路径及长度
定义：图G的顶点v1到顶点vl的拟路径是指以下顶点与边的序列： v1 , e1, v2, e2, v3, …, vl-1, el-1, vl v1 ,v2 ,v3 ,… ,vl-1 ,vl为G的顶点，e1 ,e2 ,… ,el-1 为G的边 ei( i= 1,2, … ,l-1 )以vi及vi+1为端点 对有向图G，ei以vi为起点，以vi+1为终点
证明：若G为不连通图或单一孤立结点的图，那么据定义知:
χ(G) = λ(G) = 0≤δ(G) 。 若G为完全图Kn，那么χ(G) = λ(G) = δ(G) = n – 1 。 对其它情况：先证λ(G) ≤δ(G)。 由于度数最小的那个结点上关联的所有边被删除后，G显然不 再连通，因而λ(G)至多是δ(G)，即λ(G) ≤δ(G)。
证明：充分性是显然的。 必要性：设顶点v是简单连通图G的割点，如果不存在两个 顶点v1，v2，使v1到v2的通路都经过顶点v，那么对任意两 个顶点v1，v2，都有一条通路不经过顶点v，因而删除顶点v 不能使G不连通，与v是简单连通图G的割点矛盾。故G中必 存在两个顶点v1，v2，使v1到v2的通路都经过顶点v 。
第18讲 路径、回路及连通性
-20-
边连通度
定义：λ(G)称为图G的边连通度，定义如下：
0
当G非连通图时
(G) 0
当G为一孤立结点时
min{ S : S为G的割集} 否则
v1
v4 v2
v5 v7