圖論 - 圖的型別

---

---

根據頂點數、邊數、互連性和整體結構，圖有多種型別。本章將僅討論其中幾種重要的圖型別。

空圖

沒有邊的圖稱為空圖。

例子

在上圖中，有三個頂點，分別命名為“a”、“b”和“c”，但它們之間沒有邊。因此它是一個空圖。

平凡圖

只有一個頂點的圖稱為平凡圖。

例子

在上圖中，只有一個頂點“a”，沒有其他邊。因此它是一個平凡圖。

無向圖

無向圖包含邊，但邊不是有向的。

例子

在這個圖中，“a”、“b”、“c”、“d”、“e”、“f”、“g”是頂點，“ab”、“bc”、“cd”、“da”、“ag”、“gf”、“ef”是圖的邊。由於它是一個無向圖，“ab”和“ba”是相同的。類似地，其他邊也以相同的方式考慮。

有向圖

在有向圖中，每條邊都有一個方向。

例子

在上圖中，我們有七個頂點“a”、“b”、“c”、“d”、“e”、“f”和“g”，以及八條邊“ab”、“cb”、“dc”、“ad”、“ec”、“fe”、“gf”和“ga”。由於它是一個有向圖，每條邊都帶有箭頭標記，表示其方向。請注意，在有向圖中，“ab”與“ba”不同。

簡單圖

沒有環且沒有平行邊的圖稱為簡單圖。

• 具有“n”個頂點的單個圖中可能存在的最大邊數為ⁿC₂，其中ⁿC₂ = n(n – 1)/2。

• 具有“n”個頂點的可能簡單圖的數量 = 2^nc₂ = 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個圖如下所示 -

連通圖

如果每對頂點之間存在一條路徑，則稱圖G為連通圖。圖中每個頂點至少應有一條邊。這樣我們就可以說它連線到邊另一側的其他頂點。

例子

在下圖中，每個頂點都有自己的邊連線到其他邊。因此它是一個連通圖。

非連通圖

如果圖G不包含至少兩個連通頂點，則稱其為非連通圖。

示例1

下圖是非連通圖的一個例子，其中有兩個連通分量，一個具有“a”、“b”、“c”、“d”頂點，另一個具有“e”、“f”、“g”、“h”頂點。

這兩個連通分量是獨立的，並且彼此不連線。因此它被稱為非連通圖。

示例2

在這個例子中，有兩個獨立的連通分量，a-b-f-e和c-d，它們彼此不連線。因此這是一個非連通圖。

正則圖

如果圖中所有頂點的度數都相同，則稱圖G為正則圖。在圖中，如果每個頂點的度數為“k”，則該圖稱為“k-正則圖”。

例子

在下圖中，所有頂點的度數都相同。因此這些圖稱為正則圖。

在這兩個圖中，所有頂點的度數都為2。它們被稱為2-正則圖。

完全圖

具有“n”個互連頂點的簡單圖稱為完全圖，並用“K_n”表示。在圖中，一個頂點應該與所有其他頂點都有邊，然後它被稱為完全圖。

換句話說，如果一個頂點連線到圖中的所有其他頂點，則它被稱為完全圖。

例子

在下圖中，圖中的每個頂點都與圖中除自身之外的所有其他頂點連線。

在圖I中，

在圖II中，

環圖

如果一個簡單圖具有“n”個頂點（n >= 3）和“n”條邊，並且所有邊都形成長度為“n”的環，則稱為環圖。

如果圖中每個頂點的度數為二，則稱為環圖。

符號 - C_n

例子

看看下面的圖 -

• 圖I有3個頂點和3條邊，形成一個環“ab-bc-ca”。

• 圖II有4個頂點和4條邊，形成一個環“pq-qs-sr-rp”。

• 圖III有5個頂點和5條邊，形成一個環“ik-km-ml-lj-ji”。

因此，所有給定的圖都是環圖。

輪圖

輪圖是從環圖C_n-1透過新增一個新頂點獲得的。該新頂點稱為中心，連線到C_n的所有頂點。

符號 - W_n

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

例子

看看下面的圖。它們都是輪圖。

在圖I中，它是從C₃透過在中間新增一個名為“d”的頂點獲得的。它表示為W₄。

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

在圖II中，它是從C₄透過在中間新增一個名為“t”的頂點獲得的。它表示為W₅。

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

在圖III中，它是從C₆透過在中間新增一個名為“o”的頂點獲得的。它表示為W₇。

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

有環圖

至少有一個環的圖稱為有環圖。

例子

在上圖示例中，我們有兩個環a-b-c-d-a和c-f-g-e-c。因此它被稱為有環圖。

無環圖

沒有環的圖稱為無環圖。

例子

在上圖示例中，我們沒有任何環。因此它是一個無環圖。

二分圖

具有頂點劃分V = {V₁, V₂}的簡單圖G = (V, E)稱為二分圖，如果E的每條邊都連線V₁中的一個頂點到V₂中的一個頂點。

一般來說，二分圖有兩組頂點，假設為V₁和V₂，如果畫一條邊，它應該連線集合V₁中的任何頂點到集合V₂中的任何頂點。

例子

在這個圖中，您可以觀察到兩組頂點 - V₁和V₂。這裡，兩條名為“ae”和“bd”的邊連線了兩組V₁和V₂的頂點。

完全二分圖

如果V₁中的每個頂點都連線到V₂的每個頂點，則稱具有劃分V = {V₁, V₂}的二分圖“G”，G = (V, E)為完全二分圖。

一般來說，完全二分圖連線集合V₁中的每個頂點到集合V₂中的每個頂點。

例子

下圖是一個完全二分圖，因為它有連線集合V₁中的每個頂點到集合V₂中的每個頂點的邊。

如果|V₁| = m且|V₂| = n，則完全二分圖用K_{m, n}表示。

• K_m,n有(m+n)個頂點和(mn)條邊。

• 如果m=n，則K_m,n是正則圖。

一般來說，完全二分圖不是完全圖。

如果m=n=1，則K_m,n是完全圖。

具有n個頂點的二分圖中的最大邊數為

如果n=10，k5, 5= ⌊ n² / 4 ⌋ = ⌊ 10² / 4 ⌋ = 25

類似地K6, 4=24

K7, 3=21

K8, 2=16

K9, 1=9

如果n=9，k5, 4 = ⌊ n² / 4 ⌋ = ⌊ 9² / 4 ⌋ = 20

類似地K6, 3=18

K7, 2=14

K8, 1=8

如果“G”沒有奇數長度的環，則“G”是二分圖。二分圖的一個特例是星形圖。

星形圖

形式為K_{1, n-1}的完全二分圖是具有n個頂點的星形圖。如果一個頂點屬於一個集合，而所有其餘頂點屬於另一個集合，則星形圖是完全二分圖。

例子

在上圖中，“n”個頂點中的所有“n–1”個頂點都連線到一個頂點。因此它採用K_{1, n-1}的形式，它們是星形圖。

圖的補圖

令'G−'為一個簡單圖，其一些頂點與“G”相同，並且如果邊不存在於G中，則邊{U, V}存在於'G−'中。這意味著，如果兩個頂點在G中不相鄰，則它們在'G−'中相鄰。

如果存在於圖I中的邊不存在於另一個圖II中，並且如果圖I和圖II組合在一起形成一個完全圖，則圖I和圖II稱為彼此的補圖。

例子

在以下示例中，圖-I有兩條邊“cd”和“bd”。其補圖-II有四條邊。

請注意，圖-I中的邊不存在於圖-II中，反之亦然。因此，這兩個圖的組合給出了“n”個頂點的完全圖。

注意 - 兩個補圖的組合給出一個完全圖。

如果“G”是任何簡單圖，則

|E(G)| + |E('G-')| = |E(K_n)|，其中n = 圖中頂點數。

例子

設“G”是一個具有九個頂點和十二條邊的簡單圖，求'G-'中的邊數。

已知， |E(G)| + |E('G-')| = |E(K_n)|

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

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

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

|E('G-')| = 24

“G”是一個具有40條邊的簡單圖，其補圖'G−'有38條邊。求圖G或'G−'中的頂點數。

設圖中的頂點數為“n”。

已知， |E(G)| + |E('G-')| = |E(K_n)|

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

156 = n(n-1)

13(12) = n(n-1)

n = 13