ただし、頂点の数、エッジの数、相互接続性、および全体の構造に応じて、さまざまなタイプのグラフが多数ありますが、そのような一般的なタイプのグラフのいくつかは次のとおりです。
1. ヌルグラフ
あ ヌルグラフ 頂点間にエッジがないグラフです。ヌル グラフは空のグラフとも呼ばれます。
例
n 個の頂点を持つヌル グラフは Nn で表されます。
2. 自明なグラフ
あ 自明なグラフ 頂点が 1 つだけあるグラフです。
例
上のグラフには、エッジのない頂点「v」が 1 つだけあります。したがって、それは自明なグラフです。
3. 単純なグラフ
あ 簡単なグラフ は次の無向グラフです 平行なエッジがない そして ループなし 。
n 個の頂点を持つ単純なグラフ。各頂点の次数は最大でも n -1 です。例
上の例では、最初のグラフは頂点 A と B の間に 2 つのエッジがあり、ループもあるため、単純なグラフではありません。
2 番目のグラフは、ループや平行エッジが含まれていないため、単純なグラフです。
4. 無向グラフ
アン 無向グラフ エッジが次のようなグラフです。 指示されていない 。
例
上のグラフには有向エッジがないため、無向グラフになります。
5. 有向グラフ
あ 有向グラフ は、 エッジが方向付けられている 矢印で。
有向グラフとも呼ばれます。 ダイグラフ 。
例
上のグラフでは、各エッジは矢印の方向を向いています。有向エッジには A から B への矢印があり、A は B に関連していますが、B は A に関連していないことを意味します。
6. 完全なグラフ
すべての頂点のペアが 1 つのエッジによって結合されているグラフは、 完全なグラフ 。考えられるすべてのエッジが含まれています。
n 個の頂点を持つ完全なグラフには正確に nC2 個のエッジが含まれており、Kn で表されます。
例
上記の例では、グラフ内の各頂点が 1 つのエッジを介して残りのすべての頂点に接続されているため、両方のグラフが完全なグラフになります。
7. 接続されたグラフ
あ 接続されたグラフ は、任意の 1 つの頂点から他の任意の頂点にアクセスできるグラフです。接続されたグラフでは、頂点の各ペアの間に少なくとも 1 つのエッジまたはパスが存在します。
例
上の例では、任意の 1 つの頂点から他の任意の頂点までトラバースできます。これは、すべての頂点のペアの間に少なくとも 1 つのパスが存在することを意味し、したがって接続されたグラフになります。
8. 切り離されたグラフ
あ 切断されたグラフ は、頂点の各ペアの間にパスが存在しないグラフです。
例
上のグラフは、切り離された 2 つの独立したコンポーネントで構成されています。したがって、あるコンポーネントの頂点から他のコンポーネントの頂点に移動することはできないため、切断されたグラフになります。
9. 通常のグラフ
あ 通常のグラフ はすべての頂点の次数が等しいグラフです。
すべての頂点の次数が k である場合、それは k-正則グラフと呼ばれます。
例
上の例では、すべての頂点の次数は 2 です。したがって、それらは 2- と呼ばれます。 通常のグラフ 。
10. 循環グラフ
「n」個の頂点 (n>=3) と「n」個のエッジを持ち、すべてのエッジで「n」のサイクルを形成するグラフは、次のように呼ばれます。 サイクルグラフ 。
少なくとも 1 つのサイクルを含むグラフは、 循環グラフ 。
サイクルグラフでは、各頂点の次数は 2 です。
n個の頂点を持つサイクルグラフをCnと表記します。
開発者モードを無効にする
例1
上の例では、すべての頂点の次数が 2 です。したがって、それらはすべて循環グラフです。
例 2
上のグラフには 2 つのサイクルが含まれているため、循環グラフになります。
11. 非巡回グラフ
サイクルを含まないグラフは、 非循環グラフ 。
例
上のグラフには循環が含まれていないため、非循環グラフになります。
12. 二部グラフ
あ 二部グラフ は、エッジがセット内ではなくセット間のみを通過するように、頂点セットを 2 つのセットに分割できるグラフです。
グラフ G (V, E) が、各エッジ e ∈ E となるように頂点セット V(G) が 2 つの空ではない素なサブセット V1(G) と V2(G) に分解できる場合、そのグラフは二部グラフと呼ばれます。 (G) には、V1(G) に最後のジョイントが 1 つあり、V2(G) にもう 1 つの最後の点があります。
分割 V = V1 ∪ V2 は G の二分割として知られています。
例1
例 2
13. 完全な二部グラフ
あ 完全な二部グラフ は、最初のセットの各頂点が 1 つのエッジによって 2 番目のセットの各頂点に結合されている 2 部グラフです。
完全な 2 部グラフは、完全な 2 部グラフです。
Complete Bipartite graph = Bipartite graph + Complete graph
例
上のグラフは K として知られています4、3。
14. スターグラフ
スター グラフは、n-1 個の頂点が次数 1 を持ち、単一の頂点が次数 (n -1) をもつ完全な 2 部グラフです。これはまさに、(n - 1) 個の頂点が 1 つの中心頂点に接続された星形のように見えます。
n 個の頂点を持つスター グラフは S で示されます。n。
例
上の例では、n 個の頂点のうち、すべての (n-1) 個の頂点が 1 つの頂点に接続されています。したがって、それは星図です。
15 加重グラフ
重み付きグラフは、エッジに何らかの重みまたは数値がラベル付けされているグラフです。
重み付きグラフ内のパスの長さは、パス内のすべてのエッジの重みの合計です。
例
上のグラフで、パスが a -> b -> c -> d -> e -> g の場合、パスの長さは 5 + 4 + 5 + 6 + 5 = 25 となります。
16. マルチグラフ
任意の頂点のペアの間に複数のエッジがあるグラフ、または頂点から頂点までのエッジ (ループ) があるグラフは、 マルチグラフ 。
例
上のグラフでは、頂点セット B と C が 2 つのエッジで接続されています。同様に、頂点セット E と F は 3 つのエッジで接続されます。したがって、それはマルチグラフです。
17. 平面グラフ
あ 平面グラフ は、その 2 つのエッジが、それらが入射する頂点以外で交差しないように平面内に描くことができるグラフです。
例
上のグラフは、エッジが互いに交差しているため、平面ではないように見えるかもしれません。しかし、上のグラフを書き直すことはできます。
上のグラフの 3 つの平面図は次のとおりです。
上記 3 つのグラフは互いに交差する 2 つのエッジで構成されていないため、上記のグラフはすべて平面です。
18. 非平面グラフ
平面グラフではないグラフを非平面グラフと呼びます。言い換えれば、少なくとも 1 対の交差エッジがなければ描画できないグラフは、非平面グラフとして知られています。
例
上のグラフは非平面グラフです。