グラフ理論入門
1. 概要
このチュートリアルでは、コンピュータサイエンスで最も重要なデータ構造のいくつか–グラフについて説明します。
まず、グラフ理論の概念を理解するために、グラフ理論の基礎を学びます。 次に、機械学習アプリケーションで見つけることができるグラフの種類を調べます。
このチュートリアルの最後に、グラフとは何か、どのような種類のグラフが存在するかがわかります。 また、グラフのプリミティブコンポーネントの特性が何であるかもわかります。
2. グラフ理論の基礎
2.1. グラフの定義
グラフは、頂点のセットとエッジのセットで構成される構造です。 したがって、グラフを作成するには、頂点とエッジの2つのセットの要素を定義する必要があります。
頂点は、グラフが存在するために必要な基本単位です。 グラフに少なくとも1つの頂点が必要であるという条件を課すのが通例ですが、これが当てはまる実際の理論的な理由はありません。 頂点は、ある種の基準によって相互に関連付けられたオブジェクトに対応する数学的抽象化です。
代わりに、エッジのないグラフを定義できるという意味で、エッジはオプションです。 エッジが存在する場合は、それ自体への頂点の接続を含む、グラフの任意の2つの頂点間のリンクまたは接続です。 エッジの背後にある考え方は、エッジが存在する場合、2つのオブジェクト間に関係が存在することを示し、エッジが接続することを想像するというものです。
通常、頂点のセットとエッジのセットで示します。 次に、2つのセット間の関係をモデル化する構造としてグラフを定義できます。
従来は常に最初に頂点を示し、次にエッジを示すため、括弧の間の2つのセットの順序が重要であることに注意してください。 したがって、グラフは、頂点のセットとエッジのセットの間の関係をモデル化する構造であり、その逆ではありません。
先に進む前に、用語について簡単に説明します。グラフは、数学とネットワーク理論の両方の共同研究対象です。 2つの分野で使用される用語はわずかに異なりますが、常に同じ概念を指します。 この記事では、数学の用語を使用しますが、必要に応じて、変換テーブルを使用して2つの間を変換できます。
2.2. 頂点の一般的なプロパティ
次に、頂点とエッジが持つ特性について詳しく説明します。 最初に頂点から始めましょう。
前に述べたように、グラフには頂点が必要ですが、必ずしもエッジは必要ありません。 実際、グラフを完全に頂点で構成することは完全に可能です。 空のグラフの頂点など、他の頂点に接続されていない頂点は、分離されたと呼ばれます。
また、孤立した頂点の次数はゼロに等しいとも言います。 このコンテキストでの次数は、頂点に対する入射エッジの数を示します。
分離されていない頂点については、正の次数があると言います。これは通常、として示されます。 頂点の次数は任意の自然数にすることができます。
名前の葉は、特定の種類の頂点を示します。1つは次数です。 この用語は階層ツリーと共通しており、同様に、他の1つの頂点にのみ接続されている頂点に関係します。
2.3. 頂点のラベル
頂点には、値を関連付けることもできます。 これらの値は任意の形式をとることができ、特定の制限はありません。 値が関連付けられている頂点はラベル付き頂点と呼ばれ、値が関連付けられていない頂点はラベルなしと呼ばれます。
一般に、ラベルのない2つの頂点は、それらのペアの頂点のみに基づいて区別できます。 ラベル付けされた頂点間の比較では、代わりに頂点のペアとそれらに割り当てられた値の両方を調査する必要があります。
頂点に関する最後の注意点は、グラフに含まれる頂点の数に関するものです。 この番号は特に重要であり、グラフの順序と呼びます。
2.4. エッジの一般的なプロパティ
これで、エッジの特性を調べることができます。 頂点とは対照的に、エッジは孤立して存在することはできません。 これは、グラフ自体が存在するために頂点を必要とし、エッジがグラフに関連して存在するという考慮に由来します。
エッジは、グラフ内の任意の2つの頂点を接続できます。 エッジで接続された2つの頂点は、そのエッジの端点と呼ばれます。 その定義により、エッジが存在する場合、2つのエンドポイントがあります。
エッジが3つ以上の頂点を接続するグラフも存在し、ハイパーグラフと呼ばれます。 このチュートリアルではそれらに焦点を当てていませんが、知識グラフの開発における歴史的および現代的重要性のため、それらの存在について言及する必要があります。
2.5. エンドポイント、方向、ループ
エッジの2つの端点を、頂点の方向を指しているのか、頂点から離れているのかによって、さらに区別することができます。 頂点に向かうエッジを入力エッジと呼び、頂点から発生するエッジを出力エッジと呼びます：
上の画像では、ペアを接続しているエッジは、に接続している対応するエッジによって往復していません。 この場合、グラフは有向グラフであると言い、エッジを円弧と呼びます。
エッジを無向にすることもでき、どちらがそのエッジの原点の頂点であるかに関係なく、2つの頂点を接続します。このタイプのエッジは線と呼ばれ、それらによって接続された任意の2つの頂点を通過できるようになっています。両方向。 これを見る1つの方法は、円弧と円弧の間の線とそれに対応する線を想像することです。
このタイプの考え方の利点は、グラフの隣接行列にうまく変換されることです。
さらに、エッジは、同じ頂点の入力エッジと出力エッジになることができます。 この場合、そのエッジをループと呼びます。
ループは特殊な種類のエッジであり、すべてのグラフに存在するわけではありません。 ループのないグラフを他のグラフと区別するために、単純なグラフと呼びます。
最後に、グラフのエッジの数はそのグラフの特別なパラメータであると言えます。 この番号をグラフのサイズと呼びます。これには、後で説明するいくつかの特別なプロパティがあります。
2.4. グラフ内のパス
空でないエッジのセットを持つグラフには、2つの頂点を接続するエッジのシーケンスで構成されるパスがあります。 有向エッジのシーケンスに関連するパスを、当然のことながら有向パスと呼ぶことができます。 ただし、無向エッジに関連するパスには特別な名前はありません。
パスとグラフの関係を確認する1つの方法は、各グラフがラビリンスであり、その各頂点が交差点であると想像することです。
このモデルでは、パスの開始頂点は迷路の入口に対応し、ターゲット頂点は出口に対応します。 この概念フレームワークを使用すると、迷路を横断してトレイルを残すことを想像できます。これをパスと呼びます。
特別な種類のパスの1つは、グラフ内のすべての頂点をトラバースするパスであり、ハミルトンパスと呼ばれます。 ハミルトンパスは、必ずしもすべてのグラフに存在するとは限りません。 すべての頂点をカバーする完全なトレースを残すことができるため、トレース可能なハミルトンパスを含むグラフを呼び出します。
最後に、開始頂点と終了頂点が一致するパスは特別であり、サイクルと呼ばれます。 パスを見つけるためのアルゴリズムがパスを無期限にループしてしまう可能性があるため、グラフのサイクルを検出することが重要です。
パスがコンピュータサイエンスで特に重要である理由についての最後の注意。 これは、ダイクストラのアルゴリズムや A * など、最短経路を簡単に見つけることができる効率的なアルゴリズムの方法があるためです。 これにより、プロセスの最適化、ロジスティクス、検索クエリの処理などの問題をコンピューターで解決できます。
3. グラフの種類
3.1. 空のグラフ
グラフは、頂点のセットがnullでない場合にのみ存在することを前述しました。 ただし、それらのエッジのセットは空の場合もあります。 この場合、グラフは空であると言います。
空のグラフのサイズは常にです。
3.2. 有向グラフ
上で予想されたように、有向グラフは、2つの頂点の間に少なくとも1つのエッジを持ち、反対方向に同じ頂点を接続する対応するエッジを持たないグラフです。
有向グラフには、対象と対象を自由に入れ替えることができない現実世界の関係をうまくモデル化するという特徴があります。 原則として、グラフを有向にするか無向にするかがわからない場合、グラフは有向になります。
有向グラフは、既存の有向エッジの方向にのみトラバースできます。
有向グラフに関しては、有向グラフに可能なエッジの最大数が含まれているかどうかを判断する一般的な方法があることを簡単に説明できます。 これは、有向グラフのエントロピーに関係する理由から重要です。
3.3. 無向グラフ
無向グラフは、頂点間にエッジが存在することで、対応するエッジが存在することを意味するグラフです。
無向グラフでは、エッジで接続された任意の2つの頂点間のトラバースが可能です。 同じことが有向グラフには必ずしも当てはまりません。
3.4. 接続されたグラフと切断されたグラフ
また、パスの特性に基づいてグラフを区別することもできます。 たとえば、頂点のすべてのペアを接続するパスがあるかどうか、またはそれらの間にパスがない頂点のペアがあるかどうかによって区別できます。 2つの頂点の間に少なくとも1つのパスがある場合、グラフを連結と呼びます。
同様に、互いに分離された頂点が少なくとも2つある場合、グラフは切断されていると言います。
3.5. ハミルトニアン連結グラフ
ハミルトニアン連結グラフは、任意の2つの頂点の間にハミルトンパスがあるグラフです。 接続されたグラフが必ずしもハミルトニアンに接続されているとは限らないことに注意してください。
ハミルトニアン連結グラフは常に追跡可能なグラフですが、その逆は必ずしも当てはまりません。
3.6. 完全グラフ
可能なすべての頂点のペアの間にエッジが含まれている場合、グラフは完全であると言います。 順序の完全グラフの場合、そのサイズは常に次のようになります。
ラベルのない頂点を持つ同じ順序のすべての完全グラフは同等です。
3.7. トーナメント
トーナメントは、有向エッジのみを含む一種の完全グラフです。
この名前は、スポーツイベントの試合構成の作成に頻繁に使用されることに由来しています。
3.8. 加重グラフ
表示される最後のタイプのグラフは、加重グラフです。 重み付きグラフは、エッジに重み（つまり数値）が割り当てられているグラフです。
機械学習で一般的に使用される典型的な加重グラフは、人工ニューラルネットワークです。 ニューラルネットワークは、各頂点に追加の活性化関数が割り当てられた有向加重グラフとして概念化できます。
4. 結論
このチュートリアルでは、グラフ理論の概念的基礎を研究しました。 また、グラフ、頂点、エッジ、およびパスの定義についてもよく理解しました。
また、遭遇する可能性のあるグラフのタイプと、頂点、エッジ、およびパスの観点から予測可能な特性についても調査しました。
