chap14有向图汇总.pptx

1 第十四章 有向图 2 §14.1 有向图的概念 3 有向图的定义 定义14.1.1：一个有向图D是一个有序三元组 V(D), A(D), D , 其中， 1)V(D)是非空顶点集合，简记为V ; 2)A(D)是弧的集合，简记为A，A∩V= ; 3) D是A到VV={u,v|u , v∈V}的一个映射，称为关联函数，简记为 . 为方便，有时将u ,v简记为uv . 易知，uv = vu当且仅当u =v . 注：有向图可以简单理解为“边有方向的图” 4 一个有向图V, A,  设V={u ,v ,w, x}, A= {1 ,2 , …,9}, 定义如下： (1) =uv , (2) =vv , (3) =vw , (4) =xw , (5) =vx , (6) =xv , (7) =xu , (8) =ux , (9) =xu . x u w v 1 5 8 9 6 4 7 3 2 5 有向图与无向图 无向图与有向图的区别：无向图中的是将边映射为顶点的无序对偶，uv = vu。而有向图中的映射D是将边映射为顶点的有序对偶，uv≠vu，故为有向。 有向图D 不记弧的方向 D的基础图 无向图G 规定边的方向 G的定向图 6 有向图中的弧（边） 弧的头和尾：如果是有向图D的一条弧，且() =uv , 则称u是的尾，v是的头。 环：有向图中头尾相同的弧。 多重弧：两条或两条以上的头尾相同的弧。 简单有向图：无环，无多重弧的有向图。 u v  多重弧 非多重弧   ’ ’ 7 有向图中的度 出度：在有向图中，以顶点u为尾的弧（从u射出的弧）的数目称为u的出度，记为dD+(u) ; 入度：在有向图中，以顶点u为头的弧（射入u的弧）的数目称为u的入度，记为dD– (u) ; 度：顶点u的入度与出度的和为u的度,记为 dD(u)= dD+(u)+ dD– (u) ; dD+(a)=2 dD- (a)=1 dD(a)=3 8 有向图中的途径 有向途径:有向图中一个头尾相接的途径，即：w=v01v1,…, kvk，vi∈V(D), j∈A(D)且D(j)= vi-1 vi (j的弧尾是vi-1 ，弧头是vi )，i=0,1,…,k , j=1,…,k； 有向链：弧不重复的有向途径； 有向通路：顶点不重复的有向途径，u为起点，v为终点的有向通路记为(u,v)-通路； 有向通路长度：通路上弧的数目； 有向回路：起点和终点重合的有向通路； 有向k-回路：长度为k的有向回路； 注：以上概念与无向图中相关概念类似，只是增加了方向性。 9 有向图的连通性 定义14.1.2：设D是有向图， ⑴若对D中任意顶点u、v，同时有(u, v)—通路和(v, u)—通路存在，称D是双向连通图，或强连通图； ⑵若对D中任意顶点u、v，或有(u, v)—通路，或有(v, u)—通路，称D是单连通图; ⑶若D的基础图是连通图，则称D是弱连通图。 显然，强连通图单连通图弱连通图。 有向图的连通性 (a)是强连通的 (b)是单连通的 (c)是弱连通的 强连通图的充要条件（补充） 定理：有向图D=(V,A)是强连通的，当且仅当D中存在包含D中所有顶点的有向闭链。 11 12 强连通分支 强连通分支：有向图D的极大强连通子图. 该图有三个强连通分支,如图所示（用红、绿、蓝三种颜色标记）。 13 §14.2 有向通路与有向回路 14 有向通路的长度 有向图中有向通路的长度与其基础图中的（无向）通路的长度无关。 却与图的色数有关 . 最长有向通路长度=1 色数(G)=2 15 有向通路之长不短于色数减一 定理14.2.1 ：有向图D中包含长度至少为(G) –1的有向通路。其中，G为D的基础图。 证明思路： 寻找有向图D的最长有向通路k 构造一个(k+1)点着色β 证明β是正常（k+1）着色 由图色数(G)≤k+1得结论：k≥ (G) –1 16 v1 v2 v3 D v5 1(a).令 A是使D不含有向回路所需删去的最小弧集 v4 A’={(v5v2)} 1(b).令D=D – A，设D中最长有向通路的长度为k D’ k=3 2(a).对D进行点着色 ：若D中以v为起点的最长有向通路之长为i-1，令(v)=i 4 3 2 1 2 2(b).这样就得到一个 (k+1)着色。下证是G的正常(k+1)着色。 17 v1 v2 v3 D v5 3(a). D 中任何一条有向(u, v)-通路(u≠v)P均满足(u)≠(v) v4 3(b). D 中的任何弧(u,v) 的首尾不同色