グラフ理論-グラフの種類

頂点の数、エッジの数、相互接続性、およびそれらの全体的な構造に応じて、さまざまなタイプのグラフがあります。この章では、いくつかの重要なタイプのグラフについてのみ説明します。

ヌルグラフ

エッジのない*グラフはヌルグラフと呼ばれます。

例

ヌルグラフ

上記のグラフには、「a」、「b」、「c」という名前の3つの頂点がありますが、それらの間にエッジはありません。したがって、Null Graphです。

自明なグラフ

頂点が1つしかない*グラフは、自明なグラフと呼ばれます。

例

Trivial

上記のグラフでは、頂点「a」は1つしかなく、他のエッジはありません。したがって、これは単純なグラフです。

無向グラフ

無向グラフにはエッジが含まれていますが、エッジは有向グラフではありません。

例

非監督

このグラフでは、「a」、「b」、「c」、「d」、「e」、「f」、「g」が頂点、「ab」、「bc」、「cd」、「da」 '、' ag '、' gf '、' ef 'はグラフのエッジです。無向グラフであるため、エッジ「ab」と「ba」は同じです。同様に、他のエッジも同様に考慮されます。

有向グラフ

有向グラフでは、各エッジに方向があります。

例

有向グラフ

上記のグラフでは、7つの頂点「a」、「b」、「c」、「d」、「e」、「f」、および「g」、および8つのエッジ「ab」、「cb」、「 dc」、「ad」、「ec」、「fe」、「gf」、および「ga」。有向グラフなので、各エッジには方向を示す矢印が付いています。有向グラフでは、「ab」は「ba」とは異なることに注意してください。

シンプルなグラフ

ループなし*および*平行エッジなし*のグラフは、単純グラフと呼ばれます。

「n」個の頂点を持つ単一のグラフで可能なエッジの最大数は^ n ^ C〜2〜です。ここで^ n ^ C〜2〜= n（n – 1）/2です。
「n」個の頂点= 2 ^^ n ^ c〜2〜^ = 2 ^ n（n-1）/2 ^で可能な単純なグラフの数。

例

次のグラフには、3つのエッジを持つ3つの頂点があり、最大の平行エッジとループを除外しています。これは、上記の式を使用して証明できます。

シンプルグラフ

n = 3頂点を持つエッジの最大数-

nC2 = n(n–1)/2
   = 3(3–1)/2
   = 6/2
   = 3 edges

n = 3頂点を持つ単純なグラフの最大数-

2nC2 = 2n(n-1)/2
   = 23(3-1)/2
   = 23
   = 8

これらの8つのグラフは以下のとおりです-

8つのグラフ

接続グラフ

グラフGは、頂点のすべてのペア間にパスが存在する場合は接続されていると言われます。グラフのすべての頂点に少なくとも1つのエッジが必要です。そのため、エッジの反対側にある他の頂点に接続されていると言えます。

例

次のグラフでは、各頂点には他のエッジに接続された独自のエッジがあります。したがって、接続されたグラフです。

接続グラフ

切断グラフ

少なくとも2つの接続された頂点が含まれていない場合、グラフGは切断されます。

例1

次のグラフは、「a」、「b」、「c」、「d」の頂点を持つコンポーネントと「e」、「f」、「g」を持つコンポーネントの2つのコンポーネントがある、切断グラフの例です。 'h’頂点。

切断グラフ

2つのコンポーネントは独立しており、互いに接続されていません。したがって、非接続グラフと呼ばれます。

例2

切断グラフ1

この例では、a-b-f-eとc-dの2つの独立したコンポーネントがあり、これらは互いに接続されていません。したがって、これは切断されたグラフです。

正則グラフ

グラフGは、すべての頂点の次数が同じであれば、規則的であると言われます*。グラフでは、各頂点の次数が「k」の場合、そのグラフは「k-regular graph」と呼ばれます。

例

次のグラフでは、すべての頂点の次数が同じです。したがって、これらのグラフは通常のグラフと呼ばれます。

正規グラフ

両方のグラフで、すべての頂点の次数は2です。それらは、2-Regular Graphsと呼ばれます。

完全なグラフ

「n」の相互頂点を持つ単純なグラフは完全なグラフと呼ばれ、「K〜n〜」で示されます*。グラフでは、頂点は他のすべての頂点とエッジを持っている必要があり、完全なグラフと呼ばれます。

つまり、頂点がグラフ内の他のすべての頂点に接続されている場合、完全なグラフと呼ばれます。

例

次のグラフでは、グラフ内の各頂点は、それ自体を除き、グラフ内の残りのすべての頂点に接続されています。

完全なグラフ

グラフIでは、

	a	b	c
a	Not Connected	Connected	Connected
b	Connected	Not Connected	Connected
c	Connected	Connected	Not Connected

グラフIIでは、

	p	q	r	s
p	Not Connected	Connected	Connected	Connected
q	Connected	Not Connected	Connected	Connected
r	Connected	Connected	Not Connected	Connected
s	Connected	Connected	Connected	Not Connected

サイクルグラフ

「n」個の頂点（n> = 3）と「n」個のエッジを持つ単純なグラフは、すべてのエッジが「n」個の長さのサイクルを形成する場合、サイクルグラフと呼ばれます。

グラフの各頂点の次数が2の場合、それはサイクルグラフと呼ばれます。

表記-C〜n〜

例

次のグラフを見てください-

グラフIには、「ab-bc-ca」というサイクルを形成する3つのエッジを持つ3つの頂点があります。
グラフIIには、「pq-qs-sr-rp」サイクルを形成する4つのエッジを持つ4つの頂点があります。
グラフIIIには、「ik-km-ml-lj-ji」というサイクルを形成する5つのエッジを持つ5つの頂点があります。

サイクルグラフ

したがって、指定されたグラフはすべてサイクルグラフです。

ホイールグラフ

ホイールグラフは、新しい頂点を追加することにより、サイクルグラフC〜n-1〜から取得されます。その新しい頂点は Hub と呼ばれ、C〜n〜のすべての頂点に接続されます。

表記-W〜n〜

No. of edges in Wn = No. of edges from hub to all other vertices &plus;
                     No. of edges from all other nodes in cycle graph without a hub.
                     = (n–1) + (n–1)
                     = 2(n–1)

例

以下のグラフをご覧ください。それらはすべてホイールグラフです。

ホイールグラフ

グラフIでは、中央に「d」という名前の頂点を追加することにより、C〜3〜から取得されます。 W〜4〜と表示されます。

Number of edges in W4 = 2(n-1) = 2(3) = 6

グラフIIでは、中央に「t」という名前の頂点を追加することにより、C〜4〜から取得されます。 W〜5〜と表示されます。

Number of edges in W5 = 2(n-1) = 2(4) = 8

グラフIIIでは、中央に「o」という名前の頂点を追加することにより、C〜6〜から取得されます。 W〜7〜と表示されます。

Number of edges in W4 = 2(n-1) = 2(6) = 12

巡回グラフ

少なくとも1つのサイクルを持つグラフは、巡回グラフと呼ばれます。

例

巡回グラフ

上記のグラフ例では、a-b-c-d-aとc-f-g-e-cの2つのサイクルがあります。したがって、巡回グラフと呼ばれます。

非循環グラフ

サイクルのない*グラフは非循環グラフと呼ばれます。

例

非周期グラフ

上記のグラフの例では、サイクルはありません。したがって、これは非循環グラフです。

二部グラフ

頂点パーティションV = \ {V〜1〜、V〜2〜}を持つ単純なグラフG =（V、E）は、2部グラフと呼ばれます* EのすべてのエッジがV〜1〜の頂点をの頂点に結合する場合V〜2〜*。

一般に、バイパータイトグラフには2つの頂点セットがあります。V〜1〜とV〜2〜で、エッジを描画する場合、セットV〜1〜の頂点をセットVの頂点に接続する必要があります。〜2〜。

例

二部グラフ

このグラフでは、V〜1〜とV〜2〜の2組の頂点を観察できます。ここでは、「ae」と「bd」という名前の2つのエッジが、2つのセットV〜1〜とV〜2〜の頂点を接続しています。

完全な二部グラフ

パーティションV = \ {V〜1〜、V〜2〜}を持つ2部グラフ 'G'、G =（V、E）は、V〜1〜のすべての頂点がすべてに接続されている場合、完全な2部グラフと言われます。 V〜2〜の頂点。

一般に、完全な2部グラフは、セットV〜1〜の各頂点をセットV〜2〜の各頂点に接続します。

例

次のグラフは、セットV〜1〜の各頂点をセットV〜2〜の各頂点に接続するエッジがあるため、完全な2部グラフです。

完全な二部グラフ

| V〜1〜|の場合= mおよび| V〜2〜| = nの場合、完全な2部グラフはK〜m、n〜で示されます。

K〜m、n〜には（m + n）個の頂点と（mn）個のエッジがあります。
K〜m、n〜は、m = nの場合、通常のグラフです。

一般的に、*完全な二部グラフは完全なグラフ*ではありません。

K〜m、n〜は、m = n = 1の場合、完全なグラフです。

*n* 頂点を持つ2部グラフのエッジの最大数は

[

n² / 4

]

n = 10、k5、5 =⌊[.fraction]＃の場合 n² / 4 ＃⌋=⌊[.fraction]＃ 10² / 4 ＃⌋= 25

同様に、K6、4 = 24

K7、3 = 21

K8、2 = 16

K9、1 = 9

n = 9、k5、4 =⌊[.fraction]＃の場合 n² / 4 ＃⌋=⌊[.fraction]＃ 9² / 4 ＃⌋= 20

同様に、K6、3 = 18

K7、2 = 14

K8、1 = 8

「G」に奇数の長さのサイクルがない場合、「G」は2部グラフです。二部グラフの特殊なケースは、*星グラフ*です。

スターグラフ

K〜1、n-1〜の形式の完全な2部グラフは、n頂点を持つ星形グラフです。単一の頂点が1つのセットに属し、残りのすべての頂点が他のセットに属する場合、スターグラフは完全な2部グラフです。

例

スターグラフ

上記のグラフでは、「n」個の頂点のうち、すべての「n-1」個の頂点が単一の頂点に接続されています。したがって、星形グラフであるK〜1、n-1〜の形式です。

グラフの補数

_ '[。sy] G [.oncapital] − を 'G’の頂点と、 '[にエッジ\ {U、V}が存在するようないくつかの頂点を持つ単純なグラフとします。 sy] G [.oncapital] −' 、Gにエッジが存在しない場合つまり、2つの頂点がGで隣接していない場合、2つの頂点は '[。sy] G [.oncapital] - _で隣接しています。

グラフIに存在するエッジが別のグラフIIに存在せず、グラフIとグラフIIの両方が組み合わされて完全なグラフを形成する場合、グラフIとグラフIIは互いに補数と呼ばれます。

例

次の例では、graph-Iには2つのエッジ「cd」と「bd」があります。補完グラフIIには4つのエッジがあります。

グラフの補数

graph-Iのエッジはgraph-IIには存在せず、その逆も同様です。したがって、両方のグラフを組み合わせると、「n」個の頂点の完全なグラフが得られます。

注-2つの相補的なグラフの組み合わせにより、完全なグラフが得られます。

「G」が単純なグラフの場合、

|E(G)| + |E(G-)| = |E(K_n)|, where n = number of vertices in the graph.

例

「G」を9つの頂点と12のエッジを持つ単純なグラフとし、_ '[。sy] G [.oncapital] - _でエッジの数を見つけます。

あります| E（G）| + | E（_ '[。sy] G [.oncapital] - _）| = | E（K〜n〜）|

12＆plus; | E（_ '[。sy] G [.oncapital] - _）| = [.fraction] ##

9(9-1)/2⁹₂

12＆plus; | E（_ '[。sy] G [.oncapital] - _）| = 36

|E(G-)| = 24

「G」は40のエッジを持つ単純なグラフであり、その補数_ '[。sy] G [.oncapital] − には38のエッジがあります。グラフGまたは '[。sy] G [.oncapital] − _の頂点の数を見つけます。

グラフ内の頂点の数を「n」とします。

あります| E（G）| + | E（_ '[。sy] G [.oncapital] - _）| = | E（K〜n〜）|

40＆plus; 38 = [.fraction]＃ n(n-1) / 2 #

156 = n（n-1）

13（12）= n（n-1）

n = 13

Graph-theory-types-of-graphs

目次

グラフ理論-グラフの種類

ヌルグラフ

例

自明なグラフ

例

無向グラフ

例

有向グラフ

例

シンプルなグラフ

例

接続グラフ

例

切断グラフ

例1

例2

正則グラフ

例

完全なグラフ

例

サイクルグラフ

例

ホイールグラフ

例

巡回グラフ

例

非循環グラフ

例

二部グラフ

例

完全な二部グラフ

例

スターグラフ

例

グラフの補数

例

例