有向グラフ

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

意味

正式には、有向グラフは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上のパスからなる自由カテゴリであり、FinVct _Kは体K上の有限次元ベクトル空間のカテゴリです。Q の表現では、頂点にベクトル空間、辺（つまりパス）にそれらの間の線型変換と互換性のあるラベルを付け、自然変換によって変換します。

基本用語

弧( 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 \in V$ とする。 vの入次数は deg ⁻ ( v )で表され、出次数は deg ⁺ ( v ) で表されます。

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

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

\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 ）への有向パスを含む場合、強連結または強連結である。強連結成分は、最大強連結部分グラフである。

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

参照

二項関係 – 2つの集合の要素間の関係
コーツグラフ – 線形システムを解くための数学グラフ
有向グラフマークアップ言語
DRAKONフローチャート – アルゴリズムマッピングツール
フローチャート – ワークフローまたはプロセスを表す図
球状集合
グラフ理論用語集
グラフデータベース – クエリにグラフ構造を使用するデータベース
グラフスタイルシート – 数学とコンピューティングのフレームワーク
グラフ理論 – 離散数学の分野
グラフ（抽象データ型） - コンピュータサイエンスにおける抽象データ型
ネットワーク理論 – 離散オブジェクト間の関係を表現するグラフの研究
方向付け（グラフ理論） - 無向グラフの辺に方向を割り当てる
先行順序 – 反射的および推移的な二項関係
位相ソート – 有向非巡回グラフのノード順序付け
転置グラフ – エッジが反転した有向グラフ
垂直制約グラフ
ゼロ重量サイクル問題

注記

^ バン＝ジェンセンとグーティン (2000)。 Bang-Jensen & Gutin (2018)、第 1 章。Diestel (2005)、セクション 1.10。ボンディ＆マーティ (1976)、セクション 10。
^ abc チャートランド、ゲイリー（1977年）『グラフ理論入門』クーリエ社、ISBN 9780486247755. 2023年2月4日時点のオリジナルよりアーカイブ。2020年10月2日閲覧。
^ Bang-Jensen & Gutin (2018)、第7章、Yeo著。
^ ab Bang-Jensen & Gutin (2018)、第 2 章、Bang-Jensen と Havet 著。
^ Bang-Jensen & Gutin (2018)、第8章、Galeana-SanchezとHernandez-Cruz著。
^ Diestel（2005）、セクション1.10。
^ Bang-Jensen & Gutin (2018)、第 3 章、Gutin 著。
^ サティヤナラーヤナ、バヴァナリ; Prasad、Kuncham Syam、離散数学とグラフ理論、PHI Learning Pvt.株式会社、p. 460、ISBN 978-81-203-3842-5; Brualdi, Richard A. (2006), 組み合わせ行列クラス, 数学とその応用百科事典, 第108巻, Cambridge University Press, p. 51, ISBN 978-0-521-86565-4。
^ Bang-Jensen & Gutin (2000) 2007年版では19ページ、第2版（2009年）では20ページ。

参考文献

バン・ジェンセン、ヨルゲン。 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個のノードを持つ有向グラフ（または有向グラフ）の数

外部リンク

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