道 (グラフ理論)

グラフ理論における道と閉道の理解

グラフ理論は、頂点と辺の構造を形式的に扱う数学の一分野です。この分野において「道」または「パス」とは、一連の頂点から構成された順序であり、各頂点間には辺が存在することが特徴です。一般に道は無限に続くこともありますが、有限の道には必ず始点と終点があります。これらの特定の頂点は「端子頂点」と呼ばれ、道上の他の頂点は「内部頂点」として知られています。

道のもう一つの特別な形態が「閉道」であり、これは始点と終点が同じ頂点である道を指します。閉道においては、どの頂点を始点と見なすかは選択可能です。道と閉道はグラフ理論の基本概念であり、多くの教科書や論文で詳しく説明されています。具体例として、BondyおよびMurtyの1976年の著書や、Gibbonsの1985年の作品、Diestelの2005年の理論書、Korteらの1990年の研究が挙げられます。これらの資料では、道に関連する多くの進んだアルゴリズムについても触れています。

道のバリエーション

道にはいくつかのタイプが存在します。無向グラフだけでなく、有向グラフにも道が含まれており、常に前の頂点から次の頂点へと辺が向かっています。このような道は「有向道」や「有向閉道」として知られ、特別な名称で呼ばれます。また、単純な道（「単純道」）は、頂点が重複しない道を指し、一般的に始点と終点以外の頂点も一度しか現れない閉道は「単純閉道」と呼ばれます。

最近では、「単純」という形容詞が暗黙のうちに理解されることが多く、したがって「道」と言えば通常は単純道を意味し、「閉道」は単純閉道を指すと考えられています。しかし、文献によって用語の使い方が異なることもあります。例えば、BondyとMurtyの1976年の著書では、頂点が重複する道を「歩道」と表現し、単純道を「道」としています。歩道から辺が重複しないものを「小道」と呼び、小道は頂点の重複は許可されるが、辺が重複しない特性を持っています。

さらに特異な道として、「誘導道」という名前のものがあり、これは道の上で隣接していない頂点間に辺が存在しない場合に用いられます。また、全ての頂点を含む単純閉道は「ハミルトン閉路」と名付けられます。これらの道は、グラフ内の構造を理解する上で非常に重要な要素です。

道の関係性

二つの道が共通の内部頂点を持たない場合、それらは「独立」している、または「内部頂点が互いに素である」と言います。同様に、共通の内部辺を持たない道は「辺素」であると定義されます。これらの関係は、特に複雑なグラフにおける解析において重要な役割を果たします。

道は構成する辺の数を「長さ」と呼び、ただし、同じ辺が複数回出現する場合、それは各々がカウントされます。さらに、頂点が一つしかない道も存在し、その場合は長さはゼロとされます。重み付きグラフの場合、各辺に割り当てられた値を持ち、道に属する辺の重みの総和を道の「重み」として扱います。この際、重み以外にもコストや長さなどの用語が使われることもあります。

グラフ理論における道や閉道の概念は、他の多くの問題を解決する際の基礎となります。最短経路問題や巡回セールスマン問題、中国人郵便配達問題といった具体的な問題に応用され、多様なアルゴリズムの設計や分析に繋がる重要なテーマです。

もう一度検索