无向图的最大独立轨。
独立轨:设A、B是无向图G的两个顶点,从A到B的两条没有公共内部顶点的路径互称为独立轨。A到B的独立轨的最大条数,记作P(A,B)。
设A、B是无向图G的两个不相邻的顶点,最少要删除多少个顶点才使得A和B不再连通?答案是P(A,B)个。
关于无向图G顶点连通度K(G)与顶点独立轨之间的关系。
Menger定理:
K(G) = |V(G)| - 1 当G是完全图。
K(G) = min(P(A,B))当G不是完全图。
求P(A,B)方法如下。
(1)为了求P(A,B),需要构造一个容量网络。
1、原图G中的每个顶点v变成网络N中的两个顶点v'和v'',顶点v'到v''有一条弧连接,即<v',v''>,其容量为1。
2、原图G中的每条边e = (u, v),在网络N中有两条弧e' = <u'',v'>和e'' = <u',v''>,e'和e''的容量均为INF。
3、另A''为源点,B'为汇点。
(2)求从A''到B'的最大流。
(3)流出A''的一切弧的容量和sigma F(e),即为P(A,B),所以具有流量为1的弧(v',v'')对应的顶点构成了一个割顶集,在图G中去掉这些顶点后,则A和B不再连通了。
有了求P(A,B)的算法基础,就可以得出K(G)的求解思路:首先设K(G)的初始值为INF,然后分析图G中的每一对顶点,如果A、B不相邻,则用最大流的方法求出P(A,B)和对应的割顶集。如果P(A,B)小于当前的K(G),则K(G) = P(A,B);如此直到不相邻的顶点分析完为止,即可求出K(G)。
具体的实现时,我们可以固定一个源点,枚举每个汇点,从而求出K(G)。
实际上拆点、连边时,我们一般是把<u',u''>置1,<u'', v'>与<v'',u'>置INF。
附 POJ 1966源代码。
#include <iostream> #include <cstdlib> #include <cstdio> #include <cstring> #include <string> using namespace std; const int MAXN = 105; const int MAXM = 105*105; const int INF = 0x3f3f3f3f; struct Edge { int v, next; int f; }edge[MAXM]; int cnt; int n, m; int first[MAXN], level[MAXN]; int q[MAXN]; void init() { cnt = 0; memset(first, -1, sizeof(first)); } void read_graph(int u, int v, int f) { edge[cnt].v = v, edge[cnt].f = f; edge[cnt].next = first[u], first[u] = cnt++; edge[cnt].v = u, edge[cnt].f = 0; edge[cnt].next = first[v], first[v] = cnt++; } int bfs(int s, int t) { memset(level, 0, sizeof(level)); level[s] = 1; int front = 0, rear = 1; q[front] = s; while(front < rear) { int x = q[front++]; if(x == t) return 1; for(int e = first[x]; e != -1; e = edge[e].next) { int v = edge[e].v, f = edge[e].f; if(!level[v] && f) { level[v] = level[x] + 1; q[rear++] = v; } } } return 0; } int dfs(int u, int maxf, int t) { if(u == t) return maxf; int ret = 0; for(int e = first[u]; e != -1; e = edge[e].next) { int v = edge[e].v, f = edge[e].f; if(level[v] == level[u] + 1 && f) { int Min = min(maxf-ret, f); f = dfs(v, Min, t); edge[e].f -= f; edge[e^1].f += f; ret += f; if(ret == maxf) return ret; } } return ret; } int Dinic(int s, int t) { int ans = 0; while(bfs(s, t)) ans += dfs(s, INF, t); return ans; } void init_flow() //重置网络流为初始值 { for(int i = 0; i < cnt; i += 2) { edge[i].f += edge[i^1].f; edge[i^1].f = 0; } } void read_case() { init(); for(int i = 0; i < n; i++) { read_graph(i, i+n, 1); } for(int i = 0; i < m; i++) { int u, v; while(getchar() != '(' ) ; scanf("%d,%d)", &u, &v); read_graph(u+n, v, INF); read_graph(v+n, u, INF); } } void solve() { read_case(); int ans = INF; for(int i = 1; i < n; i++) { ans = min(ans, Dinic(0+n, i)); //以0''为源点,枚举其他顶点i' init_flow(); } if(ans == INF) ans = n; printf("%d\n", ans); } int main() { while(~scanf("%d%d", &n, &m)) { solve(); } return 0; }