第8章 有向图.ppt

《第8章 有向图.ppt》由会员分享，可在线阅读，更多相关《第8章 有向图.ppt（23页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图论及其应用图论及其应用第第8章章 有向图有向图 8.1 有向图有向图 有向图有向图（directed graph；digraph）D=（V，A）V(D)顶点集。A(D)弧集。弧弧a=(u,v)：其头头为v，其尾尾为u；弧a从u连到连到(join to)v。有向子图有向子图（subdigraph）有向图D的基础图基础图（underlying graph）对应于D的无向图G（称D为G的一个定向定向（orientation）图图）u v a 2图论及其应用图论及其应用8.1 有向图有向图（无向）图的每个慨念在有向图中仍然有效例如，右图是2-连通图；有Hamiton 圈；有完美匹配；=3；vrswu

2、是它的一条(v,u)-路；vyzwsrv是它的一个圈，等等。此外，有向图还有一些与方向有关的慨念，如有向途径有向途径（directed walk）、有向迹有向迹（directed trail）、有向路有向路（directed path）、有有向向Euler环游环游（direted Euler tour）、有向圈有向圈（directed cycle）等等。例如右图中，(v,e1,x,e2,y,e3,z,e4,w,e5,u)为一 有向有向(v,u)-路路，可简记为（v,x,y,z,w,u）；又，(y,z,w,s,r,x,y)为一 有向圈。称 顶点v为 从从u可达的可达的（reachable fro

3、m u）存在有向（u，v）-路。称 顶点u与v 为双向连通的双向连通的（diconnected；strongly connected）u与v彼此可达的。3图论及其应用图论及其应用8.1 有向图有向图易见，有向图D=(V,A)中顶点间的双向连通性是V上的一个等价关系，它的等价类确定了V的一个划分 （V1，Vm），使顶点u与v双向连通 u与v 同属某等价类Vi。称每个导出子图DV1，DVm为有向图D的一个双向分支双向分支（dicomponent；strong component）。当D只有一个双向分支时，称D为双向连通的。双向连通的。易见，D的任二双向分支之间的弧都是同一个方向的任二双向分支之间的

4、弧都是同一个方向的。l例 4图论及其应用图论及其应用8.1 有向图有向图入度入度（indegree）。出度出度（outdegree）。记号 +，：最小出、入度；+，-：最大出、入度。称有向图D为严格的严格的（strict）无环、且不存在两弧其端点及方向相同。5图论及其应用图论及其应用8.1 有向图有向图习题习题10.1.1.一个简单图有多少个定向图？10.1.2.证明：=。10.1.3.设有向图D中无有向圈，则 (a)=0；(b)存在一个顶点排序v1，v，使对1 i ，每条以vi为 头的弧其尾都在v1，vi-1 中。10.1.4.证明：D是双向连通的 D是连通的，且D的每个块是双向连通的。10

5、.1.5.D的逆图逆图 是把D中每弧的方向都改为其反向所得的有向图。试用逆图慨念及习题10.1.3.(a)来证明：若有向图D中无有向圈，则+=0。10.1.6.证明：严格有向图包含长 max，+的有向路。10.1.7.证明：严格有向图中若max，+=k 1，则D包含长 k+1 的有向圈。6图论及其应用图论及其应用8.1 有向图有向图习题（续）习题（续）10.1.8.设 矩阵A=aij 为有向图D的邻接矩阵，其中aij 是D中以vi为尾、以vj为头的弧数。证明：Ak的第(i,j)元素是D中长为k的（vi,vj）-有向途径的数目。10.1.9.设D1，Dm为D的双向分支。D的凝聚图凝聚图H是一有m

6、个顶点w1，w 的有向图。H中存在以wi为尾、以wj为头的弧，当且仅当D中存在尾在Di 、而头在Dj中的弧。证明：H中不包含有向圈。10.1.10.证明：任一图G都有一个定向图D，使对每个顶点v都有|d+(v)-d-(v)|1 10.1.11.证明：D是双向连通的 对10.1.12 在连通非空有向图D中，证明：D是双向连通的 D中每弧在一有向圈上 10.1.13.设D为一以以（顶点）u为根的有向图为根的有向图（对D中任一顶点，D中都存在一有向(u,v)-路），证明：D中有一以为根的有向树以为根的有向树，中每一（唯一）有向(u,v)-路是D中最短有向(u,v)-路。10.1.14.有向图中任一有

7、向闭迹恒可划分为一些边不重的有向圈的併。7图论及其应用图论及其应用8.1 有向图有向图习题（续）习题（续）10.1.15.设T=(V,A)为一有向树有向树（无向）树的一个定向），FA(T)。证明：存在一顶点x，它恰只是F中弧的头（即不能是尾）。8图论及其应用图论及其应用10.2 有向路有向路定理定理10.1 (Roy,1967;Gallai,1968)有向图有向图D包含一包含一长为长为 -1 的有向路的有向路。l证明：令D为D的极大极大无有向圈、有向生成子图（注：D 可由空生成子图作为开始，在保持无有向圈的条件下，通过逐步加弧而得）。令k为D 中最长有向路的长。今用色1，2，k+1对D 进行顶

8、点着色如下：将v着以色i D 中以v为起点的最长有向路的长为i-1。来证这是D的正常(k+1)-顶点着色：l先证，D 中任一有向(u,v)-路P的起、终点u与v一定不同色：设v被着以色i。则由着色法知，在 D 中以v为起点的一最长有向路，设为，Q的长为i-1。由于D 中无有向圈，PQ为一有向路，起点为u，长 i。从而u上的色j i。l只要再证，D中任一弧(u,v)的两端一定不同色：当(u,v)为D 中的弧时，它就是D 中的一有向(u,v)-路，从而u与v不同色。在有向图中，最长路的长和最长有向路的长之间并无任何密切的关系，例如右面的有向图最长路的长为（可任意大），而最长有向路的长卻为19图论及

9、其应用图论及其应用10.2 有向路有向路l当(u,v)不是D 中的弧时，由D 之极大性知 D+(u,v)包含一有向圈C。于是，C-(u,v)是 D 中的有向(v,u)-路，从而u与v也不同色。l由上述知，D为(k+1)-可着色的，因此 k+1，得k -1，故D中有长为-1 的有向路。#注注 定理10.1在如下意义下是最佳的：对每个（无向）图对每个（无向）图G，都存在，都存在G的一个定向图，其最长的一个定向图，其最长有向路的长恰为有向路的长恰为 -1。l证明：令（V1，V-1）为G的正常 -顶点着色。今作G的定向图D如下：边uv（不妨设，u Vi，v Vj）定向为弧(u,v)i -1的有向路。再

10、由定理10.1得证。#称完全图的定向图为竞赛图竞赛图（tournament，是简单图！）。10图论及其应用图论及其应用10.2 有向路有向路推论推论10.1(Redei,1934)每个竞赛图都有一Hamilton 路。l证明：注意到=即可。#设(u,v)为有向图D中的一弧，则称u为v的内邻点内邻点（in-neighbour）；称v为u的外邻点外邻点（out-neighbour）。记 和 分别为有向图D中顶点v的内邻集内邻集和外邻集外邻集。11图论及其应用图论及其应用10.2 有向路有向路定理定理10.2(Chavtal&Lavasz,1974)无环、有向图D中包含一独立集S，使D的每个不在S中

11、的顶点，都是从S中某顶点通过长 2的有向路可达的。l证明：对 进行归纳。当 =1时，显然成立。假设定理对顶点数 mn的有向图，而f是定义在V上的一个实函数。证明：D中或者存在一有向路(u0，u1，um)满足f(u0)f(u1)f(um)；或者存在一有向路(v0，v1，vn)满足f(v0)f(v1)f(vn)。(b)试证：任意mn+1个不同整数的序列中，或者包含一个m项的递增子序列；或者包含一个n项的递减子序列13图论及其应用图论及其应用10.2 有向路有向路习题（续）10.2.6.(a)利用定理10.1和推论8.1.2证明：G有一个定向图，它的最长有向路的长。(b)给出(a)的构造性证明。10

12、.2.7 一竞赛图中至多有一的顶点，它是一有向哈密尔顿路的起点（或 终点）。10.2.8每一竞赛图中恒有 。14图论及其应用图论及其应用10.3 圈圈 记号（S，T）是D中尾在S内而头在T内的所有弧的集合。（S，T是V的子集）定理定理10.3(Moon,1966)3的双向连通竞赛图D中，每个顶点包含在一有向k-圈中，3 k 。证明：设u是D的任一顶点。用对k的归纳法来证明。当 k=3时，令S=N+(u)，T=N-(u)。由D的双向连通性知，S，T，（S，T）都是非空的。因此D中存在一弧(v,w)使v S，w T。从而u在有向3-圈(u,v,w,u)中，结论成立。假设对每一k，3 k n 1，则

13、D包含一有向Hamilton 圈。l证明：反证，假设D不包含有向 Hamilton 圈。令 C=（v1，v2，vq，v1）D中一最长有向圈，其长 为 q 。易见，q /2（习题10.1.7）。令P为 D-V(C)中的一条最长有向路，其长为m；其起、终点分别为u和v。显然，q+m+1 (1)m 0 使 i S，i+k T（mod q）i+j S T （mod q）1 j (Gi)，该序列一定终止于G的一生成子图Gn上。今对Gn定向如下：把G1定向为一有向圈；把Pi定向为一以vi为起点的有向路；把Qi 定向为以vi为终点的有向路。显然，每个Gi有一双向连通定向。由于Gn是G的一生成子图，G也存在双

14、向连通定向图。22图论及其应用图论及其应用10.4 公路系统的单行线化公路系统的单行线化定理定理（Nash-Williams ，1960）G为2k-边连通的 G有k-弧连通弧连通定向图。l（证略）（即|（S，S）|k S V）上述定理的特殊情形为以下定理，其证明较容易，留给读者完成：定理定理10.6 G为2k-边连通，且有一Euler 迹 G有一k-弧连通定向图。习题习题10.5.1*通过考察Petersen图证明以下结论不成立：每个图都有一定向图，使得对每个S V，（S，）和（，S）的弧数相差最多为1。10.5.2*.(a)证明Nash-Williams定理下述命题：若G的每个键至少有2k-条边，则存在G的一个定向图，其中每个键在每个方向上都至少有k-条弧。(b)通过考察Grotzsch图证明以下结论不成立：若G的每个圈至少有2k-条边，则存在G的一个定向图，其中每个圈在每个方向上都至少有k-条弧。23图论及其应用图论及其应用