有向グラフ 数学 、特にグラフ理論 において、有向グラフ （またはダイグラフ ）とは、有向辺 （しばしば弧と呼ばれる）で接続された 頂点 の集合から構成されるグラフ のことである。
意味 形式的には、有向グラフは順序対G = ( V , A )[ 1 ]
Vは、 頂点 ノード 、または点 と呼ばれる要素 からなる集合 です。Aは、 弧 、有向辺 （場合によっては、対応する集合がA の代わりにEと名付けられた単に 辺 ）、矢印 、または有向線 と呼ばれる頂点の順序対 の集合です。これは、通常の無向グラフとは異なり、後者は頂点の 順序付けされていないペア によって定義され、それらは通常、エッジ 、リンク 、または線 と呼ばれます。
前述の定義では、有向グラフが同じ始点ノードと終点ノードを持つ複数の矢印を持つことは許可されていませんが、一部の著者は、有向グラフがそのような複数の弧を持つことを許可するより広い定義を検討しています（つまり、弧の集合が多重集合 であることを許可しています）。これらのエンティティは、有向多重グラフ 多重ダイグラフ ）と呼ばれることがあります。 一方、前述の定義では、有向グラフがループ （つまり、ノードを自身に直接接続する弧）を持つことが許可されていますが、一部の著者は、有向グラフがループを持つことを許可しないより狭い定義を検討しています。[ 2 ] 単純有向グラフ と呼ばれることがあり、ループのある有向グラフはループダイグラフと呼ばれることがあります（ 有向グラフの種類 セクションを参照）。
有向グラフの種類
サブクラス 単純な有向非巡回グラフ 4つの頂点におけるトーナメント 対称有向グラフ とは、すべての辺が各方向に2回ずつ現れる有向グラフのことである（つまり、有向グラフに属するすべての矢印に対して、対応する逆方向の矢印も存在する）。（このような辺は「双方向」と呼ばれることもあり、このようなグラフも「双方向」と呼ばれることがあるが、これは双方向グラフ の意味と矛盾する。）単純有向グラフは、 ループ （頂点同士を直接接続する矢印）がなく、始点と終点が同じ矢印が複数存在しない有向グラフです。既に述べたように、矢印が複数存在する場合は、通常、有向多重グラフ と呼ばれます。ループを持つ有向グラフをループ有向グラフ と呼ぶ著者もいます。[ 2 ] 完全有向グラフは 、各頂点のペアが対称的な有向弧のペアで結ばれた単純有向グラフである（これは、辺が逆弧のペアに置き換えられた無向完全グラフ に相当する）。したがって、完全有向グラフは対称である。半完全多部有向グラフは 、 頂点集合が、異なる集合に属する任意の頂点ペア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 ） のうち、グラフの矢印となるのはせいぜい一方である）。したがって、有向グラフが有向グラフであるのは、 2サイクルを 持たない場合に限る。 [ 6 ] 方向付けを 適用することによって得られるトーナメントは 、無向完全グラフ の各辺に方向を選択することによって得られる有向グラフです。トーナメントは半完全有向グラフです。 [ 4 ] 有向グラフは、有向サイクル を持たない場合、非巡回グラフ と呼ばれます。このような有向グラフの一般的な名称は、有向非巡回グラフ [ 7 ] マルチツリー 有向木 多木は 、木（連結された非巡回無向グラフ）のエッジに方向を付けることによって形成される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 ) = 0 の頂点は、そこから出るすべての弧の始点であるため、ソース と呼ばれます。同様に、 deg + ( v ) = 0 の頂点は、そこから入るすべての弧の終点であるため、シンク と呼ばれます。
次数和の公式 によれば、有向グラフの場合、
∑ v ∈ V 度 − （ v ） = ∑ v ∈ V 度 + （ v ） = | E | 。 {\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 。ISBN） 1-84800-997-6 )バン・ジェンセン、ヨルゲン。 Gutin、Gregory (2018)、有向グラフのクラス 、Springer 、ISBN 978-3319718408 Bondy, John Adrian ; Murty, USR (1976), Graph Theory with Applications ISBN 0-444-19451-7 Diestel, Reinhard (2005),グラフ理論 （第3 版）, Springer , ISBN 3-540-26182-6 ハラリー、フランク ；ノーマン、ロバート・Z；カートライト、ドーウィン（1965）、『構造モデル：有向グラフ理論入門』 、ニューヨーク：ワイリーオンライン整数列百科事典 より、n個のノードを持つ有向グラフ（または有向グラフ）の数
