加權圖

習題預習

1. 在一個連通的有向加權圖中，如何找出最短路徑？

2. 在一個無向加權圖中，如何找出最小生成樹？

3. 在一個加權圖中，如何找到最小加權匹配？

4. 在一個有權重的二分圖中，如何找到最大匹配？

5. 在一個有向加權圖中，如何找到可以到達目標節點的最長路徑？

說明知識

加權图通常是有向或无向的，其边缘被赋予了具有相关属性的值，例如距离、时间成本等。这些属性可以表示连接节点之间的关系的任何东西；这可能是一条路线、电线杆之间的距离、两个城市之间的铁路线路、人际关系的力量或任何其他类型的连接。加权图可以用来表示各种情况，例如路径规划，网络流量和社交网络分析。

下面是一个简单的示例，其中展示了带有加权边缘的无向图。在这个图中，每个节点之间的边缘都有一个数字，表示它们之间的距离或成本：

此示例显示了从节点 A 到节点 D 的两条不同路径，每条路径都有不同的总成本。从 A 到 D 节点的最短路径是 A-B-G-E-D，它的总成本为 6。另一条路径 A-C-G-D 的总成本为 8。

总之，加权图意味着每个边缘都有与其相关的权重，表示连接节点之间的关系的某些属性。这些图可以用于许多实用的应用程序中，例如路径搜索和社交网络分析。

彙總重點

1. 权重Weight：在权重图（weighted graph）中，每条边都有与之关联的权重（weight），表示两个顶点之间的距离或成本。在有向图中，每个顶点的出度和入度可能不相等，因为两个顶点之间的边可能拥有不同的权重。

2. 最短路径Shortest Path：在权重图中，最短路径指的是图中两个顶点之间的最短路线，它由带有最小权重的边构成。在计算最短路径时，可以使用多种算法，例如Dijkstra算法、Bellman-Ford算法和Floyd-Warshall算法等。

3. 最小生成树Minimum Spanning Tree：在权重图中，最小生成树指的是连接所有顶点的无向子图，它由权重最小的边构成。在计算最小生成树时，可以使用Kruskal算法或Prim算法等。

4. 可达性Connectivity：在权重图中，连接性是指图中的顶点之间是否存在路径。可以使用深度优先搜索（DFS）或广度优先搜索（BFS）等算法来确定两个顶点之间是否存在路径。

5. 网络流Network Flow：在权重图中，网络流指的是通过图中边缘的最大流量。可以使用最大流算法来计算网络流。

6. 度数Degree：在权重图中，度数指的是每个顶点与其他顶点相连的边数。在有向图中，每个顶点的出度和入度可以不同。

7. 密度Density：在权重图中，密度指的是实际边数与可能的最大边数之比。在有向图中，最大边数可能会随顶点的入度和出度不同而变化。

知識測驗

1. 在一個城市裡，有$N$個建築物和$M$條道路，每條道路連接兩個建築物並且有一個權重。你需要選擇兩個建築物，使得它們之間的路徑權重最小，並輸出這個最小權重。如果兩個建築物之間沒有路徑，輸出 $-1$。

答案: 該問題可以使用$floyd$或者$Dijkstra$最短路算法解決。

2. 給定一個無向連通帶權圖$G=(V,E)$，請找到一棵權值總和最小的生成樹。

答案: 該問題可以使用$Kruskal$或者$Prim$算法解決。

3. 給定一個$N$家店家球鞋的價格，和$M$家店家襪子的價格。你打算買一雙球鞋和一雙襪子，在許可的價格範圍內使總價最小。請注意，許可範圍不同。請您輸出此次最短距離。如果無法購買到符合條件的球鞋和襪子，輸出 $-1$。

答案: 該問題可以使用最小擴展匹配算法解決。

4. 一個國家有$\text{N}$個城市、$\text{M}$條道路，所有道路都是雙向的。還有$\text{K}$個護城河，每個護城河都有一個起點和終點，你需要保護城市，使得所有的城市都在護城河覆蓋的範圍內。你可以挑選一些護城河，沿途覆蓋到的城市是必定保護好的，而且護城河總長度不超過$maxK$。請找到最小的最大值$maxX$，使得沒有城市在護城河覆蓋範圍外。

答案: 該問題可以使用二分答案加狀態壓縮最短路算法解決。

5. 一個有向圖$G=(V,E)$，每個邊有一個順序數字。你需要找到一條從點$s$到$t$的最短路，使得這條路上邊的順序總和最小。

答案: 該問題可以使用网络流算法解决。