あ 無向グラフ : エッジに方向がないグラフ。つまり、エッジにトラバース方向を示す矢印がありません。例: 友人関係に方向性がないソーシャル ネットワーク グラフ。
有向グラフ : エッジに方向があるグラフ。つまり、エッジにトラバース方向を示す矢印があります。例: ページ間のリンクに方向性がある Web ページのグラフ。 加重グラフ: エッジに重みまたはコストが関連付けられているグラフ。例: 重みが 2 つの都市間の距離を表す道路網グラフ。 重み付けされていないグラフ s: エッジに重みやコストが関連付けられていないグラフ。例: エッジが友情を表すソーシャル ネットワーク グラフ。 完全なグラフ: 各頂点が他のすべての頂点に接続されているグラフ。例: すべてのプレーヤーが他のすべてのプレーヤーと対戦するトーナメント グラフ。 二部グラフ: すべてのエッジが一方のセットの頂点をもう一方のセットの頂点に接続するように、頂点を 2 つの互いに素なセットに分割できるグラフ。例: 頂点を求職者と求人に分割できる求職者グラフ。 木 : サイクルのない接続されたグラフ。例: 各人が両親とつながっている家系図。 サイクル : 少なくとも 1 つのサイクルを持つグラフ。例: 自転車が通過するルートを自転車が表す自転車共有グラフ。 スパースグラフ: 頂点の数に比べてエッジが比較的少ないグラフ。例: 各頂点が化合物を表し、各エッジが 2 つの化合物間の反応を表す化学反応グラフ。 密なグラフ s: 頂点の数に比べてエッジが多いグラフ。例: 各頂点が個人を表し、各エッジが友情を表すソーシャル ネットワーク グラフ。 グラフの種類:
1. 有限グラフ
有限数の頂点と有限数の辺を持つグラフは有限であると言われます。有限グラフは、有限数の頂点と辺を持つグラフです。言い換えれば、有限グラフ内の頂点の数と辺の数は両方とも制限されており、数えることができます。有限グラフは、オブジェクトの数やオブジェクト間の関係が限られている現実世界の状況をモデル化するためによく使用されます。
2. 無限グラフ:
無限の数の頂点と無限の辺がある場合、グラフは無限であると言われます。
3. 自明なグラフ:
有限グラフに頂点が 1 つだけ含まれ、エッジが含まれない場合、そのグラフは自明であると言われます。自明なグラフとは、頂点が 1 つだけあり、エッジがないグラフです。シングルトン グラフまたは単一頂点グラフとも呼ばれます。自明なグラフは最も単純なタイプのグラフであり、より複雑なグラフを構築するための開始点としてよく使用されます。グラフ理論では、自明なグラフは退化したケースとみなされ、通常は詳細に研究されません。
データ構造内のハッシュ化4. 単純なグラフ:
単純なグラフは、頂点のペアの間に複数のエッジを含まないグラフです。異なる都市を結ぶ単純な鉄道線路は、単純なグラフの例です。
5. マルチグラフ:
いくつかの平行エッジを含み、自己ループを含まないグラフは、マルチグラフと呼ばれます。たとえばロードマップ。
- 平行エッジ: 2 つの頂点が複数のエッジで接続されている場合、そのようなエッジは、ルートは多いが宛先は 1 つである平行エッジと呼ばれます。
- ループ： 頂点から始まり同じ頂点で終わるグラフの辺をループまたは自己ループと呼びます。
6. ヌルグラフ:
次数 n でサイズ 0 のグラフは、頂点のペアを接続するエッジのない孤立した頂点のみが存在するグラフです。ヌル グラフはエッジのないグラフです。言い換えれば、これは頂点のみを持ち、頂点間の接続がないグラフです。ヌル グラフは、エッジなしグラフ、孤立グラフ、または離散グラフとも呼ばれます。
7. 完全なグラフ:
n 個の頂点を持つ単純なグラフは、各頂点の次数が n-1 の場合、つまり 1 つの頂点が n-1 個のエッジまたはグラフ内の残りの頂点に接続されている場合、完全なグラフと呼ばれます。完全なグラフはフル グラフとも呼ばれます。
8. 疑似グラフ:
自己ループといくつかの複数のエッジを持つグラフ G は擬似グラフと呼ばれます。擬似グラフは、自己ループ (頂点をそれ自身に接続するエッジ) と複数のエッジ (2 つの頂点を接続する複数のエッジ) の存在を許可するグラフの一種です。対照的に、単純なグラフは、ループや複数のエッジを許容しないグラフです。
9. 通常のグラフ:
グラフ G のすべての頂点が等しい次数であれば、単純なグラフは正則であると言われます。すべての完全なグラフは規則的ですが、その逆は不可能です。通常のグラフは、すべての頂点が同じ数のエッジまたは近傍を持つ無向グラフの一種です。言い換えれば、グラフが規則的であれば、すべての頂点は同じ次数を持ちます。
10. 二部グラフ:
グラフ G = (V, E) は、その頂点セット V(G) が 2 つの空ではない素な部分集合に分割できる場合、二部グラフであると言われます。 E(G) の各エッジ e の一端が V1(G) にあり、もう一端が V2(G) にあるように、V1(G) と V2(G)。分割 V1 U V2 = V は G の二部と呼ばれます。ここで図では、V1(G)={V5, V4, V3} および V2(G)={V1, V2} となります。
11. ラベル付きグラフ:
グラフの頂点と辺が名前、日付、または重みでラベル付けされている場合、そのグラフはラベル付きグラフと呼ばれます。加重グラフとも呼ばれます。
12. 有向グラフ:
すべてのエッジが順序付けられた頂点のペア (Vi、Vj) にマッピングされるようなマッピング f を持つグラフ G = (V, E) は、ダイグラフと呼ばれます。とも呼ばれます 有向グラフ 。順序対（Ｖｉ、Ｖｊ）とは、ＶｉからＶｊに向かう矢印を有するＶｉとＶｊの間のエッジを意味する。この図では: e1 = (V1, V2) e2 = (V2, V3) e4 = (V2, V4)
Java例外処理
13. サブグラフ:
次のような V1(G) が V(G) の部分集合であり、E1(G) が E(G) の部分集合である場合、グラフ G1 = (V1, E1) はグラフ G(V, E) の部分グラフと呼ばれます。 G1 の各エッジには、G と同じ終端頂点があります。
14. 接続または切断のグラフ:
グラフ G の頂点のペア (Vi、Vj) が相互に到達可能である場合、グラフ G は接続されていると言われます。または、グラフ G の頂点の各ペアの間に少なくとも 1 つのパスが存在する場合、グラフは接続されていると言われ、そうでない場合は切断されています。 n 個の頂点を持つヌル グラフは、n 個のコンポーネントから構成される切り離されたグラフです。各コンポーネントは 1 つの頂点で構成され、エッジは構成されません。
15. 循環グラフ:
n 個の頂点、n> = 3、つまり V1、V2、V3- – – – Vn とエッジ (V1、V2)、(V2、V3)、(V3、V4)- – – – (Vn、 V1) は循環グラフと呼ばれます。
16. サブグラフの種類:
- 頂点の互いに素な部分グラフ: V1(G1) の交差 V2(G2) = null の場合、任意の 2 つのグラフ G1 = (V1, E1) および G2 = (V2, E2) は、グラフ G = (V, E) の頂点が互いに素であると言われます。この図では、G1 と G2 の間に共通の頂点はありません。
- エッジの素な部分グラフ: E1(G1) 交差 E2(G2) = null の場合、サブグラフはエッジ共通であると言われます。図では、G1 と G2 の間に共通のエッジはありません。
注記： エッジの素のサブグラフは共通の頂点を持つことができますが、頂点の素のグラフは共通のエッジを持つことができないため、頂点の素のサブグラフは常にエッジの素のサブグラフになります。
17. スパニングサブグラフ
以下に示すグラフ G(V,E) を考えてみましょう。スパニング サブグラフは、元のグラフ G のすべての頂点を含むサブグラフです。つまり、V'=V であり、E' が E のサブセットである場合、G'(V',E') はスパニングされます。
したがって、スパニング サブグラフの 1 つは、以下の G'(V',E') のようになります。これには、元のグラフ G のすべての頂点と G のエッジの一部が含まれています。
これは、グラフ G の多くのまたがるサブグラフの 1 つにすぎません。エッジのさまざまな組み合わせによって、他のさまざまなまたがるサブグラフを作成できます。 V'=V および E'=E であるグラフ G'(V',E') を考慮すると、グラフ G' はグラフ G(V,E) の全域サブグラフであることに注意してください。
グラフの利点:
- グラフを使用すると、複雑なシステムと関係をモデル化し、分析できます。
- これらはデータを視覚化して理解するのに役立ちます。
- グラフ アルゴリズムは、コンピューター サイエンスや、ソーシャル ネットワーク分析、物流、交通などの他の分野で広く使用されています。
- グラフは、ソーシャル ネットワーク、道路ネットワーク、インターネットなどの幅広い種類のデータを表すために使用できます。
グラフの欠点:
- 大きなグラフは視覚化や分析が難しい場合があります。
- グラフ アルゴリズムは、特に大きなグラフの場合、計算コストが高くなる可能性があります。
- グラフ結果の解釈は主観的なものになる可能性があり、ドメイン固有の知識が必要になる場合があります。
- グラフはノイズや外れ値の影響を受ける可能性があり、分析結果の精度に影響を与える可能性があります。
関連記事： グラフの用途とメリット・デメリット
