オリエンテーション（グラフ理論）

グラフ理論では、無向グラフの方向付けは、各辺に方向を割り当てて、最初のグラフを有向グラフに変換することです。

有向グラフ

有向グラフは、頂点のペアのいずれもが2つの相互に対称な辺で結ばれていない場合、有向グラフと呼ばれます。有向グラフの中で、有向グラフは2サイクルを持たないグラフです（つまり、 $(x, y)$ と $(y, x)$ のどちらか1つだけがグラフの矢印になります）。^[1]

トーナメントは完全グラフの方向です。ポリツリーは無向木の方向です。^[2] サムナーの予想によれば、2n-2 個の頂点を持つすべてのトーナメントには $、 n$ $個の頂点を$ $持つ$ すべてのポリツリーが含まれます。^[3]

$n$ 頂点（ $n$ $= 1, 2, 3, \dots$ ）を持つ非同型有向グラフの数は

1、2、7、42、582、21480、2142288、575016219、415939243032、…（OEISの配列A001174）。

トーナメントは、完全有向グラフ（異なる頂点のペアごとに一方向または両方向に有向辺があるグラフ）と一対一に対応している。完全有向グラフは、2 サイクルをすべて削除することで有向グラフに変換でき、逆に有向グラフは、辺の端点ではない頂点のペアごとに 2 サイクルを追加することで完全有向グラフに変換できる。これらの対応は一対一である。したがって、同じ数列は、完全有向グラフのグラフ列挙問題も解決する。この数列の数には、明示的だが複雑な式がある。^[4]

制約された方向

強い配向とは、強く連結したグラフになる配向である。密接に関連する完全巡回配向は、すべての辺が少なくとも 1 つの単純閉路に属する配向である。無向グラフ $Gの配向は、$ $G$ のすべての連結成分の強い配向である場合に限り、完全巡回である。ロビンズの定理によれば、グラフが強い配向を持つのは、2 辺連結である場合に限り、である。連結されていないグラフは、ブリッジがない場合に限り、完全巡回配向を持つことがある。^[5]

非巡回配向は、有向非巡回グラフをもたらす配向である。すべてのグラフには非巡回配向がある。すべての非巡回配向は、頂点をシーケンスに配置し、各辺をシーケンス内の前の端点から後の端点に向けることで得られる。ガライ・ハッセ・ロイ・ヴィタバー定理は、グラフには非巡回配向があり、最長パスの頂点の数は最大で $kであり、$ 色付けできるのは最大で $k$ 色である場合に限る、と述べている。^{[6]非巡回配向と完全巡回配向は、}平面双対性によって互いに関連している。単一のソースと単一のシンクを備えた非巡回配向は、双極配向と呼ばれる。^[7]

推移的方向とは、結果として得られる有向グラフがそれ自身の推移閉包となるような方向である。推移的方向を持つグラフは比較可能性グラフと呼ばれ、半順序集合から、半順序で比較可能な2つの要素を隣接させることによって定義できる。 ^[8]推移的方向は、もし存在するなら、線形時間で見つけることができる。^{[9]しかし、結果として得られる方向（または任意の方向）が実際に推移的であるかどうかをテストするには、}行列の乗算と同等の複雑さであるため、より多くの時間が必要となる。

無向グラフのオイラー配向は、各頂点の入次数と出次数が等しい配向である。グリッドグラフのオイラー配向は、統計力学における氷型モデルの理論で生じる。^[10]

パフィアン配向は、グラフ内の特定の偶数長サイクルが、サイクルの周りの2つの方向のそれぞれに奇数の辺を向けているという性質を持つ。これらは平面グラフでは常に存在するが、他の特定のグラフでは存在しない。これらは、完全マッチングを数えるFKTアルゴリズムで使用されている。 ^[11]

参照

コネックス関係

参考文献

^ Diestel, Reinhard (2005)、「1.10 グラフのその他の概念」、グラフ理論(PDF) (第3版)、Springer、ISBN 978-3-540-26182-7。
^ Rebane, George; Pearl, Judea (1987)、「統計データからの因果多木構造の復元」、人工知能における不確実性に関する第3回年次会議 (UAI 1987)、シアトル、ワシントン州、米国、1987年7月、pp. 222–228、arXiv : 1304.2736。
^ Sumner の Universal Tournament Conjecture、Douglas B. West、2012 年 8 月 2 日閲覧。
^ ハラリー、フランク、パーマー、エドガー M. (1973)、「Formula 5.4.13」、Graphical Enumeration、ニューヨーク：アカデミックプレス、p. 133、MR 0357214。
^ Robbins, HE (1939)、「グラフに関する定理と交通管制問題への応用」、アメリカ数学月刊誌、46 (5): 281–283、doi :10.2307/2303897、hdl : 10338.dmlcz/101517、JSTOR 2303897。
^ Nešetřil, Jaroslav ; Ossona de Mendez, Patrice (2012)、「定理 3.13」、Sparsity: Graphs, Structures, and Algorithms、Algorithms and Combinatorics、vol. 28、Heidelberg: Springer、p. 42、doi :10.1007/978-3-642-27875-4、ISBN 978-3-642-27874-7、MR 2920058。
^ de Fraysseix, Hubert; Ossona de Mendez, Patrice ; Rosenstiehl, Pierre (1995)、「双極性配向の再考」、離散応用数学、56 (2–3): 157–179、doi : 10.1016/0166-218X(94)00085-R、MR 1318743。
^ Ghouila-Houri、Alain (1962)、「Caractérisation desgraphes non orientés dont on peut orienter les arrêtes de manière à obtenir legraphe d'une relationship d'ordre」、Les Comptes rendus de l'Académie des Sciences、254 : 1370 –1371、MR 0172275。
^ McConnell, RM; Spinrad, J. (1997)、「線形時間推移的指向」、第 8 回 ACM-SIAM 離散アルゴリズムシンポジウム、pp. 19–25。
^ Mihail, M.; Winkler, P. (1996)、「グラフのオイラー方向の数について」、Algorithmica、16 (4–5): 402–414、doi :10.1007/s004539900057、MR 1407581。
^ Thomas, Robin (2006)、「グラフのパフィアン方向の調査」(PDF)、国際数学者会議第3巻、Eur. Math. Soc.、チューリッヒ、pp. 963–984、doi :10.4171/022-3/47、ISBN 978-3-03719-022-7、MR 2275714

外部リンク

ワイスタイン、エリック W.、「グラフの向き」、MathWorld
ワイスシュタイン、エリック W.、「有向グラフ」、MathWorld

[1] Diestel, Reinhard (2005)、「1.10 グラフのその他の概念」、グラフ理論(PDF) (第3版)、Springer、ISBN 978-3-540-26182-7。

[2] Rebane, George; Pearl, Judea (1987)、「統計データからの因果多木構造の復元」、人工知能における不確実性に関する第3回年次会議 (UAI 1987)、シアトル、ワシントン州、米国、1987年7月、pp. 222–228、arXiv : 1304.2736。

[3] Sumner の Universal Tournament Conjecture、Douglas B. West、2012 年 8 月 2 日閲覧。

[4] ハラリー、フランク、パーマー、エドガー M. (1973)、「Formula 5.4.13」、Graphical Enumeration、ニューヨーク：アカデミックプレス、p. 133、MR 0357214。

[5] Robbins, HE (1939)、「グラフに関する定理と交通管制問題への応用」、アメリカ数学月刊誌、46 (5): 281–283、doi :10.2307/2303897、hdl : 10338.dmlcz/101517、JSTOR 2303897。

[6] Nešetřil, Jaroslav ; Ossona de Mendez, Patrice (2012)、「定理 3.13」、Sparsity: Graphs, Structures, and Algorithms、Algorithms and Combinatorics、vol. 28、Heidelberg: Springer、p. 42、doi :10.1007/978-3-642-27875-4、ISBN 978-3-642-27874-7、MR 2920058。

[7] Fraysseix, Hubert; Ossona de Mendez, Patrice ; Rosenstiehl, Pierre (1995)、「双極性配向の再考」、離散応用数学、56 (2–3): 157–179、doi : 10.1016/0166-218X(94)00085-R、MR 1318743。

[8] Ghouila-Houri、Alain (1962)、「Caractérisation desgraphes non orientés dont on peut orienter les arrêtes de manière à obtenir legraphe d'une relationship d'ordre」、Les Comptes rendus de l'Académie des Sciences、254 : 1370 –1371、MR 0172275。

[9] McConnell, RM; Spinrad, J. (1997)、「線形時間推移的指向」、第 8 回 ACM-SIAM 離散アルゴリズムシンポジウム、pp. 19–25。

[10] Mihail, M.; Winkler, P. (1996)、「グラフのオイラー方向の数について」、Algorithmica、16 (4–5): 402–414、doi :10.1007/s004539900057、MR 1407581。

[11] Thomas, Robin (2006)、「グラフのパフィアン方向の調査」(PDF)、国際数学者会議第3巻、Eur. Math. Soc.、チューリッヒ、pp. 963–984、doi :10.4171/022-3/47、ISBN 978-3-03719-022-7、MR 2275714