1. 序章

グラフは、複数の柔軟な用途を持つデータ構造です。 実際には、人々の関係から道路ルートまでを定義でき、いくつかのシナリオで使用できます。

いくつかのデータ構造により、隣接行列やエッジリストなどのグラフを作成できます。 また、グラフを定義するさまざまなプロパティを識別できます。 このようなプロパティの例は、エッジ計量およびグラフ密度です。

さらに、ノード間の接続に応じて、グラフの特定の分類と区別があります。 この場合、エッジがノードとどのように関連しているかを考慮して、特定のシーケンスを形成します。

したがって、このチュートリアルでは、グラフのノード間の接続に関連するシーケンスについて詳しく説明します。 まず、グラフの基本的な概念について簡単に説明します。 そこで、パス、回路、サイクルの理論を研究します。 散歩やトレイルについても簡潔に説明します。 最後に、概念を体系的な要約にまとめます。

2. グラフの基本

グラフは、ノード（頂点とも呼ばれます）とエッジによって形成されるデータ構造です。 ノードはグラフの基本的な要素です。 実際、ノードはグラフ内の特定のオブジェクトを抽象化したものです。

実際には、少なくとも1つのノードが含まれている場合、データ構造をグラフとして識別します。 ただし、ノードがなく、その結果、頂点がないグラフは、多くの場合、空グラフと呼ばれます。

エッジは、グラフの2つのノード間の接続です。 グラフでは、エッジはオプションです。 これは、エッジのないグラフを問題なく具体的に識別できることを意味します。 特に、ノードがあり、些細なグラフのエッジがないグラフを呼び出します。

したがって、グラフの従来の表記法は、V（頂点）とE（エッジ）の2つのセットで構成されます。 このようにして、一般的なグラフをG =（V、E）として表すことができます。

次の画像は、単純で一般的なグラフを示しています。

3. 道

実際には、パスは、グラフに存在するエッジを介して接続された、繰り返されないノードのシーケンスです。 パスは、最初と最後のノードの次数が1で、他のノードの次数が2であるグラフとして理解できます。

グラフに有向エッジが含まれている場合、パスはしばしばダイパスと呼ばれます。 したがって、前述のプロパティに加えて、ダイパスはすべてのエッジが同じ方向にある必要があります。

次の画像は、パスとダイパスの特定の例を示しています。

グラフの利用可能なパスを分析することにより、いくつかの結論を引き出すことができます。

  • 任意の2つのノード間に無向パス（有向グラフの方向を無視）がある場合、グラフは少なくとも弱く接続されます
  • 有向グラフが利用可能なパスごとに反対方向のパスを提供する場合、グラフは強く接続されています
  • グラフ内の2つのノード間に1つ以上のパスがある場合、これらのノード間の距離は最短パスの長さです（それ以外の場合、距離は無限大です）

4. 回路

回路は、同じノードで開始および終了する隣接ノードのシーケンスです。 回路がエッジを繰り返すことはありません。 ただし、シーケンス内のノードの繰り返しは許可されます。

特定の特性を持つ回路には、次の2つの特定のカテゴリがあります。

  • オイラー：この回路は、グラフのすべてのエッジを1回だけ訪問する閉じたパスで構成されています
  • ハミルトニアン：この回路は、グラフのすべてのノードに1回だけアクセスする閉じたパスです。

次の画像は、オイラーとハミルトニアンのグラフと回路を例示しています。

前に示した画像では、最初のグラフ（ハミルトニアン回路を含む）はハミルトニアンと非オイラーグラフであることに注意してください。 したがって、それを使用してオイラー回路を作成する方法はありません。

同様に、2番目のグラフ（オイラー回路を含む）は、オイラーグラフと非ハミルトングラフで構成されています。 したがって、その上に可能なハミルトン閉路はありません。

5. サイクル

サイクルは、グラフ内の隣接する個別のノードのシーケンスで構成されます。 唯一の例外は、サイクルシーケンスの最初と最後のノードが同じノードでなければならないことです。

このように、すべてのサイクルが回路であると結論付けることができますが、その逆は真実ではありません。 さらに、別の推論は、すべてのハミルトン閉路もサイクルであるということです。

したがって、循環グラフのサイクルを持つグラフを呼び出します。 反対に、非巡回グラフのサイクルのないグラフを呼び出します。 最後に、連結グラフにサイクルがない場合、それをツリーと呼びます。

次に、この画像は、閉路グラフ、非閉路グラフ、およびツリーの例を示しています。

循環検出は、グラフ理論の特定の研究分野です。 両方のサイクルを検出するアルゴリズムがあります無向と指示グラフ。 サイクルが特に望ましくないシナリオがあります。 例として、同時システムの使用待機グラフがあります。 このような場合、サイクルはデッドロックの問題が存在することを意味します。

6. その他のシーケンス：ウォーキングとトレイル

すでに見たシーケンスに加えて、実際に最も単純なものである他の2つが存在します：散歩とトレイル。 したがって、このセクションでそれらを簡単に見てみましょう。

ウォークは、グラフ内のノードとエッジの任意のシーケンスです。この場合、ノードとエッジの両方をシーケンス内で繰り返すことができます。

散歩はオープンまたはクローズに分類できます。 オープンウォークには、開始ノードと終了ノードが異なります。 クローズドウォークは、同じ開始ノードと終了ノードを持ちます。 したがって、サーキットとサイクルはクローズドウォークですが、すべてのクローズドウォークがサーキットまたはサイクルであるとは限りません。

トレイルは、シーケンス内にエッジが繰り返されていないオープンウォークです。ただし、必要な数のノードを繰り返すことができます。

下の画像は、散歩やトレイルの例を示しています。

7. 体系的な要約

前のセクションでは、グラフ内の接続を介して形成される可能性のあるノードとエッジシーケンスを調査しました。 これらのシーケンスは、ウォーク、トレイル、パス、サーキット、およびサイクルと呼ばれます。

これらのシーケンスの主な違いは、ノードとエッジが繰り返される可能性に関するものです。 さらに、特定のシーケンスが開いている（最初と最後のノードが同じ）か閉じている（最初と最後のノードが異なる）かを分析する際に、別の関連する特性を定義します。

このように、次の表では、グラフノードとエッジのさまざまなシーケンスを比較しています。

シーケンスがノードを繰り返すことができないが閉じたシーケンスである場合、唯一の例外は最初と最後のノードであり、同じでなければならないことを強調することは重要です。

8. 結論

このチュートリアルでは、グラフノードのシーケンスについて学習しました。 まず、グラフに関する基本的な概念を簡単に確認しました。 したがって、パス、回路、およびサイクルの概念を研究しました。 次に、散歩やトレイルを調査しました。 最後に、提示されたすべてのシーケンスにアプローチする体系的な要約がありました。

グラフで利用可能なシーケンスを分析することで、グラフが表すシナリオに従っていくつかのイベントを決定できると結論付けることができます。 この分析の通常のアプリケーションは、使用待機グラフでサイクルを検出することによってデッドロックを検索することです。 別の例は、特定のノードを訪問するためのより良いルートを示すシーケンスを見つけることで構成されています（巡回セールスマン問題）。