0%

【知识总结】 有向图

有序对

  • 无序对:
    • 含有1个或2个元素的集合
    • $(v_1,v_2)=\{v_1,v_2\}$,$(v_2,v_2)={v_2}$
  • 有序对:$\langle a_1,b_1\rangle=\langle a_2,b_2\rangle$ 当且仅当 $a_1=a_2$ 且 $b_1=b_2$
  • 有序对的集合表示:$\langle a,b\rangle=\{\{a\},\{a,b\}\}$

有向图和弧

  • $G=\langle V,A \rangle$
    • $V$:顶点集
    • $A$:弧集,一个有向对的集合。弧又称为有向边
  • 一些术语
    • 弧的尾
    • 弧的头
    • 环弧:头尾相同的弧
    • 并行弧:具有相同头的相同尾的弧
    • 简单有向图:无环弧,无并行弧
    • 反向弧:简单有向图中头尾相反的弧

度和邻点

  • 出度:$d^+(v)$
  • 入度:$d^-(v)$
  • 最小出度:$\delta^+$
  • 最小入度:$\delta^-$
  • 最大出度:$\Delta^+$
  • 最大入度:$\Delta^-$
  • 出邻点和入邻点

定理

对任何有向图$G$,都有$\sum\limits_{v\in V(G)}d^+(v)=\sum\limits_{v\in V(G)}d^-(v)=\sum\limits_{v\in V(G)}\frac{d(v)}{2}=\epsilon$

途径、迹、路、圈

  • 有向途径
    • 顶点和弧交替出现的序列
    • 与弧的方向一致
  • 有向迹:弧不重复出现
  • 有向路:顶点不重复出现
  • 有向圈:起点和终点相同

底图和定向

  • 底图:有向图 $\rightarrow$ 无向图
  • 定向:无向图 $\rightarrow$ 有向图
    • 不唯一
    • 竞赛图:完全图的定向

连通

  • 弱连通:底图是连通的
  • 强连通:任取顶点u和v,存在从u到v的有向路
  • 强连通分支:极大强连通子图
  • 强连通分支之间不存在公共顶点
  • 强连通分支图不存在有向圈

强连通的充要条件

$G$是强连通有向图的充要条件是$G$的所有顶点在一条有向闭途径上

强连通定向

无向图$G$可定向成强连通图的充分必要条件为:$G$连通且无割边。

竞赛图

    • 到其他任何顶点都有长度不超过2的有向路
    • 不一定唯一
  • 定理:竞赛图中出度最大的顶点一定是王
  • 竞赛图中一个顶点$v$是唯一的王当且仅当$v$的出度是$v-1$