/ ALGORITHM

支配集、覆盖集、独立集与匹配

  1. 点支配集

    支配与支配集:设无向图 $G(V,E)$ ,顶点集合 $V’ \subseteq V $ ,若对于 $ \forall v \in (V-V’) $ ,$ \exists u \in V’$ ,使得 $ (u,v) \in E$ ,则称 $u$ 支配 $v$ ,并称 $V’$ 为 $G$ 的一个 点支配集合

    极小支配集:若支配集 $V’$ 的任何真子集都不是支配集,则称 $V’$ 是极小支配集。

    最小支配集:顶点数最少的支配集称为最小支配集。

    点支配数:最小支配集中的顶点数称为点支配数,记作 $γ0(G)$ 或简记为 $γ0$。

    性质:若 $G$ 中无孤立点,则存在一个支配集 $V’$ ,并且 $V-V’$ 也是一个支配集

  2. 点覆盖集

    点覆盖集:设无向图为 $G(V, E)$ ,顶点集合 $V’⊆V$ ,若对于 $∀e∈E, ∃v∈V’$ ,使得 $v$ 与 $e$ 相关联,则称 $v$ 覆盖 $e$,并称 $V’$ 为 $G$ 的一个点覆盖集或简称点覆盖。

    极小点覆盖:若点覆盖 $V’$ 的任何真子集都不是点覆盖, 则称 $V’$ 是极小点覆盖

    最小点覆盖:顶点个数最少的点覆盖称为最小点覆盖

    点覆盖数:最小点覆盖的顶点数称为点覆盖数, 记作 $α0(G)$ ,简记为 $α0$

    性质:在连通图中,点覆盖必然是支配集,反之支配集却未必是点覆盖

  3. 点独立集

    点独立集:设无向图为 $G(V, E)$ ,顶点集合 $V’⊆V$ ,若 $V’$ 中任何两个顶点均不相邻,则称 $V’$ 为 $G$ 的点独立集,或简称独立集。

    极大点独立集:若在 $V’$ 中加入任何顶点都不再是独立集,则称 $V’$ 为极大点独立集。

    最大点独立集:顶点数最多的点独立集称为最大点独立集。

    点独立数:最大点独立集的顶点数称为点独立数, 记作β0(G),简记为β0。

    性质:图G的极大独立集必然是它的极小支配集,反之则不一定成立
    一个独立集是极大独立集当且仅当它是支配集

  4. 边覆盖集

    覆盖与边覆盖集:设无向图为 $G(V, E)$ ,边的集合 $E’⊆E$ ,若对于 $∀v∈V,∃e∈E’$ ,使得:$v$ 与 $e$ 相关联,则称 $e$ 覆盖 $v$ ,并称 $E’$ 为边覆盖集,或简称边覆盖。

    极小边覆盖:若边覆盖 $E’$ 的任何真子集都不是边覆盖, 则称 $E’$ 是极小边覆盖。

    最小边覆盖:边数最少的边覆盖集称为最小边覆盖。

    边覆盖数:最小的边覆盖所含的边数称为边覆盖数, 记作 $α1(G)$ ,或简记为 $α1$。

  5. 边独立集(匹配)

    边独立集(匹配):设无向图为 $G(V, E)$ ,边的集合 $E’⊆E$,若 $E’$ 中任何两条边均不相邻,则称 $E’$ 为 $G$ 的边独立集,也称 $E’$ 为 $G$ 的匹配

    极大匹配:若在 $E’$ 中加入任意一条边所得到的集合都不是匹配,则称 $E’$ 为极大匹配。

    最大匹配:边数最多的匹配称为最大匹配。

    边独立数:最大匹配的边数称为边独立数或匹配数,记作 $β1(G)$ ,简记为 $β1$。

  6. 总结

    最大匹配 && 最小边覆盖
    设最大匹配为 $M_{max}$ ,最小边覆盖为 $F_{min}$ ,由于一个匹配能够覆盖两个点,那么最大匹配已经覆盖了 $2\times M_{max}$ 个点,在这个基础上,我们每 增加一条边,最多可以覆盖一个点(如果能够覆盖两个点,说明之前不是最大匹配),则覆盖所有点还需要增加 $ |V|-2\times M_{max} $ 条边,即 $F_{min} = M_{max} + |V|-2\times M_{max}$
    结论: $|V| = M_{max} + F_{min} $

    最大点独立集 && 最小点覆盖
    设最大独立集为 $S_{max}$ ,最小点覆盖为 $S_{min}$ ,因为独立集之间不存在有边,那么独立集以外的点就覆盖了所有边(若有点没有覆盖边,那么它就可以属于独立集)
    结论: $|V| = S_{max} + S_{min} $

    对于最大边独立(匹配)与最小边覆盖,最大点独立与最小点覆盖,求出其中一个就能求解出另外一个

    对于边(最大边独立…),二分图可以用匈牙利算法和网络流解决,一般图一般使用开花树 $Edmonds$ 算法解决

    对于点(最大点独立…),二分图中用最小点覆盖等于最大匹配可以解决,一般图则是NP问题,暂无高效算法

  7. 贪心法求树的最小支配集

int pre[maxn];//存储父节点  
bool visit[maxn];//DFS标记数组  
int newpos[maxn];//遍历序列  
int now;  
int n, m;  

int head[maxn];//链式前向星  
struct Node  
{  
	int to;  
	int next;  
};  
Node edge[maxn];  

void DFS(int x)  
{  
	newpos[now ++] = x;//记录遍历序列  
	for(int k = head[x]; k != -1; k = edge[k].next)  
	{  
		if(!visit[ edge[k].to ])  
		{  
			visit[ edge[k].to ] = true;  
			pre[edge[k].to] = x;//记录父节点  
			DFS(edge[k].to);  
		}  
	}  
}  

int MDS()  
{  
	bool s[maxn] = {0};  
	bool set[maxn] = {0};  
	int ans = 0;  
	for(int i = n - 1; i >= 0; i--)  //逆序进行贪心  
	{  
		int t = newpos[i];  
		if(!s[t])   //如果当前点没被覆盖  
		{  
			if(! set[ pre[t] ])  //当前点的父节点不属于支配集  
			{  
				set[ pre[t] ] = true;//当前点的父节点加入支配集  
				ans ++;  //支配集节点个数加 1  
			}  
			s[t] = true; //标记当前点已被覆盖  
			s[ pre[t] ] = true;// 标记当前点的父节点被覆盖  
			s[ pre[ pre[t] ] ] = true;//标记当前点的父节点的父节点被覆盖  
		}  
	}  
	return ans;  
}  

int main()  
{  
	/* read Graph message*/ //建图  
	memset(visit, false, sizeof(visit));//初始化  
	now = 0;  
	visit[1] = true;  
	pre[1] = 1;  
	DFS(1);//从根节点开始寻摘遍历序列  
	MDS();  
	return 0;  
}