有向グラフ

OR事典

有向グラフ

読み方：ゆうこうぐらふ
【英】：directed graph

枝が向きをもつ通常のグラフを無向グラフと対比して示したいとき, これを有向グラフという.

「OR事典」の他の用語

グラフ･ネットワーク：

最小費用フロー問題  最短路問題  最近近傍法  有向グラフ  木  枝  点

ウィキペディア小見出し辞書

有向グラフ

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/05/21 05:56 UTC 版)

「隣接行列」の記事における「有向グラフ」の解説

有向グラフでは、頂点の入次数は対応する列の成分の和を取ることによって計算でき、出次数は対応する行の成分の和を取ることによって計算できる。 ラベル付きグラフ隣接行列S4の有向ケイリーグラフ 座標は0–23。グラフが有向であるため、隣接行列は必ずしも対称ではない。

有向グラフ

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/05/27 05:59 UTC 版)

「DOT言語」の記事における「有向グラフ」の解説

フローチャートや木構造のような有向グラフも、無向グラフと同様に記述できる。記述の仕方は無向グラフとほとんど同じだが、記述を始めるところに置くキーワードは graph ではなく digraph であり、二重ハイフンの代わりに -> でエッジを示す。 digraph graphname { a -> b -> c; b -> d; }

有向グラフ

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/10/12 14:26 UTC 版)

「グラフ (離散数学)」の記事における「有向グラフ」の解説

詳細は「有向グラフ」および「:en:Directed graph」を参照 有向グラフ (directed graph, digraph) は、辺に向きがあるグラフである。 限定的だが非常に一般的な意味において、有向グラフは以下の条件を満たす対 G = ( V , E ) として定義される。 V は、頂点の集合 E ⊆ { ( x , y ) ∣ ( x , y ) ∈ V 2 and x ≠ y } は辺の集合で、辺（有向辺とも言う）は頂点の順序対である。つまり1辺が異なる2頂点と関連している。 曖昧さを避けるため、この種類のグラフは厳密に「単純有向グラフ (directed simple graph)」と呼ぶ場合もある。 辺 ( x , y ) は x から y の向きを表し、頂点 x と y はその辺の「端点」であるが、 x は辺の「始点 (tail)」そして y は辺の「終点 (head)」という。辺は x と y を「結び」、 x と y に「接続する」と表現される。頂点は、グラフ内にあっても辺を持たない場合もある。辺 ( y , x ) は ( x , y ) の「逆向辺 (inverted edge)」と呼ばれる。「多重辺」は、上述の定義だと許されないが、同じ始点と終点を持つ辺が複数あるものを言う。 多重辺を許す条件のより一般的な意味で、有向グラフは以下によって構成される順序三つ組 G = ( V , E , ϕ ) として定義される。 V は、頂点の集合 E は、辺（有向辺とも言う）の集合 ϕ : E → { ( x , y ) ∣ ( x , y ) ∈ V 2 and x ≠ y } は全ての辺を頂点の順序対に写す写像「接続関数 (incidence function)」である。 曖昧さを避けるため、この種類のグラフは厳密に「多重有向グラフ(directed multigraph)」と呼ぶ場合もある。 「ループ」は始点と終点が同一な辺である。上述の2種類の定義においては有向グラフはループを持つことができない、なぜなら、辺 ( x , y ) の定義に x ≠ y の条件があるので、頂点 x と自分自身を結ぶループ（すなわち ( x , x ) ）は辺の定義を満たさないためである。そのためループを許すには定義を拡張させる必要がある。有向単純グラフに対しては E の定義を E ⊆ { ( x , y ) ∣ ( x , y ) ∈ V 2 } と修正し、有向多重グラフに対しては ϕ の定義を ϕ : E → { ( x , y ) ∣ ( x , y ) ∈ V 2 } と修正することになる。曖昧さを避けるため、これらの種類のグラフは厳密にそれぞれ「ループを許す単純有向グラフ (directed simple graph permitting loops)」そして「ループを許す多重有向グラフ（またはクイバー）」と呼ばれる場合もある。 ループを許す単純有向グラフ G において、辺は G の頂点に関する自己関係を成す。これを ∼ と表し、 G の「隣接関係」と呼ぶ。具体的には、各辺 ( x , y ) について、その端点 x と y は互いに「隣接する」と言い、 x ∼ y と表記される。

有向グラフ

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/01/02 08:06 UTC 版)

「グラフ理論」の記事における「有向グラフ」の解説

集合 V , E と、E の元（げん、要素）に、二つの V を元の対で対応させる写像 f :   E → V × V の三つ組 G := ( f , V , E ) を有向グラフという。V の元を G の頂点またはノード、E の元を G の辺または弧と呼ぶ。f(e)=(v, v)となるe∈Eはループに対応し、f(a)=f(b)となるa,b∈Eは多重辺に対応する。

有向グラフ

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/04/11 14:38 UTC 版)

「双対グラフ」の記事における「有向グラフ」の解説

有向平面グラフの双対グラフは、各双対辺を対応する主辺から時計回りに90°回転させることによって、同様に指向させることができる。ただしこれは厳密に言えば双対ではない。なぜならば、グラフGから出発し、双対を二回とったとき、G自体に戻らず、Gの転置グラフ（Gの全てのエッジを反転させたグラフ）と同型なグラフになるからである。この定義の双対では、双対を4回取ると元のグラフに戻る。

有向グラフ

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/11/26 00:49 UTC 版)

「状態遷移図」の記事における「有向グラフ」の解説

有限オートマトンの状態遷移図の古典的な形式は有向グラフであり、以下のような形式である。 各辺（エッジ）はふたつの状態の間の遷移を表す。ムーア・マシンでは各エッジに入力を付記する。 ミーリ・マシンでは各エッジに入力と出力を付記する。 各頂点（ノード）は状態を表す。ムーア・マシンでは各状態に出力を付記する。 一般には、頂点（ノード）は円で描かれ、必要ならば受容状態は二重円を使用する。