§8.2有向路与有向圈 定义8.21有向图的一个有向途径是指一个有限非空序列w=va1"1…a4v4,它的各项交替地 是顶点和弧,使得a=(1,v)(=1,2,…,k)。弧不重复的有向途径称为有向迹;顶点不重复 的有向途径称为有向路:首尾相接的有向路称为有向圈。 注:有向图中有向路的长与其底图中路的长之间没有多大关系。例如: 但却与底图的色数有关 定理8,1(Roy,1967;Gaai,1968)以图G为底图的有向图G中必有长为x(G)-1的有向路 证明:设A是使有向图G-A不含有向圈的最小弧子集。设G-A中最长有向路的长为k。 按如下方式将颜色1,2,…,k+1分配给G-A的顶点: 对任何顶点v∈v(G-A),如果G-A中从v出发的最长有向路长为i,则给v染色计1 用V表示染有第i种色的顶点的集合。下证(1,2…,Wk+1)是G的正常k+1顶点染色。为此, 先证明关于这种染色的两个结论 (1)G-A中任一有向路的起点与终点异色 事实上,设P(l,)是G-A的一条有向路,l≠v。无妨设v∈V。由染色规则可知,存 在有向路 Q=vv1V2…vsG-A 其中v=v。又因G-中没有有向圈,故v1,"2…,ngP(u,)。因此P(u,v)儿UQ是起点为u且 长至少为计+1的有向路。于是由染色规则,ugV。 (2)G的任一条边两端点异色 事实上,设e=∈E(G)。若w∈A',则由A'的最小性,(G-A')+含有有向圈C。C 是G-A的一条有向路,故由(1),u与v异色:若∈AG-A),则v是G-A的 条有向路。由(1),u与v也异色。 可见(1,V2…,Wk)是G的正常k+1顶点染色。因而x(G)≤k+1,即k≥x(G)-1。证毕。 定理822若G是无环有向图,则其底图G中必有一个独立集S,使得对V(G)-S中的每个 顶点v,存在v∈S,在G中从v到v有长不超过2的有向路。 证明:对顶点数v作归纳。 v=1时定理显然成立 假设对顶点数少于v的所有有向图G,结论成立。考虑顶点数为v的有向图G。2 §8.2 有向路与有向圈 定义 8.2.1 有向图的一个有向途径是指一个有限非空序列 w vav av = 0 11" k k ，它的各项交替地 是顶点和弧，使得 1 ( , ),( 1,2, , ) i ii a vv i k = = − " 。弧不重复的有向途径称为有向迹；顶点不重复 的有向途径称为有向路；首尾相接的有向路称为有向圈。 注：有向图中有向路的长与其底图中路的长之间没有多大关系。例如： 但却与底图的色数有关。 定理 8.2.1 (Roy,1967;Gallai,1968) 以图 G 为底图的有向图G JG 中必有长为χ()1 G − 的有向路。 证明：设 A′ 是使有向图G A − ′ JG 不含有向圈的最小弧子集。设G A − ′ JG 中最长有向路的长为 k。 按如下方式将颜色 1, 2, ···, k+1 分配给G A − ′ JG 的顶点： 对任何顶点v VG A ∈ − ( )′ JG ，如果G A − ′ JG 中从 v 出发的最长有向路长为 i，则给 v 染色 i+1。 用 Vi 表示染有第 i 种色的顶点的集合。下证(V1,V2,···,Vk+1)是 G 的正常 k+1 顶点染色。为此， 先证明关于这种染色的两个结论。 （1）G A − ′ JG 中任一有向路的起点与终点异色 事实上，设 P(u,v)是G A − ′ JG 的一条有向路，u≠v。无妨设 i 1 v V ∈ + 。由染色规则可知，存 在有向路 Q vvv v G A 012 i = ⊆ − ′ JG " 。 其中 v0=v。又因G A − ′ JG 中没有有向圈，故 1 2 , , , (,) i v v v Puv " ∉ 。因此 Puv Q (,) ∪ 是起点为 u 且 长至少为 i＋1 的有向路。于是由染色规则， i u V ∉ 。 （2）G 的任一条边两端点异色。 事实上，设e uv E G = ∈ ( ) 。若uv A ∈ ′ ，则由 A′ 的最小性，( G A − ′ JG )+uv 含有有向圈 C。C - uv 是G A − ′ JG 的一条有向路，故由（1），u 与 v 异色；若uv A G A ∈ − ( )′ JG ，则 uv 是G A − ′ JG 的一 条有向路。由（1），u 与 v 也异色。 可见(V1,V2,···,Vk+1)是 G 的正常 k+1 顶点染色。因而χ() 1 G k ≤ + ，即k G ≥χ − ()1。证毕。 定理 8.2.2 若G G 是无环有向图，则其底图 G 中必有一个独立集 S，使得对VG S ( ) − 中的每个 顶点 v，存在 0 v S ∈ ，在G G 中从 0 v 到v 有长不超过 2 的有向路。 证明：对顶点数 ν 作归纳。 ν =1 时定理显然成立。 假设对顶点数少于 ν 的所有有向图G G ，结论成立。考虑顶点数为 ν 的有向图G G