資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究圖的型別
根據頂點數、邊數、互連性和整體結構，圖有多種型別。本章將僅討論其中幾種重要的圖型別。
空圖
**沒有邊的圖**稱為空圖。
示例
在上圖中，有三個頂點，分別命名為“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”個頂點的單個圖中可能存在的最大邊數為nC2，其中nC2 = n(n – 1)/2。
具有“n”個頂點的簡單圖的個數為2nc2 = 2n(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”個互連頂點的簡單圖稱為完全圖，並用“Kn”表示。在圖中，**一個頂點應與所有其他頂點都有邊相連**，然後它被稱為完全圖。
換句話說，如果一個頂點連線到圖中的所有其他頂點，則它被稱為完全圖。
示例
在下圖中，圖中的每個頂點都與圖中除自身以外的所有其他頂點相連。
在圖 I 中，
| a | b | c | |
|---|---|---|---|
| a | 未連線 | 已連線 | 已連線 |
| b | 已連線 | 未連線 | 已連線 |
| c | 已連線 | 已連線 | 未連線 |
在圖 II 中，
| p | q | r | s | |
|---|---|---|---|---|
| p | 未連線 | 已連線 | 已連線 | 已連線 |
| q | 已連線 | 未連線 | 已連線 | 已連線 |
| r | 已連線 | 已連線 | 未連線 | 已連線 |
| s | 已連線 | 已連線 | 已連線 | 未連線 |
環圖
如果一個簡單圖具有“n”個頂點（n >= 3）和“n”條邊，並且所有邊都形成長度為“n”的環，則該圖稱為環圖。
如果**圖中每個頂點的度數為二**，則稱為環圖。
**符號** - Cn
示例
請檢視以下圖表 -
圖 I 有 3 個頂點和 3 條邊，形成一個環“ab-bc-ca”。
圖 II 有 4 個頂點和 4 條邊，形成一個環“pq-qs-sr-rp”。
圖 III 有 5 個頂點和 5 條邊，形成一個環“ik-km-ml-lj-ji”。
因此，所有給定的圖都是環圖。
輪圖
輪圖是從環圖 Cn-1 透過新增一個新頂點獲得的。該新頂點稱為**中心**，它連線到 Cn 的所有頂點。
**符號** - Wn
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 中，它是從 C3 透過在中間新增一個名為“d”的頂點獲得的。它表示為 W4。
Number of edges in W4 = 2(n-1) = 2(3) = 6
在圖 II 中，它是從 C4 透過在中間新增一個名為“t”的頂點獲得的。它表示為 W5。
Number of edges in W5 = 2(n-1) = 2(4) = 8
在圖 III 中，它是從 C6 透過在中間新增一個名為“o”的頂點獲得的。它表示為 W7。
Number of edges in W4 = 2(n-1) = 2(6) = 12
有環圖
**至少有一個**環的圖稱為有環圖。
示例
在上圖示例中，我們有兩個環 a-b-c-d-a 和 c-f-g-e-c。因此，它被稱為有環圖。
無環圖
**沒有環**的圖稱為無環圖。
示例
在上圖示例中，我們沒有任何環。因此，它是一個無環圖。
二分圖
頂點劃分 V = {V1, V2} 的簡單圖 G = (V, E) 稱為二分圖，**如果 E 的每條邊都連線 V1 中的一個頂點到 V2 中的一個頂點**。
通常，二分圖有兩組頂點，假設為 V1 和 V2，如果畫一條邊，它應該連線集合 V1 中的任何頂點到集合 V2 中的任何頂點。
示例
在此圖中，您可以觀察到兩組頂點 - V1 和 V2。這裡，名為“ae”和“bd”的兩條邊連線了兩組頂點 V1 和 V2。
完全二分圖
如果劃分 V = {V1, V2} 的二分圖“G”，G = (V, E) 使得 V1 中的每個頂點都連線到 V2 的每個頂點，則稱其為完全二分圖。
通常，完全二分圖將集合 V1 中的每個頂點連線到集合 V2 中的每個頂點。
示例
下圖是一個完全二分圖，因為它具有連線集合 V1 中的每個頂點到集合 V2 中的每個頂點的邊。
如果 |V1| = m 且 |V2| = n，則完全二分圖表示為 Km, n。
Km,n 有 (m+n) 個頂點和 (mn) 條邊。
如果 m=n，則 Km,n 是一個正則圖。
通常，**完全二分圖不是完全圖**。
如果 m = n = 1，則 Km,n 是一個完全圖。
具有**n**個頂點的二分圖中的最大邊數為
如果 n = 10，k5, 5 = ⌊ n2 4 ⌋ = ⌊ 102 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'是二分圖。二分圖的一種特殊情況是**星形圖**。
星形圖
形式為K1, n-1的完全二分圖是具有n個頂點的星形圖。如果一個頂點屬於一個集合，而所有其餘頂點屬於另一個集合，則星形圖是完全二分圖。
示例
在上圖中，在'n'個頂點中，所有'n-1'個頂點都連線到一個頂點。因此，它採用K1, n-1的形式，這些都是星形圖。
896次瀏覽
