有向グラフ

数学、より具体的にはグラフ理論において、有向グラフ(またはダイグラフ) は、有向辺(アークとも呼ばれる)によって接続された頂点の集合で構成されるグラフです。

正式には、有向グラフは順序付き対G = ( V , A )であり、^[1]

• V は、頂点、ノード、またはポイントと呼ばれる要素を持つ集合です。
• A は、弧、有向エッジ（対応するセットがAではなくEと呼ばれる単純なエッジの場合もあります）、矢印、または有向線と呼ばれる頂点の順序付きペアの集合です。

これは通常のグラフや無向グラフとは異なり、後者は通常、エッジ、リンク、またはラインと呼ばれる頂点の順序付けられていないペアで定義されます。

前述の定義では、有向グラフが同じソースノードとターゲットノードを持つ複数の矢印を持つことはできませんが、一部の著者は、有向グラフがそのような複数のアークを持つことを許可する（つまり、アークの集合が多重集合であることを許可する）より広い定義を検討しています。これらのエンティティは、有向マルチグラフ（またはマルチダイグラフ）と呼ばれることがあります。
一方、前述の定義では、有向グラフがループ（つまり、ノードを直接自分自身に接続するアーク）を持つことを許可していますが、一部の著者は、有向グラフがループを持つことを許可しないより狭い定義を検討しています。^{[2]ループのない有向グラフは}単純有向グラフ と呼ばれることがあり、ループのある有向グラフはループダイグラフと呼ばれることがあります（「有向グラフの種類」のセクションを参照）。

• 対称有向グラフは、すべての辺が各方向に 1 つずつ、計 2 回出現する有向グラフです (つまり、有向グラフに属するすべての矢印に対して、対応する逆矢印もその有向グラフに属します)。 (このような辺は「双向」と呼ばれることもあり、このようなグラフは「双向」と呼ばれることもありますが、これは双向グラフの意味と矛盾します。)
• 単純な有向グラフは、ループ（頂点同士を直接つなぐ矢印）がなく、同じソースノードとターゲットノードを持つ複数の矢印がない有向グラフです。すでに紹介したように、複数の矢印がある場合、そのエンティティは通常、有向マルチグラフと呼ばれます。一部の著者は、ループのある有向グラフをループ有向グラフと表現しています。^[2]
  • 完全有向グラフは、各頂点のペアが対称な有向弧のペアで結合されている単純な有向グラフです (これは、辺が逆弧のペアに置き換えられた無向完全グラフに相当します)。したがって、完全有向グラフは対称です。
  • 半完全多部有向グラフは、頂点集合が異なる集合内の頂点xとy のペアごとにxとy の間に弧が存在するような集合に分割された単純な有向グラフである。 xとy の間には 1 つの弧が存在する場合もあれば、反対方向に 2 つの弧が存在する場合もある。^[3]
  • 半完全有向グラフは、各頂点のペアの間に弧がある単純な有向グラフです。すべての半完全有向グラフは、各頂点が分割の集合を構成する、自明な方法で半完全多部有向グラフです。^[4]
  • 準推移的有向グラフは、xからyおよびyからzへの弧を持つ異なる頂点の3 つ組x、y、zごとに、 xとzの間に弧が存在する単純な有向グラフです。 xとzの間には 1 つの弧だけが存在する場合もあれば、反対方向の 2 つの弧が存在する場合もあります。半完全有向グラフは準推移的有向グラフです。準推移的有向グラフの拡張にはk準推移的有向グラフと呼ばれるものがあります。 ^[5]
  • 有向グラフは、有向辺の反対のペアを持たない有向グラフです（つまり、 ( x , y )と( y , x )のうちの1つだけがグラフの矢印になります）。したがって、有向グラフが有向グラフである場合、 2サイクルはありません。 ^[6]このようなグラフは、無向グラフに 方向を適用することで取得できます
    • トーナメントは、無向完全グラフの各辺の方向を選択することで得られる有向グラフである。トーナメントは半完全有向グラフである。 ^[4]
    • 有向グラフは有向閉路を持たない場合非巡回グラフと呼ばれます。このような有向グラフの一般的な名前は有向非巡回グラフ（DAG）です。^[7]
      • マルチツリーは、同じ開始頂点から同じ終了頂点までの 2 つの異なる有向パスが存在しない DAG です。
      • 有向ツリーまたはポリツリーは、ツリー (接続された非循環の無向グラフ) のエッジを方向付けることで形成される DAG です。
        • ルート付きツリーは、基になる無向ツリーのすべてのエッジがルートから離れるかルートに近づくように向いている有向ツリーです (それぞれ、樹状突起またはアウトツリー、およびインツリーと呼ばれます)。

• 重み付き有向グラフ（有向ネットワークとも呼ばれる）は、重み付きグラフ（無向ネットワークまたは重み付きネットワークとも呼ばれる）と同様に、矢印に重みが割り当てられた（単純な）有向グラフです。^[2]
  • フロー ネットワークは、ソースとシンクの2 つのノードが区別される重み付き有向グラフです。
• ルート付き有向グラフ(フロー グラフとも呼ばれる) は、頂点がルートとして区別されている有向グラフです。
  • 制御フロー グラフは、プログラムの実行中にプログラムが通過する可能性のあるパスを表すためにコンピューター サイエンスで使用されるルート付き有向グラフです。
• シグナルフロー グラフは、ノードがシステム変数を表し、ブランチ (エッジ、アーク、または矢印) がノードのペア間の機能的な接続を表す有向グラフです。
• フロー グラフは、一連の線形代数方程式または微分方程式に関連付けられた有向グラフです。
• 状態図は、有限状態マシンを表す有向多重グラフです。
• 可換図は、カテゴリ理論で使用される有向グラフであり、頂点は（数学的な）オブジェクトを表し、矢印は射を表し、同じ開始点と終了点を持つすべての有向パスは、合成によって同じ結果につながるという特性があります。
• リー群の理論において、箙 Q は、関数として定義される表現 V の定義域として機能し、したがってその形状を特徴付ける有向グラフであり、具体的には関数カテゴリFinVct _K ^{F ( Q )}の対象です。ここで、F ( Q ) はQ内のパスからなるQ上の自由カテゴリであり、 FinVct _Kは体K上の有限次元ベクトル空間のカテゴリです。箙の表現では、頂点にベクトル空間のラベルが付けられ、辺 (したがってパス) にはそれらの間の線型変換と互換性があり、自然変換によって変換されます。

弧( x , y )はxから yへ向かうとみなされます。yは弧の先頭、xは末尾と呼ばれます。 yはxの直接の後続、xはyの直接の前続と呼ばれます。パスがxからyにつながる場合、y はxの後続であり、xから到達可能であり、x はyの前続であると言われます。 弧( y , x )は、 ( x , y )の逆弧と呼ばれます。

ループを持つ多重有向グラフの隣接行列は、頂点に対応する行と列を持つ整数値の行列です。ここで、非対角要素a _ijは頂点iから頂点jへの弧の数であり、対角要素a _iiは頂点iのループの数です。有向グラフの隣接行列は論理行列であり、行と列の順列を除いて一意です。

有向グラフの別の行列表現は接続行列です。

詳細な定義については指示を参照してください。

頂点の場合、頂点に隣接する先端の数は頂点の入次数と呼ばれ、頂点に隣接する末端の数は頂点の出次数(ツリーの分岐係数と呼ばれる) と呼ばれます。

G = ( V , E )、v ∈ Vとします。vの入次数はdeg ⁻ ( v )で表され、出次数は deg ⁺ ( v ) で表されます。

deg ⁻ ( v ) = 0の頂点は、そこから出ていく各弧の起点となるため、ソースと呼ばれます。同様に、 deg ⁺ ( v ) = 0の頂点は、そこから入ってくる各弧の終点となるため、 シンクと呼ばれます。

次数和の公式は、有向グラフの場合、

${\displaystyle \sum _{v\in V}\deg ^{-}(v)=\sum _{v\in V}\deg ^{+}(v)=|E|.}$

すべての頂点v∈Vについてdeg + ( ^v ) = deg− ⁽ v )が成立する場合、そのグラフはバランス有向グラフと呼ばれる。^[8]

有向グラフの次数列は、その入次数と出次数のペアのリストです。上記の例では、次数列は ((2, 0), (2, 2), (0, 2), (1, 1)) です。次数列は有向グラフの不変量であるため、同型有向グラフは同じ次数列を持ちます。ただし、次数列は一般に有向グラフを一意に識別するものではありません。場合によっては、同型でない有向グラフが同じ次数列を持つことがあります。

有向グラフ実現問題は、与えられた正の整数ペアのシーケンスの次数シーケンスを持つ有向グラフを見つける問題です。（末尾のゼロのペアは、適切な数の孤立した頂点を有向グラフに追加することで簡単に実現されるため、無視できます。）ある有向グラフの次数シーケンスであるシーケンス、つまり有向グラフ実現問題が解を持つシーケンスは、有向グラフィックまたは有向グラフィカルシーケンスと呼ばれます。この問題は、Kleitman-Wang アルゴリズムまたはFulkerson-Chen-Anstee 定理によって解決できます。

有向グラフが弱連結（または単に連結^[9] ）であるとは、グラフのすべての有向辺を無向辺に置き換えることによって得られる無向基底グラフが連結グラフである場合をいう。

有向グラフが強く連結されている、つまり強いグラフであるとは、頂点のペア( x、y )ごとにxからy (およびyからx )への有向パスが含まれている場合です。強いコンポーネントは、最大限に強く連結されたサブグラフです。

連結されたルート付きグラフ(またはフロー グラフ) は、区別されたルート頂点からすべての頂点への有向パスが存在するグラフです。

• バン・ジェンセン、ヨルゲン。 Gutin、Gregory (2000)、Digraphs: Theory、Algorithms and Applications、Springer、ISBN 1-85233-268-9（2007 年に修正された第 1 版は現在、著者のサイトから無料で入手できます。第 2 版は 2009 年にISBN 1-84800-997-6で出版されました）。 
• バン・ジェンセン、ヨルゲン。 Gutin、Gregory (2018)、有向グラフのクラス、Springer、ISBN 978-3319718408。
• ボンディ、ジョン・エイドリアン、マーティ、USR（1976）、グラフ理論と応用、ノースホランド、ISBN 0-444-19451-7。
• ディーステル、ラインハルト（2005）、グラフ理論（第3版）、シュプリンガー、ISBN 3-540-26182-6（電子版第3版は著者のサイトから無料で入手できます）。
• ハラリー、フランク、ノーマン、ロバート Z.、カートライト、ドーウィン (1965)、構造モデル: 有向グラフ理論入門、ニューヨーク: ワイリー。
• オンライン整数列百科事典のn 個のノードを持つ有向グラフ (または有向グラフ) の数

ウィキメディア・コモンズには、有向グラフに関連するメディアがあります。