第 6 章 圖

【考綱內容】

1.圖的基本概念

2.圖的存儲及基本操作：(1) 鄰接矩陣法；(2) 鄰接表法；(3) 鄰接多重表、十字鏈表

3.圖的遍歷：(1) 深度優先搜索；(2) 廣度優先搜索

4.圖的基本應用：(1) 最小 (代價) 生成樹；(2) 最短路徑；(3) 拓撲排序；(4) 關鍵路徑

【考情統計】

年份	題數及分值			考點
	單選題	綜合題	總分值
2009	1	1	12	無向連通圖的特性、最短路徑（新的算法）
2010	2	0	4	連通圖的特性、拓撲排序
2011	1	1	10	圖的基本概念、鄰接矩陣、拓撲序列、關鍵路徑
2012	4	0	8	圖的存儲表示法、廣度優先遍歷、最小生成樹（性質、Prim 和 Kruskal 算法）、拓撲排序、最短路徑（Dijkstra）
2013	3	0	6	鄰接矩陣、廣度優先遍歷、關鍵路徑
2014	1	1	12	圖的基本概念、圖的存儲、拓撲排序、最短路徑（Dijkstra）
2015	2	1	12	廣度優先遍歷、最小生成樹（Prim 和 Kruskal）、鄰接矩陣
2016	3	0	12	鄰接表、深度優先遍歷、拓撲排序、最短路徑（Dijkstra）
2017	1	1	10	無向圖邊數和頂點數的關系、最小生成樹（Prim）
2018	1	1	14	拓撲排序、最小生成樹（Prim 或 Kruskal）
2019	2	0	4	有向無環圖描述表達式、關鍵路徑
2020	3	0	6	深度優先遍歷、拓撲排序、最小生成樹（Kruskal）、關鍵路徑
2021	2	1	19	拓撲排序、最短路徑（Dijkstra）、鄰接矩陣分析與應用
2022	2	0	4	圖的基本概念、關鍵路徑
2023	1	1	15	最短路徑、圖的基本概念
2024	1	1	15	鄰接多重表、拓撲排序算法題

【考點解讀】

????????本章內容是數據結構考試重點之一，每年必考，出題形式有選擇題與綜合應用題。①圖的基本應用是本章的重點內容，408 真題中每年都會有相關考查。考生應該熟練掌握圖的基本應用小節里的相關算法（算法思想及算法代碼都要掌握）。②真題也常考各種圖相關算法的實現細節，例如：廣度優先遍歷和深度優先遍歷的過程、Prim 算法和 Kruskal 算法實現過程的對比、Dijkstra 算法實現過程等。③本章第一小節 “圖的基本概念” 常在圖的各類計算題中考查，考生應熟練的掌握本章第一小節中的所有概念名詞。

????????另外，需要引起 408 考生高度重視的是：圖的算法題自 2021 年 408 首次考察以來，最近幾年（2021 年、2023 年和 2024 年）的 408 考試中均在考察圖的算法題。但在 2021 年之前連續十幾年 408 考試都沒考過圖的算法題。尤其是 2024 年 408 考試突然考察拓撲排序的算法題，令很多考生猝不及防，幾乎是得 0 分。所以，圖的算法題考生務必高度重視，不再是可以忽視的部分。考生不要只停留在只掌握算法思想，不僅要會手動模擬（選擇題常考），還應該熟練掌握圖相關的算法代碼（應對算法題），會靈活運用圖的相關的算法。

【復習建議】

本章要注意理解并掌握圖的基礎概念和各種圖的應用。復習建議如下：

????????1.各種圖的定義和圖相關的概念是本章的基礎。重要知識點為出入度和度的概念以及這三者之間的關系、圖的連通性、生成樹概念、圖的相關計算。

????????2.圖的存儲結構，考生除了掌握四種常用圖的存儲結構之外，還需分辨出這四種存儲方式的優缺點。其中，鄰接矩陣和鄰接表是考查的重點，后兩者只需理解思想即可。

????????3.需要掌握圖的兩種遍歷方式，加深理解為什么圖的遍歷需要訪問數組，這也是區分樹與圖的遍歷很重要的一點。

????????4.圖的四種應用，分別為：最小生成樹（涉及 Prim 算法和 Kruskal 算法）、最短路徑（Dijkstra 算法和 Floyd 算法）、拓撲排序、關鍵路徑。考生需要掌握這些應用的思想，并要求能根據具體題目進行手動推導答案，出題較為靈活，經常結合本章節其他小節的內容進行綜合考查。

6.1 圖的基本概念

6.1.1 圖的定義

????????圖?G?由兩個集合?V(vertex)?和?E(edge)?組成，記為?G=(V,E)。其中，V?是?G?的頂點集合，記為?V(G)；E?是連接?V?中兩個不同頂點（頂點對）的邊的有限集合，記為?E(G)?1。若用頂點表示對象，則邊表示對象間關系。
????????【提示】圖?G?的邊集?E(G)?可以是空集，但頂點集?V(G)?不能為空集。
????????通常，用符號?<v,w>?表示從頂點?v?到頂點?w?的一條邊。
????????若表示邊的頂點對是有序的，則稱該圖為有向圖 1。在有向圖中，<v,w>?和?<w,v>?分別表示兩條不同的邊。
????????有向圖的邊?<v,w>?也稱為弧：頂點?v?是邊的起點，也稱為弧尾；頂點?w?是邊的終點，也稱為弧頭（有箭頭的一方）。
????????【提示】弧頭和弧尾的概念跟通常理解的不一樣，弧頭是箭頭 (→) 指向的一方，不要弄混了。
????????例如：在圖 6.1-(a) 中的弧?<V2?,V1?>，頂點?V1??是弧頭，頂點?V2??是弧尾。

例如，圖 6.1-(a) 所示的有向圖?G?可表示為：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?G=(V(G),E(G))
????????????????????????????????????????????????????????V(G)={V1?,V2?,V3?,V4?}
????????????????????????????????E(G)={<V2?,V1?>,<V1?,V3?>,<V1?,V4?>,<V3?,V4?>,<V4?,V2?>}

????????若表示邊的頂點對是無序的，<v,w>?和?<w,v>?表示同一條邊，則稱該圖為無向圖。為了跟有向圖區分，通常用符號?(v,w)?表示無向圖中從頂點?v?到頂點?w?的一條邊。
????????例如，圖 6.1-(b) 所示的無向圖?G?可表示為：
????????????????????????????????????????????????????????????????G=(V(G),E(G))
????????????????????????????????????????????????????????V(G)={V1?,V2?,V3?,V4?}
????????????????????????????????????????E(G)={(V1?,V2?),(V3?,V1?),(V4?,V1?),(V3?,V4?),(V4?,V2?)}

6.1.2 圖的基本術語

1.頂點的度、出度和入度

????????在無向圖中，某個頂點的度（Degree）指與該頂點相連的邊的條數。

????????例如，在圖 6.1-(b) 所示無向圖中，頂點 V?、V?、V?、V?的度分別為：3，2，2，3。
????????在有向圖中，以頂點 v 為終點（即：指向頂點 v，以頂點 v 為弧頭）的邊數目，稱為頂點 v 的入度 1。以頂點 v 為起點（即：以頂點 v 為弧尾）的邊數目，稱為頂點 v 的出度 1。在有向圖中，某個頂點的度等于該頂點的入度與出度的和。
????????例如，在圖 6.1-(a) 所示有向圖中，頂點 V?的度為 3，頂點 V?入度為 1，頂點 V?出度為 2。
關于頂點的度，有如下結論：
????????①在有向圖或無向圖中，因為每條邊都要連接兩個頂點，所以，邊總條數的兩倍等于所有頂點的度之和。但全部頂點數目之和不一定等于邊數的兩倍 (例如，圖中只有一個頂點，沒有邊)。
????????②在有向圖中，所有頂點的出度的和等于所有頂點的入度的和。
????????③在無向或有向圖中，奇數度的頂點的個數是偶數。由①知，所有頂點的度之和是偶數，又因偶數度頂點的度之和為偶，故奇度頂點的度之和亦偶，所以奇度頂點的個數必偶。

2.完全圖

無向完全圖：圖中任意兩個頂點都有邊相連。n 個頂點的無向完全圖共有 n (n - 1)/2 條邊。
有向完全圖：圖中任意兩個頂點都有兩條方向相反的邊相連。n 個頂點的有向完全圖共有 n (n - 1) 條邊。

3.稠密圖和稀疏圖

????????稠密圖和稀疏圖是一個主觀的概念。邊數較少（如邊的條數 E 遠小于 V2 ）的圖稱為稀疏圖，反之稱為稠密圖 2。

4.路徑和路徑長度

路徑：指從一個頂點開始經過一系列的邊到達另一個頂點形成的頂點序列。
路徑長度：指路徑上的邊的條數。例如，圖 6.1-(a) 中頂點 V?到頂點 V?之間的路徑有 2 條：{V?、V?、V?} 和 {V?、V?、V?、V?}，路徑長度分別為 2 和 3。

5.回路或環

回路（環）：指起點和終點是同一個頂點的路徑。回路也稱為環。例如，在圖 6.1-(a) 中，路徑 {V?、V?、V?、V?、V?} 是一條回路。

6.子圖

子圖：若圖 G′的頂點集和邊集分別為圖 G 頂點集和邊集的子集，則圖 G′稱為圖 G 的子圖。
????????【注意】子圖首先得是個圖，圖 G 的頂點集 V 的任意子集 V′與邊集 E 的任意子集 E′，不一定能構成圖 G 的子圖，因為 (V′, E′) 不一定能構成一個圖。例如：頂點集 V′ = {V?,V?} 是圖 6.1-(a) 頂點集的子集，E′ = {<V?,V?>,<V?,V?>} 是圖 6.1-(a) 邊集的子集，但 (V′, E′) 不是圖 6.1-(a) 的子圖，因為 (V′, E′) 不能構成一幅圖。

7.連通，連通圖，極大連通子圖，連通分量

????????連通：指兩個頂點間存在路徑。
????????連通圖：若圖 G 中任意兩個頂點都是連通的，則稱 G 為連通圖，否則稱為非連通圖 3。若一個圖 G 有 n 個頂點，邊的條數小于 n - 1，則 G 必為非連通圖。
????????連通子圖：同時滿足連通圖和子圖的定義。
????????極大連通子圖：極大連通子圖是不被另外任何一個連通子圖所包含的子圖。無向圖 G 的極大連通子圖稱為 G 的連通分量 3。連通圖 G 存在唯一的連通分量，即圖 G 本身。非連通圖的連通分量不唯一。
????????例如，在圖 6.2 中：①圖 (a)、(b) 均為連通圖，且圖 (a) 是自身的極大連通子圖，圖 (b) 是自身的極大連通子圖；②圖 (a) 和圖 (b) 共同組成一張圖 (c)，頂點 B 到頂點 H 之間不存在路徑，所以圖 (c) 是非連通圖。在圖 (c) 中有兩個連通分量 (即有兩個極大連通子圖)，分別為圖 (a) 和圖 (b)。

8.極小連通子圖，生成樹，生成森林

極小連通子圖：指圖的某一個頂點子集所確定的連通子圖中，包含邊數最少的連通子圖。
生成樹：連通圖的生成樹是含有圖中全部的 n 個頂點和 n - 1 條邊的極小連通子圖。若隨機去掉生成樹的一條邊，則該生成樹會變成非連通圖。若隨機添一條邊，則該生成樹會形成一個環。
生成森林：對于非連通圖 G 而言，連通分量的生成樹構成了圖 G 的生成森林。

9.強連通圖，強連通分量

強連通圖：任意兩個頂點間都存在路徑的有向圖。
【提示】一個圖是強連通并不一定說明圖中任意兩個頂點之間都存在雙向邊，是允許有其他頂點作為中間頂點的。
強連通分量：有向圖的極大強連通子圖 2。

10.邊的權，網（帶權圖）

邊的權：在無向圖或有向圖的每一條邊上都可以標上一個代表某種含義的數值，該數值稱為邊的權 2。例如：用邊來表示活動，那么邊的權值可以表示完成該活動的時間開銷，完成該活動的費用等。
網：指邊上帶有權值的圖，也稱為帶權圖 3。

6.1.3 習題精編

1.無向圖 G = (V,E)，若圖 G 的頂點數和邊數相等，則圖 G 一定是（ ）。
A. 連通圖
B. 非連通圖
C. 無環的圖
D. 有環的圖

2.以下關于圖的敘述中，正確的是（ ）。
A. 圖與樹的區別在于圖的邊數大于等于頂點數
B. 假設圖 G = (V,E)，頂點集 V′?V，E′?E，則 V′和 E′構成 G 的子圖
C. 無向圖的連通分量是指向無圖中的極大連通子圖
D. 圖的遍歷就是從圖中某一頂點出發并訪問圖中其余頂點

2.【參考答案】?C
【解析】?A 錯誤，因為圖和樹的區別是邏輯上的區別，二者的定義不同，而不能只依靠邊數和頂點數的多少來判斷誰是樹誰是圖。B 錯誤，該選項具有很強的迷惑性，看似是和子圖的定義相差無幾，不過仔細看可以發現，若集合 E′中的邊對應的頂點不是 V′的元素，則 V′和 E′依然構不成子圖。C 正確。D 錯誤，迷惑性很強。圖的遍歷是每個頂點最多只會被訪問一次，若圖非連通，只從某一頂點出發不一定能夠訪遍所有頂點。

3.以下關于圖的敘述中，正確的是（ ）。
A. 強連通有向圖的任何頂點到其他所有頂點都有弧
B. 圖的任意頂點的入度等于出度
C. 有向完全圖一定是強連通有向圖
D. 有向圖的邊集的任意子集和頂點集的任意子集均可構成原有向圖的子圖

3.【參考答案】?C
【解析】?A 錯誤，強連通有向圖是任何頂點到其他所有頂點都有路徑，而不一定都有弧。B 錯誤，圖包含有向圖和無向圖，有向圖的任意頂點的入度不一定等于出度，無向圖才滿足。C 正確。D 錯誤，若邊集的子集中邊的頂點元素不在頂點集的子集里，則有向圖的邊集的子集和頂點集的子集仍然構不成原有向圖的子圖。

4.若圖 G 為非連通無向圖，含有 15 條邊，則圖 G 至少有（ ）個頂點。
A. 6
B. 7
C. 8
D. 9

4.【參考答案】?B
【解析】?關鍵詞 “至少”，“非連通”。假設滿足題意的無向圖至少有 n + 1 個頂點。首先考慮含有 n 個頂點且一定為連通圖的情況，滿足條件的圖為完全圖，含有 15 條邊，然后再加上一個頂點，則可得到此時的非連通圖至少含有的頂點個數。所以，15 = (n - 1) n/2，解得 n 等于 6，因此 15 條邊的非連通無向圖至少有 6 + 1 = 7 個頂點，選擇 B。

5.強連通有向圖 G?和連通無向圖 G?都含有 n 個頂點，則 G?和 G?最少邊條數分別為（ ）。
A. n，n - 1
B. n (n - 1)，n - 1
C. n，n
D. n (n - 1)，n

5.【參考答案】?A
【解析】?若圖構成連通無向圖，則邊數最少的情況是構成一棵樹，則至少有 n - 1 條邊；若是強連通有向圖，則邊數最少的情況是構成一個有向環，即有 n 條邊。選擇 A。

6.無向圖 G 有 100 條邊，度為 9 和度為 11 的頂點均各有 10 個，其余都是度為 3 的頂點，則圖 G 共有（ ）個頂點。
A. 20
B. 23
C. 26
D. 29

6.【參考答案】?A
【解析】?在 n 個頂點，e 條邊的無向圖中，每個頂點的度之和等于邊數的兩倍。因此，可得 (9 * 10) + (11 * 10) + (n - 10 - 10) * 3 = 100 * 2，解得 n = 20，選擇 A。

7.若有向圖 G = (V,E) 的頂點數為 n。則 G 每個頂點的入度和出度之和最大值可是（ ）。
A. n
B. n - 1
C. 2n
D. 2n - 2

7.【參考答案】?D
【解析】?每個頂點可以和其他 n - 1 個頂點都有邊相連（對應每一個出度），且每條邊都可以有兩個方向相反的邊（對應每一個入度），因此最多可以有 2 (n - 1) 條邊（每條邊對應一個度）。

8.具有 6 個頂點的無向圖，當有（ ）條邊時能確保是一個連通圖。
A. 8
B. 9
C. 10
D. 11

8.【參考答案】?D
【解析】?當 5 個頂點的無向圖為完全圖時，再加上一條邊連接另外的第 6 個頂點，此時能用最少的邊確保該圖是連通圖。共需 11 條邊，選擇 D。

9.設有無向圖 G = (V,E) 和 G′=(V′,E′)，若 G′是 G 的生成樹，則下列不正確的是（ ）。
I. G′一定是 G 的子圖
II. G′為 G 的連通分量
III. G′為 G 的無環子圖
IV. G′為 G 的極小連通子圖且 V′ = V
A. 只有 IV
B. II、III
C. III、IV
D. 只有 II

9.【參考答案】?D
【解析】?II 錯誤，無向圖的極大連通子圖稱為連通分量，而一個連通圖的生成樹是極小連通子圖。又因此，極小連通子圖是無環的。所以 I、III、IV 正確。選擇 D。

10.如果一個環具有 n 個頂點，則該環含有（ ）棵生成樹。
A. n2
B. n
C. n - 1
D. 1

10.【參考答案】?B
【解析】?生成樹是不含有環的，即本題情境下，刪去環中的任意一條邊即可變成一棵生成樹。且環中有 n 個頂點故有 n 條邊可選擇，因此可以生成 n 種生成樹。

11.無向圖 G = (V,E)，|V| = n，|E| = e，且圖 G 是森林。那么該圖 G 中必有（ ）棵樹。
A. n
B. e
C. n - e
D. 1

11.【參考答案】?C
【解析】?(核心：將森林轉化成一棵樹的思想) 假設該森林中有 x 棵樹。具有 n 個頂點的樹有 n - 1 條邊。將每一棵樹連接到一個新增的結點，則變成了另一棵樹，此時森林中的所有樹變成了一棵新樹，且頂點數是 n + 1，邊數是 e + x，由樹的頂點和邊的關系可知，樹的頂點數等于邊數加一，所以有 n + 1 = e + x + 1，可解得 x = n - e。選擇 C。

12.設無向圖的頂點個數為 n，則該圖最多有（ ）條邊。
A. n - 1
B. n (n - 1)/2
C. n (n + 1)/2
D. 0

12.【參考答案】?B
【解析】?完全圖為該圖含有最多條邊的情況。即每個頂點都和其余 n - 1 個頂點都有邊相連。

13.含有 n 個頂點的完全有向圖的邊數為（ ）。
A. n2
B. n (n + 1)
C. n/2
D. n (n - 1)

13.【參考答案】?D
【解析】?有向圖的完全圖是任意兩個頂點之間都有兩條方向相反的邊相連。因此可得答案 D。相比較而言，無向完全圖的邊數則是比有向完全圖的邊數少一半。

14.一個有 n 個結點的無向圖，最少有（ ）個連通分量；最多有（ ）。
A. 0
B. 1
C. n - 1
D. n

14.【參考答案】?B，D
【解析】?圖的極大連通子圖稱為圖的連通分量。當 n 個頂點兩兩之間都是連通的（即有路徑），則此時只具有 1 個連通分量，屬于最少的情況。當 n 個頂點各自獨立，不存在邊，則此時有 n 個連通分量，屬于最多的情況。綜上，選擇 B，D。

15.在一個無向圖中，所有頂點的度數之和等于所有邊數的（ ）倍；在一個有向圖中，所有頂點的入度之和等于所有頂點出度之和的（ ）倍。
A. 1/2
B. 2
C. 1
D. 4

15.【參考答案】?B，C
【解析】?在無向圖中，每一條邊兩端各有一個頂點，且這兩個頂點的度均算了一次。因此，所有頂點的度數之和等于所有邊數的兩倍。在有向圖中，一條邊的兩端仍然各有一個頂點，該邊為兩端頂點貢獻了一單位的入度和一單位的出度 ，且總是成對出現。因此，有向圖所有頂點的入度必然等于所有頂點的出度。綜上，選擇 B，C。

16.若一有向圖有 6 個頂點，11 條邊，問該圖是稠密圖還是稀疏圖？（ ）
A. 稠密圖
B. 稀疏圖
C. 都是
D. 都不是

16.【參考答案】?B
【解析】?根據稠密圖和稀疏圖判斷公式，|E|=11 小于 |V|log?|V| = 6×log?6 ≈ 15.51，所以該

圖為稀疏圖。

17.下列有關圖的定義，錯誤的是（ ）。
A. 無向圖的所有頂點數之和可能不是邊數的兩倍
B. 若存在一個含有 n 個頂點，且邊數最小值大于 n - 2 的圖，那么該圖一定含有環
C. 有向圖所有頂點的入度與出度之和相等，并且等于邊數
D. 如果從 u 到 v 根本不存在路徑，則可記該距離為無窮

17.【參考答案】?B
【解析】?A 正確，只有一個頂點，沒有邊的無向圖為此特例。B 錯誤，首先沒有說明是無向圖還是有向圖。其次，對于無向圖有大于 n - 1 條的邊數，才能保證該無向圖有環。C、D 正確。對于 D 選項，可能有點誤導性，考生需要根據具體題目所給含義進行判斷，不一定每一次都是用無窮表示不存在路徑。

18.無向圖 G 是一個包含 n（n≥2 且 n 為偶數）個頂點的圖，此圖中有且僅有兩個連通分量，且每個連通分量也可看作一個完全圖，則圖 G 中最少包含幾條邊？

18.【參考答案】?(n2?2n)/4。設兩個連通分量的頂點數分別為a、b，有a+b=n。因每個連通分量都是完全圖，所以兩個連通分量共有a(a?1)/2+b(b?1)/2條邊。a(a?1)/2+b(b?1)/2=[(a+b)2?(a+b)?2ab]/2=(n2?n)/2?ab。由基本不等式可知，最少有(n2?n)/2?(n2/4)=(n2?2n)/4條邊。

19.(1) 若 G?是一個具有 n 個頂點的連通無向圖，則 G?最多有多少條邊？G?最少有多少條邊？
(2) 若 G?是一個具有 n 個頂點的強連通有向圖，則 G?最多有多少條邊？G?最少有多少條邊？
(3) 若 G?是一個具有 n 個頂點的弱連通有向圖，則 G?最多有多少條邊？G?最少有多少條邊？
(說明：弱連通有向圖指把有向圖看作無向圖時，仍是連通的)

19.【參考答案】
(1) 答案：最多n(n?1)/2，最少n?1。當該連通無向圖同時又是完全圖時，具有最多的邊，共n(n?1)/2條邊。當該連通無向圖正好是一棵樹時（即不存在回路），此時具有最少的邊，共n?1條邊。注意：連通無向圖最少邊數的情況不是剛好成環的情況，因為是無向圖，所以不需要成環就可以是連通圖了。
(2) 答案：最多n(n?1)，最少n。當圖G2?又剛好是完全圖時，此時具有最多的邊，共n(n?1)條邊。當圖G2?剛好成環時，此時具有最少的邊，共n條邊。
(3) 答案：最多n(n?1)，最少n?1。當圖G3?剛好是完全圖時，具有最多的邊，共n(n?1)條邊。當圖G3?正好是一棵 “有向樹” 時，此時具有最少的邊，且剛好滿足弱連通圖的定義，共有n?1條邊。

6.1.4 真題演練

20.【2009】下列關于無向連通圖特性的敘述中，正確的是（ ）。
I. 所有頂點的度之和為偶數
II. 邊數大于頂點個數減 1
III. 至少有一個頂點的度為 1
A. 只有 I
B. 只有 II
C. I 和 II
D. I 和 III

20.【參考答案】?A
【解析】?Ⅰ 對，無向圖中所有頂點的度之和恰好為邊數的 2 倍。Ⅱ 錯，當無向連通圖為生成樹的時候，邊數剛好等于頂點數 - 1。Ⅲ 錯，若無向連通圖為一個環，此時所有頂點的度均不為 1。

21.【2010】若無向圖 G = (V, E) 中含有 7 個頂點，要保證圖 G 在任何情況下都是連通的，則需要的邊數最少是（ ）。
A. 6
B. 15
C. 16
D. 21

21.【參考答案】?C
【解析】?關鍵詞 “任何情況下”、“連通”。若沒有邊數最少的限制，對于 “任何情況下都要連通” 的要求，很容易會聯想到完全圖。但本題是有 “邊數最少” 的限制，可以在 6 個頂點是完全圖的條件下再加一條邊即可滿足題意。即6(6?1)/2=15，答案為15+1=16，選 C。
說明：可能有考生會認為只要滿足圖是 “生成樹” 即可，因此要選擇 A。生成樹確實是連通的，不過該圖不一定在任何情況下都是一棵生成樹。

22.【2017】已知無向圖 G 含有 16 條邊，其中度為 4 的頂點個數為 3，度為 3 的頂點個數為 4，其他頂點的度均小于 3。圖 G 所含的頂點個數至少是（ ）。
A. 10
B. 11
C. 13
D. 15

22.【參考答案】?B
【解析】?本題的關鍵是：“無向圖邊數的 2 倍等于所有頂點的度之和。”，且題目要求 “頂點個數至少是”。因此令度小于 3 的頂點有x個，即度為 2 的頂點有x個，由題意得16×2=4×3+3×4+2x，解得x=4。因此G的頂點個數至少為3+4+4=11個。
提示：若本題假設其余頂點的度均為 2 不可以解得整數的話，那么可以考慮假設其余頂點的度均為 1。一般而言這兩者是可以解出正確答案的，若出現有度為 1，也有度為 2 的頂點，則題目需要增加額外信息。