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

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

空グラフ

A graph having no edges ヌルグラフと呼ばれます。

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

トリビアルグラフ

A graph with only one vertex トリビアルグラフと呼ばれます。

上に示したグラフでは、頂点 '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」とは異なることに注意してください。

シンプルなグラフ

グラフ with no loops といいえ parallel edges 単純グラフと呼ばれます。

  • '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の頂点を持つエッジの最大数-

n C 2 = n(n–1)/ 2

= 3(3–1)/ 2

= 6/2

= 3つのエッジ

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

2 n C 2 = 2 n(n-1)/ 2

= 2 3(3-1)/ 2

= 2 3

8

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

コネクテッドグラフ

グラフGは接続されていると言われています if there exists a path between every pair of vertices。グラフのすべての頂点に少なくとも1つのエッジが必要です。つまり、エッジの反対側にある他の頂点に接続されていると言えます。

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

切断されたグラフ

グラフGには、接続された頂点が2つ以上含まれていない場合、切断されます。

例1

次のグラフは、切断されたグラフの例です。1つは「a」、「b」、「c」、「d」の頂点を持ち、もう1つは「e」、「f」、「g」、 'h'頂点。

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

例2

この例では、abfeとcdの2つの独立したコンポーネントがあり、これらは互いに接続されていません。したがって、これは切り離されたグラフです。

正則グラフ

グラフGは規則的であると言われていますが、 if all its vertices have the same degree。グラフでは、各頂点の次数が「k」の場合、そのグラフは「k-正則グラフ」と呼ばれます。

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

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

完全グラフ

'n'の相互頂点を持つ単純なグラフは完全グラフと呼ばれ、 denoted by ‘Kn。グラフでは、a vertex should have edges with all other vertices、それからそれは完全グラフと呼ばれました。

言い換えると、頂点がグラフ内の他のすべての頂点に接続されている場合、それは完全グラフと呼ばれます。

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

グラフIでは、

A b c
A 接続されていません 接続済み 接続済み
b 接続済み 接続されていません 接続済み
c 接続済み 接続済み 接続されていません

グラフIIでは、

p q r s
p 接続されていません 接続済み 接続済み 接続済み
q 接続済み 接続されていません 接続済み 接続済み
r 接続済み 接続済み 接続されていません 接続済み
s 接続済み 接続済み 接続済み 接続されていません

サイクルグラフ

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

グラフの各頂点の次数が2の場合、それは閉路グラフと呼ばれます。

Notationcn

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

  • グラフIには、サイクル「ab-bc-ca」を形成している3つのエッジを持つ3つの頂点があります。

  • グラフIIには、サイクル「pq-qs-sr-rp」を形成している4つのエッジを持つ4つの頂点があります。

  • グラフIIIには、サイクル「ik-km-ml-lj-ji」を形成している5つのエッジを持つ5つの頂点があります。

したがって、与えられたすべてのグラフは閉路グラフです。

ホイールグラフ

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

表記法- W N

Wのエッジの数n =ハブから他のすべての頂点までのエッジの数+

ハブのない閉路グラフの他のすべてのノードからのエッジの数。

=(n–1)+(n–1)

= 2(n–1)

次のグラフを見てください。それらはすべてホイールグラフです。

グラフIにおいて、Cから得られる3「D」と命名中央に頂点を追加することによって。これは、Wと表記される4

W4のエッジの数= 2(n-1)= 2(3)= 6

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

W5のエッジの数= 2(n-1)= 2(4)= 8

グラフIIIには、Cから得られる6「O」と命名中央に頂点を追加することによって。これは、Wと表記される7

W4のエッジの数= 2(n-1)= 2(6)= 12

閉路グラフ

グラフ with at least one サイクルは循環グラフと呼ばれます。

上記のグラフの例では、abcdaとcfgecの2つのサイクルがあります。したがって、それは閉路グラフと呼ばれます。

非巡回グラフ

グラフ with no cycles 非巡回グラフと呼ばれます。

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

2部グラフ

頂点パーティションVとの単純なグラフG =(V、E)= {V 1 V、2部グラフと呼ばれています}if every edge of E joins a vertex in V1 to a vertex in V2

一般に、Bipertiteグラフ頂点の二組を有している、私たちは、言うV1とV2、およびエッジが描かれている場合、それはセットV内の任意の頂点を接続する必要がありましょう1セットV内の任意の頂点に2

V -このグラフでは、頂点の二組を観察することができます1及びV 2を。ここで、「AE」と「BD」という名前の2つの縁部は、二組のVの頂点接続されている1及びV 2

完全2部グラフ

パーティションVとの二部グラフ「G」、G =(V、E)= {V 1、V 2は} V内のすべての頂点の場合、完全な二部グラフであることが言われている1がVのすべての頂点に接続されている2

一般に、完全な二部グラフは、集合Vの各頂点を接続する1セットVから各頂点に2

それは集合Vの各頂点を接続するエッジ持っているので、次のグラフは、完全な二部グラフである1組のVから各頂点に2

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

  • K m、nには、(m + n)個の頂点と(mn)個のエッジがあります。
  • K m、nは、m = nの場合の正則グラフです。

一般的に、 complete bipartite graph is not a complete graph

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

n個の頂点を持つ2部グラフのエッジの最大数は-です。

[N 2 /4]

もしN = 10、K5、5 = [N 2/4] = [10 2 /4] = 25。

同様に、K6、4 = 24

K7、3 = 21

K8、2 = 16

K9、1 = 9

n = 9の場合、k5、4 = [n2 / 4] = [92/4] = 20

同様に、K6、3 = 18

K7、2 = 14

K8、1 = 8

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

スターグラフ

K1、n-1の形式の完全2部グラフは、n個の頂点を持つスターグラフです。スターグラフは、1つの頂点が一方のセットに属し、残りのすべての頂点がもう一方のセットに属している場合、完全2部グラフです。

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

グラフの補集合

エッジがGに存在しない場合、「G-」を「G」の頂点と同じようにいくつかの頂点があり、エッジ{U、V}が「G-」に存在する単純なグラフとします。つまり、2つの頂点が隣接しています。 2つの頂点がGで隣接していない場合は、「G-」で。

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

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

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

Note − 2つの補グラフを組み合わせると、完全なグラフが得られます。

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

| E(G)| + | E( 'G-')| = | E(Kn)|、ここでn =グラフ内の頂点の数。

'G'を9つの頂点と12のエッジを持つ単純なグラフとし、 'G-'のエッジの数を見つけます。

あなたが持っている、| E(G)| + | E( 'G-')| = | E(Kn)|

12 + | E( 'G-')| =

9(9-1)/ 2 = 9 C 2

12 + | E( 'G-')| = 36

| E( 'G-')| = 24

「G」は40個のエッジを持つ単純なグラフであり、その補集合「G-」には38個のエッジがあります。グラフGまたは「G-」で頂点の数を見つけます。

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

| E(G)| + | E( 'G-')| = | E(Kn)|

40 + 38 = n(n-1)/ 2

156 = n(n-1)

13(12)= n(n-1)

n = 13