离散件图的道路与连通

离散件图的道路与连通演示文稿现在是1页\一共有38页\编辑于星期日（优选）离散件图的道路与连通现在是2页\一共有38页\编辑于星期日2。道路的分类：①迹：任何满足道路定义的道路。②简单道路：边不重复出现的道路。③基本道路：结点不重复出现的道路。例：上图中，p1是迹，p2是简单道路，p3是基本道路，p4是零道路。现在是3页\一共有38页\编辑于星期日3。回路：起点和终点相同的道路。边不重复出现的回路称为简单回路。结点不重复出现的回路称为圈。例：下图中，c1是一般回路，c2是简单回路，c3是圈。现在是4页\一共有38页\编辑于星期日例：下图中c1=v1e1v1e2v2e7v4e8v3e4v1e3v2e2v1c2=v1e1v1e2v2e3v1e5v4e8v3e4v1c3=v1e5v4e10v6e12v5e9v3e4v1（c3可简记为：c3=v1v4v6v5v3v1）都是回路。c1是一般回路，c2是简单回路，c3是圈。v1v2v3v4v6v5e9e10e12e8e7e2e4e5e6e3e1e11现在是5页\一共有38页\编辑于星期日4。定理：设G是n阶图，如果存在从结点u到v的道路，则必存在长度不超过n-1的道路。

证明要点：如果结点u到v的道路p的长度超过n-1，则p中至少有n+1个结点，因而道路中至少有一个结点出现两次，如viei...v1，则去掉ei...vi后仍是结点u到v的道路，但是道路长度至少短1。重复这一过程，即得所需结论。现在是6页\一共有38页\编辑于星期日二、无向图的连通问题1。定义:如果存在从结点u到结点v的道路，则称u到v是连通的。结点集V上的“连通”关系具有性质：自反、对称、传递。2。如果图G中任何两个结点都是连通的，则称G是连通图。现在是7页\一共有38页\编辑于星期日3。图G中的极大连通子图称为图G的支，图G的支数记为(G)。图G连通当且仅当(G)=1。

例：下图中(G)=3。v1v6v4v7v5v2v3v8现在是8页\一共有38页\编辑于星期日4。连通图G=(V,E)的点割集定义：设SV，如果(G-S)>1，则称S是G的一个点割集。

①S是G的一个点割集，而S的任何真子集都不是点割集时，称S是G的一个基本点割集。如S1={v2，v5}，S2={v2，v6},S3={v2，v7}，S4={v3，v5},S5={v4}②由单个结点（如u）构成的点割集简称为割点。v1v6v4v7v5v2v3现在是9页\一共有38页\编辑于星期日定理结点u是图G的割点当且仅当存在两结点v和w，使v到w的任何道路都经过u。证明要点：“”,当u是割点时，则Gu至少有2支，从这2支中各选一个结点即可。“”,反之，如果v到w的任何道路都经过u，则去掉u后，v和w各在Gu的1支中，即u是割点。现在是10页\一共有38页\编辑于星期日5。连通图G=(V,E)的边割集定义：设FE，如果(G-F)>1，则称F是G的一个边割集。

①F是G的一个边割集，而F的任何真子集都不是边割集时，称F是G的一个基本边割集。如F1={v2v3，v3v7}，F2={v2v3，v5v7},F3={v1v4}，F4={v2v4，v2v6，v5v6},F5={v4v6，v2v6，v2v5，v3v7}②由单条边（如uv）构成的边割集简称为割边。v1v6v4v5v2v3v7现在是11页\一共有38页\编辑于星期日定理边e是图G的割边当且仅当e不在G的任何回路上。

证明要点：“”:当e是割边时，则Ge有2支，因而e不在G的任何回路上。“”:反之，如果e不在任何回路上，则去掉e后，e关联的两个结点各在Ge的1支中，即e是割边。

现在是12页\一共有38页\编辑于星期日

6.图的连通度(限无环图G)(1)点连通度:记为К(G),定义为 最小基本点割集基数, 当GKn

К(G) n1, 当GKn例如下图中,К(G)2v1v6v4v5v2v3v7v8现在是13页\一共有38页\编辑于星期日(2)边连通度:记为λ(G),定义为 最小基本边割集基数, 当GK1

λ(G) 0, 当GK1例如下图中,К(G)2,

λ(G)2v1v6v4v5v2v3v7v8现在是14页\一共有38页\编辑于星期日练习:求下列图的К(G),

λ(G),和К(G)=2λ(G)=2=2К(G)=2λ(G)=2=2К(G)=2λ(G)=3=4现在是15页\一共有38页\编辑于星期日(3)连通度定理:К(G)λ(G)证明要点:首先,每个结点关联的边构成一个边割集,于是λ(G).下面证明К(G)λ(G)：首先注意对每个基本边割集F，(G-F)=2；其次设F含λ(G)条边，G-F的2支为G1和G2，若G不是二部图，则去掉这支中与F关联的全部结点即可；若G是二部图，则交替删去这2支中与F关联的结点即可。现在是16页\一共有38页\编辑于星期日四、有向图的道路1。定义：如果图G中由结点和边交替构成的序列p=v0e1v1e2v2...ekvk,满足其中每条ei是vi-1的出边和vi的入边，则称p为由v0到vk的一条有向道路。在下图中，一些有向道路p1=v1v4v2v1v3v5v4 p2=v3v2v1v3v5v4v2

p3=v5v4v2v1v3v1v2v3v4v5现在是17页\一共有38页\编辑于星期日2。有向道路的分类：①有向迹：任何满足定义的有向道路。②有向简单道路：边不重复的有向道路。③有向基本道路：结点不重复的有向道路。3。有向回路：起点和终点相同的有向道路。边不重复的有向回路称为有向简单回路。结点不重复的有向回路称为有向圈，现在是18页\一共有38页\编辑于星期日在下图中，一些有向回路p1=v1v4v2v1v3v5v4v2v1p2=v3v2v1v3v5v4v3p3=v5v4v2v1v3v5v1v2v3v4v5现在是19页\一共有38页\编辑于星期日五、有向图的连通问题1。如果存在从结点u到结点v的有向道路，则称u可达v。结点集V上的“可达”关系具有性质：自反、传递。定理：如果在n阶有向图中结点u可达v，则必存在从结点u到结点v的长度不超过n-1的有向道路。现在是20页\一共有38页\编辑于星期日2。有向图G的连通有如下三个层次：①强连通图：任何一对不同结点都相互可达。②单向连通图：任何一对不同结点间，至少从一个结点可达另一个结点。③弱连通图：不看边的方向时是连通的。

abcd单向连通弱连通abcdabcd强连通现在是21页\一共有38页\编辑于星期日3。强连通的性质①死锁问题的强连通背景②定理:有向图G是强连通图当且仅当存在一条包含所有结点的有向回路。证明要点：当G强连通时,据定义可依次构造道路v1v2

v3…vn

v1,反过来是明显的.③定义：有向图G的极大强连通子图称为强分图。例：下面有３个强分图:G({v2,

v3,

v4}),G({v5,

v6})G({v1})v1v2v5v3v4v6现在是22页\一共有38页\编辑于星期日定理：每个结点都只位于一个强分图中。证明要点：强连通是结点集合上的一个等价关系，由每个等价类诱导的子图是一个强分图．

现在是23页\一共有38页\编辑于星期日作业：习题9。21、2、5(吴子华)or习题10。31、2、5(冯伟森)附加题1：证明>1的图必含回路，反之成立吗？附加题2：证明连通图的1度结点不是割点。现在是24页\一共有38页\编辑于星期日第三节图的矩阵表示一、邻接矩阵1。设G=(V,E)是有向简单图,其中V={v1,v2,...,vn},定义矩阵A=(aij)

nn如下:1如果(vi,vj)Eaij=0如果(vi,vj)E

称A为G的邻接矩阵.现在是25页\一共有38页\编辑于星期日下面有向图对应的邻接矩阵是v1v2v3v4v5v100110v210110A=v300001v400100v500010v1v2v5v3v4现在是26页\一共有38页\编辑于星期日2。邻接矩阵的性质：①邻接矩阵等价地描述了有向图的信息。矩阵行和等于结点出度，列和等于入度。②设A2=(a(2)ij)，则

a(2)ij=1kn

(aikakj)

a(2)ij

0当且仅当至少存在aik=1且

akj=1，也就是存在从vi到vj的长度为2的有向道路。因此

a(2)ij的值表达了从vi到vj的长度为2的有向道路数目。现在是27页\一共有38页\编辑于星期日例如，对于前面的邻结矩阵v1v2v3v4v5v100101v200211A2=v300010v400001v500100

从中可以看出，存在一条从v1到v3的长度为2的道路，2条从v2到v3的长度为2的道路，1条从v4到v5的长度为2的道路，不存在从v5到v2的长度为2的道路等等。v1v2v5v3v4现在是28页\一共有38页\编辑于星期日v1v2v3v4v5

v100011v200112A3=v3

00100v400010v500001v1v2v5v3v4现在是29页\一共有38页\编辑于星期日类似地，可以构造0011000121A4=000010010000010可对照图找出长度为4的有向道路.③设Am=(a(m)ij)，那么a(m)ij的值表达了从vi到vj长度为m的有向道路数目。a(m)ii的值表达了通过vi的长度为m的有向回路数目。

现在是30页\一共有38页\编辑于星期日3。可达矩阵设G=(V,E)是有向简单图,其中V={v1,v2,...,vn},定义矩阵P=(pij)

nn如下:1vi非平凡可达vjpij=0其它

称P为G的可达矩阵.现在是31页\一共有38页\编辑于星期日可达矩阵P可通过邻结矩阵A求得，方法之一是计算矩阵和：B=A+A2+...

+An-1然后，令pij=1当且仅当bij>0。例如，由前面的例子可得现在是32页\一共有38页\编辑于星期日B=A+A2+A3+A40033210554=001120021100121其中每个非0的bij表达了vi到vj的长度不超过4的道路数目，若bij=0，表明不存在从vi到vj的非平凡道路。

v1v2v5v3v4现在是33页\一共有38页\编辑于星期日由矩阵B直接可导出下面的可达矩阵：0011110111P=001110011100111可达矩阵也可以利用Warshall算法求得。v1v2v5v3v4现在是34页\一共有38页\编辑于星期日4。由可达矩阵构造图的强分图令Q=PPT=(qij)

nn，其中1i=jqij=pijpjiij那么，在矩阵Q中第k行中元素1对应列的结点，构成图的一个强分图。现在是35页\一共有38页\编辑于星期日例：根据前面例子得到的可达矩阵，可得00111010001011100000PPT

=00111