Loading article…
グラフ理論では、グラフ内のパスは、ほとんどの定義ではすべて異なる（頂点が異なっているため、エッジも異なっている）頂点のシーケンスを結合する有限または無限のエッジのシーケンスです。有向グラフの有向パス（ディパス[1]と呼ばれることもあります）は、異なる頂点のシーケンスを結合する有限または無限のエッジのシーケンスですが、エッジがすべて同じ方向に向いているという追加の制限があります。
パスはグラフ理論の基本的な概念であり、ほとんどのグラフ理論のテキストの導入部で説明されています。たとえば、Bondy & Murty (1976)、Gibbons (1985)、Diestel (2005) を参照してください。Korte ら (1990) は、グラフ内のパスに関するより高度なアルゴリズムのトピックを扱っています。
定義
散歩道、トレイル、小道
- G = ( V , E , ϕ )をグラフとします。有限ウォークは、エッジのシーケンス( e 1 、 e 2 、 …、e n − 1 )と、 i = 1、2 、…、 n − 1に対してϕ ( e i ) = { v i、v i + 1 }となる頂点のシーケンス( v 1 、 v 2 、… 、 v n ) です。 ( v 1 、v 2、… 、v n )はウォークの頂点シーケンスです。v 1 = v nの場合、ウォークは閉じて おり、それ以外の場合は開いています。無限ウォークは、ここで説明したのと同じタイプのエッジのシーケンスですが、最初または最後の頂点がなく、半無限ウォーク (またはレイ) には最初の頂点がありますが、最後の頂点はありません。
- トレイルとは、すべての端が明確に区別される散歩道のことである。[2]
- パスとは、すべての頂点（したがってすべての辺）が明確に区別される経路のことである。[2]
w = ( e 1 , e 2 , …, e n − 1 )が頂点シーケンス( v 1 , v 2 , …, v n )を持つ有限ウォークである場合、wはv 1からv nへのウォーク であると言われます。トレイルやパスについても同様です。2 つの異なる頂点間に有限ウォークがある場合、それらの間には有限のトレイルと有限のパスも存在します。
一部の著者は、パスのすべての頂点が別個である必要はなく、代わりに、すべての頂点が別個であるパスを指すために 「単純パス」という用語を使用します。
重み付きグラフは、グラフ内のすべてのエッジに値 (重み) を関連付けます。重み付きグラフ内のウォーク (またはトレイルまたはパス) の重みは、通過したエッジの重みの合計です。重みの代わりにコストや長さという言葉が使用されることもあります。
指示された散歩道、指示された道、指示された道
- G = ( V , E , ϕ )を有向グラフとする。有限有向ウォークは、頂点のシーケンス( v 1 , v 2 , … , v n ) が存在するエッジのシーケンス ( e 1 , e 2 , … , e n − 1 )であり、i = 1 , 2 , … , n − 1に対してϕ ( e i ) = ( v i , v i + 1 ) が成立する。 ( v 1 , v 2 , … , v n )は、有向ウォークの 頂点シーケンスである。 v 1 = v nの場合、有向ウォークは閉じており、それ以外の場合は開いている。無限有向ウォークは、ここで説明したのと同じタイプのエッジのシーケンスだが、最初または最後の頂点がなく、半無限有向ウォーク (またはレイ) には最初の頂点はあるものの最後の頂点がない。
- 有向トレイルとは、すべてのエッジが明確に区別される有向ウォークである。[2]
- 有向パスとは、すべての頂点が異なる有向パスである。[2]
w = ( e 1 , e 2 , …, e n − 1 )が頂点シーケンス( v 1 , v 2 , …, v n )を持つ有限有向ウォークである場合、wはv 1から v nへのウォークであると言われます。有向トレイルまたはパスについても同様です。 2 つの異なる頂点間に有限有向ウォークがある場合、それらの間には有限有向トレイルと有限有向パスも存在します。
「単純な有向パス」とは、すべての頂点が異なるパスです。
重み付き有向グラフは、有向グラフ内のすべてのエッジに値 (重み) を関連付けます。重み付き有向グラフ内の有向ウォーク (またはトレイル、パス) の重みは、横断されたエッジの重みの合計です。重みの代わりに コストや長さという言葉が使用されることもあります。
例
- 各頂点のペアを含むパスが存在する場合、グラフは接続されています。
- 有向グラフは、各頂点のペアを含む反対方向の有向パスがある場合に強く連結されます。
- 2 つの連続しないパス頂点を接続するグラフ エッジがないパスは、誘導パスと呼ばれます。
- グラフのすべての頂点を繰り返しなく含むパスは、ハミルトン パスと呼ばれます。
- 2 つのパスに共通の内部頂点またはエッジがない場合、それらのパスは頂点独立(または、内部的に分離、または内部的に頂点分離) です。同様に、2 つのパスに共通のエッジがない場合、それらのパスはエッジ独立(またはエッジ分離) です。内部的に分離している 2 つのパスはエッジ分離ですが、その逆は必ずしも真ではありません。
- グラフ内の 2 つの頂点間の距離は、それらの間の最短経路が存在する場合はその最短経路の長さであり、存在しない場合は距離は無限大です。
- 接続されたグラフの直径は、グラフの頂点のペア間の最大距離 (上記で定義) です。
パスを見つける
グラフ内の最短経路と最長経路を見つけるためのアルゴリズムはいくつか存在しますが、重要な違いは、前者の問題は後者よりも計算上はるかに簡単であるという点です。
ダイクストラのアルゴリズムは、非負のエッジ重み（またはエッジ重みなし）を持つ有向グラフと無向グラフ内のソース頂点から他のすべての頂点までの最短経路のリストを生成しますが、ベルマン・フォードのアルゴリズムは、負のエッジ重みを持つ有向グラフに適用できます。フロイド・ワーシャルのアルゴリズムは、重み付き有向グラフ内のすべての頂点ペア間の最短経路を見つけるために使用できます。
パス分割問題
kパス分割問題とは、与えられたグラフを長さが最大kの頂点が互いに素なパスの最小集合に分割する問題である。[3]
参照
注記
参考文献
- Bender, Edward A.; Williamson, S. Gill (2010) リスト、決定、グラフ。確率入門付き。
- Bondy, JA; Murty, USR (1976)。グラフ理論とその応用。ノースホランド。p. 12-21。ISBN 0-444-19451-7。
- ディーゼル、ラインハルト (2005)。グラフ理論。スプリンガー・フェルラーク。 6～9ページ。ISBN 3-540-26182-6。
- ギボンズ, A. (1985).アルゴリズムグラフ理論. ケンブリッジ大学出版局. pp. 5–6. ISBN 0-521-28881-9。
- Corte, ベルンハルト; Lovász, ラスロー;プロメル、ハンス・ユルゲン。シュライバー、アレクサンダー(1990)。パス、フロー、および VLSI レイアウト。スプリンガー・フェルラーク。ISBN 0-387-52685-4。
- McCuaig, William (1992)。「Intercyclic Digraphs」。Robertson, Neil、Seymour, Paul (編)。グラフ構造理論。AMS–IMS–SIAM Joint Summer Research Conference on Graph Minors、シアトル、1991 年 6 月 22 日～7 月 5 日。アメリカ数学会。p. 205。