組合せとグラフの理論(塩田)第5回 (4) 有向グラフのオイラー性

有向グラフのオイラー性

 有向グラフでは弧の向きに従って一筆描きを考えます。 (一方通行が指定されている道路をイメージしてください。)
Def.16 有向グラフの頂点 $v$ に対し、その入出次数とは
  • 入次数 $\mbox{indeg}(v)=$ ( $v$ に入る弧の本数 )
  • 出次数 $\mbox{outdeg}(v)=$ ( $v$ から出る弧の本数 )
では
$\mbox{indeg}(v)=1$, $\qquad\mbox{outdeg}(v)=2$
と数えます。
Th.17 連結な有向グラフ $D$ について
$D$ がオイラーグラフであること
$\qquad\Leftrightarrow$ $D$ のすべての頂点 $v$ で $\mbox{indeg}(v)=\mbox{outdeg}(v)$ が成り立つこと
証明 は無向グラフの場合を若干修正すればできます。ポイントは
  • 有向オイラーサーキットは有向閉路に分けられること
  • 有向閉路では $\mbox{indeg}(v)=\mbox{outdeg}(v)=1$ が成り立つこと
  • Alg.5, Alg.6 は向きを指定しても成り立つこと
です。