图论6-Digraph

Posted on

图论6-Digraph

Conceptions

有向图(directed graph）$D(V;A)$定义为非空有限顶点集$V$和$V$的有序对(箭头，arcs)形成的有限簇$A$；

箭头的第一个顶点为尾(tail),第二个顶点为头(head)，箭头由尾指向头；

有向图消去方向后得到的无向图称作底图(underlying grapg)；

称$D$为简单有向图(simple digraph)，如果 $D$中所有箭头都不一样，且没有自环；

称两个有向图同构(isomorphic)，如果它们的底图同构且箭头保持相同的方向；

有向图$D$的邻接矩阵$A(D)$定义为$A=(a_{ij}){n\times n}$,$a{ij}$为$v_i$指向$v_j$的箭头数；

关联矩阵$M(D)$定义为$M=(m_{ij}){n\times n}$，$m{ij}=1$如果$v_i$是$e_j$的尾,$m_{ij}=-1$如果$v_i$是$e_j$的头；

有向图的迹是指箭头的有限序列；

称有向图为弱连通的，如果它不能表示为两个有向图的并，当且仅当其底图是连通的；

称有向图为强连通的，如果任何两个顶点$u,v$.均有从$u$到$v$的有向路径；

有向图的强连通分量是其最大化的强连通子图；

称图$G$为可定向的(orientable)如果图$G$的每个边可以标定方向使得形成的有向图是强连通的；

称有向图$D$是欧拉图，如果存在闭合迹包含$D$中所有的箭头，这样的迹称作欧拉迹；

对于有向图$D$的顶点$v$,出度(out-degree)$d^+(v)$定义为以$v$为尾的箭头数，入度(in-degree)$d^-(v)$定义为以$v$为头的箭头数；

称顶点$v$为有向图$D$的源点(source)，如果$d^-(v)=0$;

称顶点$v$为有向图$D$的汇点(source)，如果$d^+(v)=0$;

称有向图$D$是哈密顿的(Hamiltonian)，如果存在一个有向圈包括所有顶点；

称有向图$D$是半哈密顿的(semi-Hamiltonian)，如果存在一个有向路径包括所有顶点；

Theorem(Robbin)

对于连通图$G$，若$G$是可定向的当且仅当$G$是2-边连通的,即每条边至少被一个圈包含；

proof:必要性显然，充分性只需按照以下算法标方向即可：

  1. 选取任意一个圈$C$,周期性地表明它的边的方向；

  2. 选取不在$C$中但是和$C$相关联的边$e$；

    $e$不是桥，假设$e$被包含在$C’$中，令$C=C’$，回到1；

Theorem(Handshaking dilemma)

$$
\sum_{v\in V(D)}d^+(v)=\sum_{v\in V(D)}d^-(v)=E(D)
$$

Theorem

连通有向图$D$是欧拉的当且仅当对于$D$中任何顶点$v$均有$d^+(v)=d^-(v)$;

Theorem(Ghouila-Houri)

令有向图$D$是具有$n$个顶点的强连通图；如果$d^+(v)\ge \frac{n}{2},d^-(v)\ge \frac{n}{2}$,则$D$是哈密顿的；

Tourament

竞赛图(tourament)定义为任何两个顶点都有箭头相连的有向图；

Theorem(Redei)

任何非哈密顿的竞赛图$T$都是半哈密顿的；(竞赛图必有哈密顿路)

proof：对顶点数归纳，取$v_n\in T$,由归纳假设，取路径$v_0\to v_1\to \cdots\to v_{n-1}$，若$v_n\to v_0$或$v_{n-1}\to v_n$,直接加在头尾即可；否则存在$i$是最小的满足$v_i\to v_n\to v_{i+1}$的下标，则哈密顿路为$v_0\to v_1\to \cdots v_i\to v_n\to v_{i+1}\to \cdots\to v_{n-1}$;

Theorem(Moon)

竞赛图$D$都是哈密顿的当且仅当$D$是强连通的；

proof:必要性显然，充分性归纳证明更强结论：对于任意$k(3\le k\le n)$，存在长度为$k$的圈；若当前圈之外存在一个顶点对圈既有出边也有入边，找到插入的下标即可得到更长圈；

image-20250113204028589

否则可以划分为对圈只有出边和点集$W$和对圈只有入边的点集$Z$,$W$到$Z$必存在一条入边，考虑去掉圈中一点加入该边即可得到更长圈；

image-20250113204044553