公共边的路P,Q1,它们的一端是v1,另一端在G1上。给定向为指向v1,Q1定向为指向 G1,令G2=G1UPUQ,则G2是强连通的。 若G2仍不是生成子图,则存在v2∈(G)-1(G2),同理,存在无公共边的路P2,Q2 其一端在v2处,另一端在G2中。给P定向为指向v2,Q2定向为指向G2,令 G3=G2UP2UQ2,则G3是强连通的。如此反复,可得一个强连通子图序列G1,G2 顶点数严格递增。因|I(G)是有限数,故必在某一步得到Gn后终止,G是强连通的且是 G的生成子图。最后,把G中不在G,中的边任意定向,得到以G为底图的一个强连通有向 证毕 定理8.3.3G是单连通有向图的充要条件是G的所有顶点在一个有向途径上 证明:充分性是显然的 必要性:首先用归纳法证明:对G的任何至少含有2个顶点的顶点子集S,必有u∈S, 使得u到S中每个其它顶点在G中都有有向路。 当S只含2个顶点时,由于G单连通,结论显然成立 假设对任何含有k个顶点的子集,结论成立。下证对含有k+1个顶点的子集S,结论也 成立 事实上,任取v∈S,由归纳假设,S-{v中必有某点u,它到S-{v}中每个其它顶点都 有有向路。由于G单连通,在G中、ν之间必有有向路。如果u到v有有向路,则u符合 结论的要求;如果v到u有有向路,则ν符合结论的要求。归纳法完成 下面来证明定理必要性的结论。 取S=v(G),由上述结论,存在劭1∈S,使得u到S中每个其它顶点都有有向路。再 令S2V(G)-{an},由上述结论,存在l2∈S2,使得l2到S2中每个其它顶点都有有向路。 再令S=V(G)-{n,a2},由上述结论,存在l2∈S3,使得3到S3中每个其它顶点都有有向 路。以此类推,可得到含所有顶点的序列,顶点沿序列依次有有向路,这些有向路合成一条 含所有点的有向途径。证毕 §84 Euler有向图和 Hamilton有向图 定义841经过有向图G的所有弧恰一次的有向迹称为G的一条 Euler有向迹。经过有向图 G的所有弧恰一次的有向闭迹称为G的一条 Euler有向闭迹。存在 Euler有向迹的有向图称 为Euer有向图。经过有向图G的所有顶点恰一次的有向路称为G的一条 Hamilton有向路 经过有向图G的所有顶点恰一次的有向圈称为G的一个 Hamilton有向圈。存在 Hamilton有 向圈的有向图称为 Hamilton有向图 定理8..平凡弱连通有向图G是Euer有向图的充分必要条件是对任何v∈(G),都 有d(v)=d(v)。4 公共边的路 1 1 P Q, ，它们的一端是 1 v ，另一端在G1上。给 P1定向为指向 1 v ，Q1定向为指向 G1，令G G PQ 2 11 1 = ∪ ∪ ，则G2 是强连通的。 若G2 仍不是生成子图，则存在 2 2 v VG VG ∈ () ( ) − ，同理，存在无公共边的路 2 2 P Q, ， 其一端在 2 v 处，另一端在 G2 中。给 P2 定向为指向 2 v ， Q2 定向为指向 G2 ， 令 G G PQ 3 22 2 = ∪ ∪ ，则G3 是强连通的。如此反复，可得一个强连通子图序列 1 2 G G, ,"， 顶点数严格递增。因| ( )| V G 是有限数，故必在某一步得到Gn 后终止，Gn 是强连通的且是 G 的生成子图。最后，把 G 中不在Gn 中的边任意定向，得到以 G 为底图的一个强连通有向 图。 证毕。 定理 8.3.3 G G 是单连通有向图的充要条件是G G 的所有顶点在一个有向途径上。 证明：充分性是显然的。 必要性：首先用归纳法证明：对G G 的任何至少含有 2 个顶点的顶点子集 S，必有u S ∈ ， 使得 u 到 S 中每个其它顶点在G G 中都有有向路。 当 S 只含 2 个顶点时，由于G G 单连通，结论显然成立。 假设对任何含有 k 个顶点的子集，结论成立。下证对含有 k+1 个顶点的子集 S，结论也 成立。 事实上，任取v S ∈ ，由归纳假设，S−{v}中必有某点 u，它到 S−{v}中每个其它顶点都 有有向路。由于G G 单连通，在G G 中 u、v 之间必有有向路。如果 u 到 v 有有向路，则 u 符合 结论的要求；如果 v 到 u 有有向路，则 v 符合结论的要求。归纳法完成。 下面来证明定理必要性的结论。 取 S1=V( G G )，由上述结论，存在 1 1 u S ∈ ，使得 u1到 S1 中每个其它顶点都有有向路。再 令 S2=V( G G ) −{u1}，由上述结论，存在 2 2 u S ∈ ，使得 u2到 S2 中每个其它顶点都有有向路。 再令 S3=V( G G ) −{u1, u2}，由上述结论，存在 3 3 u S ∈ ，使得 u3 到 S3 中每个其它顶点都有有向 路。以此类推，可得到含所有顶点的序列，顶点沿序列依次有有向路，这些有向路合成一条 含所有点的有向途径。证毕。 §8.4 Euler 有向图和 Hamilton 有向图 定义 8.4.1 经过有向图G G 的所有弧恰一次的有向迹称为G G 的一条 Euler 有向迹。经过有向图 G G 的所有弧恰一次的有向闭迹称为G G 的一条 Euler 有向闭迹。存在 Euler 有向迹的有向图称 为 Euler 有向图。经过有向图G G 的所有顶点恰一次的有向路称为G G 的一条 Hamilton 有向路； 经过有向图G G 的所有顶点恰一次的有向圈称为G G 的一个 Hamilton 有向圈。存在 Hamilton 有 向圈的有向图称为 Hamilton 有向图。 定理 8.4.1 非平凡弱连通有向图 G 是 Euler 有向图的充分必要条件是对任何v VG ∈ ( ) ，都 有dv dv () () + − =