圖

習題預習

1. 給定一個圖，如何判斷它是否為樹？
2. 在一個有向圖中，有多少條簡單路徑從一個點到另一個點？
3. 在一個加權圖中，如何找到一條從起點到終點的最短路徑？
4. 如何找到一個圖的最小生成樹？
5. 如何將一個圖分為幾個連通分量？

說明知識

Graph是一種數學計算機科學中的資料結構，它由一組節點（也稱為頂點）和這些節點之間的連接關係（也稱為邊）組成。在Graph中，節點表示某種實體，連接則表示實體之間的關係。Graph可以用於建立各種各樣的系統和應用，例如計算機網絡、社交媒體分析和交通路線規劃。

下面舉例幾種不同的Graph：

1. 有向圖（Directed Graph）：每條邊都有一個方向，表示從其中一個節點到另一個節點的關係。例如，互聯網上的網頁可以用有向圖表示，其中節點表示網頁，邊表示網頁之間的超連結關係。

2. 無向圖（Undirected Graph）：邊沒有方向，表示兩個節點之間沒有明確的方向。例如，交通路線可以用無向圖表示，其中節點表示路口，邊表示道路。

3. 帶權重圖（Weighted Graph）：邊有權重或成本，表示從一個節點到另一個節點的距離或花費。例如，路徑規劃可以用帶權重圖表示，其中權重表示路徑的行駛距離或時間。

4. 帶標籤圖（Labeled Graph）：每個節點都有一個標籤或名稱，用於識別節點。例如，社交媒體上的用戶可以用帶標籤圖表示，其中節點是用戶，標籤是用戶名。

總之，Graph可以用於描述實體之間的各種關係，其應用廣泛，且在計算機科學中扮演著重要的角色。

彙總重點

1. Graph是一種用於表示物件之間關係的數學結構。

2. Graph由兩個要素組成：節點（node）和邊（edge）。

3. 節點可以表示物件，邊表示物件之間的關係。

4. Graph可以是有向的（每條邊都有一個方向）或無向的（沒有方向）。

5. Graph可以是加權的（每條邊有一個權值）或非加權的。

6. Graph可以用來解決許多問題，例如最短路徑、社交網絡分析和任務分配等。

7. 常見的Graph算法包括BFS（廣度優先搜索）、DFS（深度優先搜索）和最小生成樹等。

8. Graph在許多領域中都有應用，如計算機科學、社會科學、物理學和生物學等。

知識測驗

1. 根據下列的圖標，計算在2008年到2010年期間，紅色線條所表示的商品的年平均售價增加了多少？

答案：$8 - 6 = 2$，紅色線條的年平均售價增加了2元。

2. 下列為2010年某公司每月的收入和利潤，請問該公司的最佳月份為何？

答案：最佳月份為2月，其利潤到達最高點。

3. 下列圖表顯示某公司每年的總交易額，請問哪一年的營業額達到最高點？

答案：2014年，營業額達到最高點。

4. 下列圖表顯示某地區年平均溫度的變化，請問年平均溫度最高的是哪一年？

答案：2007年，年平均溫度最高。

5. 下列圖表為某人反覆測量自己的體重，請問他的體重變化在哪段時期變化最明顯？

答案：2018年10月至12月，體重變化最明顯。