DataStructure Graph Examples
Examples for Graphs
Lecture Notes for Data Structure.
图论总是非常有意思的！但是图论算法迁移到实际问题中总是需要费一番功夫，因此，笔者将在这篇博客中介绍经典的图论算法的几道例题，望有所收获。
Message Transportation
MuLinjiu的老家A town（二维平面上）科技十分落后，A town有很多居民聚集地，他们之间信息不通，现在MuLinjiu想为自己的家乡做出一些贡献。已知MuLinjiu有任意多条电缆，每条电缆的长度不超过d（d待确定），如果两个聚集地有电缆相连，则他们可以通信。此外，MuLinjiu还掌握着s个无线电通信装置，同时拥有无线电通信装置的两个村庄可以通信（不限距离）。现在我们要找出一种方案使得所有的村庄可以互相通信时（可以通过别的村庄中转，如A与B可通信，B与C可通信，即认为A与C也可通信）d可以取得的最小值。
再描述
Consider $G = (V,E)$, we have $|V| = p$, for the initial statement, all vertices have a edge connected to the other.
We need to find a subgraph $G’ \subseteq G$, $G’ = (V, E’)$. We need to ensure that $G’$ is still connected and the maximum length edge is the shortest.
这个问题可以转化为图论中的最小生成树（MST）问题。我们需要构建一个图，其中：
- 顶点：代表村庄。
- 边：代表村庄之间的通信方式。
- 如果两个村庄都分配了无线电装置，它们之间的边的权重可以视为 0（因为不限距离）。
- 否则，它们之间的边的权重是它们之间的欧几里得距离。
然而，无线电装置的数量是有限的（s 个），我们需要选择 s 个村庄来放置无线电装置，以最小化生成树中的最大边（即 d）。
思路
我们先不考虑无线电装置，假设$s = 0$，那么此时就是非常经典的最小生成树问题。我们需要找到最短的可以生成一颗联通树的边，因此对边进行排序之后使用Krustal算法。
现在考虑无线电装置的作用：无线电装置可以对生成的树做进一步的优化：对于较长的边，直接使用无线电代替。我们有$s$个无线电可以来优化，因此我们可以最多**覆盖$s-1$**条边（因为他是一颗最小生成树），但是他需要保证这$s$个节点和$s-1$条边是联通的。
换句话说，我们已经构建了一个$G’ = (V’, E’)$，我们需要利用无线电装置对这个图进一步优化！因此，我们的第二个任务就是在既有生成树的基础上，选择一个包含 $s$个村庄的连通子图，使得这些村庄之间的最大边尽可能大。