文章目录
- 一、证明思路
- 1. 权重的唯一性
- 2. 权重不唯一时的多样性
- 3. 形式化证明
- 4. 图的特性和边的可替换性
- 二、简单算法实现
数据结构：最小支撑树
在图论中，使用 Kruskal 算法构建最小生成树 (MST) 时，是否存在多个不同的最小生成树取决于图中边的权重。如果所有边的权重都是唯一的，那么最小生成树也将是唯一的。然而，如果存在具有相同权重的边，并且这些边可以互换而不改变整体的最小权重，那么可能存在多个最小生成树。
一、证明思路
以下是证明图中可能存在多个最小生成树的思路：
1. 权重的唯一性
如果图中所有边的权重都是唯一的，那么任何时候选择下一条边添加到树中时都只有一个最优选择。这意味着构建过程中没有任何决策分支，从而保证了最小生成树的唯一性。
2. 权重不唯一时的多样性
如果存在多条具有相同最小权重的边，且它们连接的顶点不会形成环，那么选择不同的边将可能导致构建不同的最小生成树。在这种情况下，每个选择都可以导致不同的树结构，而总权重仍然相同。
3. 形式化证明
要形式化证明可能存在多个最小生成树，可以采用以下步骤：
-
定义：假设一个连通图 G = ( V , E ) G = (V, E) G=(V,E)，其边 E E E 中存在权重相等的边。假设 e 1 e_1 e1 和 e 2 e_2 e2 是权重相等的边，且它们连接不同的顶点对。
-
构建MST：使用 Kruskal 算法开始构建 MST。当到达选择 e 1 e_1 e1 或 e 2 e_2 e2的步骤时，两条边都可选，因为选择任意一条都不会与已选择的边形成环，且权重相同。
-
分叉：选择 e 1 e_1 e1 后继续构建 MST，完成后得到 T 1 T_1 T1。重置，再选择 e 2 e_2 e2，继续构建另一个 MST，得到 T 2 T_2 T2。
-
比较：如果 T 1 T_1 T1和 T 2 T_2 T2 在结构上不同，这证明了存在多个最小生成树。
4. 图的特性和边的可替换性
在实际操作中，可以通过检查图中边权重的分布来预判是否可能存在多个 MST。如果能够在不违反最小权重总和的前提下替换边，则表明存在多个 MST。
总结来说，Kruskal 算法在存在权重相同且可交换的边时，可能会构建出结构不同但权重相等的多个最小生成树。这种情况下，具体的 MST 可能依赖于算法处理边的顺序。
二、简单算法实现
要判断Kruskal算法下，最小支撑树是否相同：
- 我们在最小支撑树中加入一条边e，使得最小支撑树形成一个环，如果环中存在一条其他的边和e的权值相同，则最小支撑树不唯一。因为删掉原来最小支撑树环中和e权值相同的一条边，将e添加进去，则仍然构成一个最小支撑树，并且和原来的最小支撑树不同。
- 我们可以发现，只有具有相同权值的非最小支撑树中的边才可能形成和原最小支撑树不同的最小支撑树。我们可以在最小支撑树中加入它来判断形成的环中是否和它有相同权值的边，来判断是否有多种最小支撑树。但这样实现非常复杂，我们可以考虑删除原来最小支撑树中与 非最小支撑树边集中的某条边 权值相同的 边（标记即可），来判断原边集删除该边后能否生成相同权值的最小支撑树。
- 为了方便，我们直接在最小支撑树边集合里面标记！然后下一次生成最小支撑树时再忽略该边。如果能生成同样权重的最小生成树则表示最小生成树不唯一。
为何使用tuple类型而不使用结构体，在C++STL——tuple中有讲到。
#include<bits/stdc++.h>
using namespace std;
class UnionFind {
public:
UnionFind(int c): n(c) {
parent.resize(c);
rank.resize(c, 0); // 初始化秩数组
for (int i = 0; i < c; ++i)
parent[i] = i;
}
int find(int x) {
if (parent[x] != x)
parent[x] = find(parent[x]); // 路径压缩
return parent[x];
}
void Union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
// 按秩合并
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else {
parent[rootY] = rootX;
rank[rootX] += 1; // 如果秩相同，则任选一个作为根，并增加其秩
}
minus();
}
}
int n;
private:
vector<int> parent;
vector<int> rank; // 秩
void minus() { --n; } // 减少连通分量的数量
};
int ans = INT_MAX;
int N,M;
tuple<int,int,int> flag_Node;
bool flag = false;
bool Kruskal(vector<tuple<int,int,int>> & edge,set<tuple<int,int,int>> & st){
UnionFind uf(N);
int weight = 0;
for(auto & i : edge){
if(!flag || i != flag_Node)
if(uf.find(get<1>(i)) != uf.find(get<2>(i))){
uf.Union(get<1>(i),get<2>(i));
weight += get<0>(i);
if(!flag)//还没有标记则说明是第一次生成时期
st.insert(i);
}
}
if(uf.n == 1 && weight == ans) return false;//表示存在多种最小支撑树
if(uf.n == 1 && !flag) ans = min(ans,weight);//求得最小支撑树的权重
if(uf.n != 1 && !flag) {//没有连通，并且是第一次生成。
cout << "No MST" << endl;
cout << uf.n;
return false;
}
return true;
}
int main(void){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> N >> M;
vector<tuple<int,int,int>> edge;
for(int i = 0;i < M;++i){
int v1,v2,weight;
cin >> v1 >> v2 >> weight;
edge.push_back({weight,v1-1,v2-1});
}
//排序边权
sort(edge.begin(),edge.end());
set<tuple<int,int,int>> st;//保存最小生成树的边
if(!Kruskal(edge, st)) {//生成最小支撑树
return 0;
}
cout << ans <<'\n';
flag = true;//开始判断是否存在最小支撑树
for(auto & i : st){
flag_Node = i;//标记该边，之后生成最小支撑树不考虑该边。
if(!Kruskal(edge,st)){//复用一下
cout << "No";
return 0;
}
}
cout << "Yes";
return 0;
}
清晰版：
#include<bits/stdc++.h>
using namespace std;
class UnionFind {
public:
UnionFind(int c): n(c) {
parent.resize(c);
rank.resize(c, 0); // 初始化秩数组
for (int i = 0; i < c; ++i)
parent[i] = i;
}
int find(int x) {
if (parent[x] != x)
parent[x] = find(parent[x]); // 路径压缩
return parent[x];
}
void Union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
// 按秩合并
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else {
parent[rootY] = rootX;
rank[rootX] += 1; // 如果秩相同，则任选一个作为根，并增加其秩
}
minus();
}
}
int n;
private:
vector<int> parent;
vector<int> rank; // 秩
void minus() { --n; } // 减少连通分量的数量
};
int ans = INT_MAX;
int N,M;
tuple<int,int,int> flag_Node;
bool Kruskal(vector<tuple<int,int,int>> & edge,set<tuple<int,int,int>> & st){
UnionFind uf(N);
int weight = 0;
for(auto & i : edge){
if(uf.find(get<1>(i)) != uf.find(get<2>(i))){
uf.Union(get<1>(i),get<2>(i));
weight += get<0>(i);
st.insert(i);
}
}
ans = weight;
if(uf.n != 1) {//没有连通，并且是第一次生成。
cout << "No MST" << endl;
cout << uf.n;
return false;
}
return true;
}
bool unique(vector<tuple<int,int,int>> & edge,set<tuple<int,int,int>> & st){
UnionFind uf(N);
int weight = 0;
uf.n = N;
for(auto & i : edge){
if(i != flag_Node)
if(uf.find(get<1>(i)) != uf.find(get<2>(i))){
uf.Union(get<1>(i),get<2>(i));
weight += get<0>(i);
}
cout << uf.n<<' ';
}
if(uf.n == 1 && weight == ans) return false;//表示存在多种最小支撑树
return true;
}
int main(void){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> N >> M;
vector<tuple<int,int,int>> edge;
for(int i = 0;i < M;++i){
int v1,v2,weight;
cin >> v1 >> v2 >> weight;
edge.push_back({weight,v1-1,v2-1});
}
//排序边权
sort(edge.begin(),edge.end());
set<tuple<int,int,int>> st;//保存最小生成树的边
if(!Kruskal(edge, st)) {//生成最小支撑树
return 0;
}
cout << ans <<'\n';
for(auto & i : st){
flag_Node = i;//标记该边，之后生成最小支撑树不考虑该边。
if(!unique(edge,st)){
cout << "Yes";
return 0;
}
}
cout << "No";
return 0;
}
