第8章 有向图.ppt
图论及其应用图论及其应用第第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是它的一条(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 from 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的任二双向分支之间的弧都是同一个方向的任二双向分支之间的弧都是同一个方向的。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.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个顶点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图论及其应用图论及其应用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 进行顶点着色如下：将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图论及其应用图论及其应用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.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中的顶点，都是从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.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，则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也存在双向连通定向图。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图论及其应用图论及其应用
