[关闭]
@LinKArftc 2015-08-26T13:59:31.000000Z 字数 4933 阅读 1972

图论

图论

易混淆概念

平凡图（trivial graph）

只有一个顶点的图，即阶n = 1 的图称为平凡图。相反，阶n>1 的图称为**非平凡图（nontrivial graph）**。

零图（null graph）

**边**的集合E(G)为空的图，称为零图。

关联

指的是边与点之间的关系

图G 的最小度（minimum degree）

图G 所有顶点的最小的度数，记为δ(G)。

图G 的最大度（maximum degree）

图G 所有顶点的最大的度数，记为Δ(G)。

度序列（degree sequence）

若把图G 所有顶点的度数排成一个序列s，则称s 为图G 的度序列

序列是可图的（graphic）

一个非负整数组成的有限序列如果是某个无向图的度序列，则称该序列是可图的。
判定一个序列是否是可图的，有以下**Havel-Hakimi 定理**。

路径

path，又叫**通路**

简单路径

路径上各顶点互相不重复

回路

若路径上第一个顶点vi 与最后一个顶点vj 重合，则称这样的路径为回路

简单回路

除第一个和最后一个顶点外，没有顶点重复的回路称为简单回路。简单回路也称为圈（cycle）

定理

Havel-Hakimi 定理

由非负整数组成的非增序列s：d1, d2, …, dn(n ≥ 2, d1 ≥ 1)是可图的，当且仅当序列
s1: d2 – 1, d3 – 1, …, dd1+1 – 1, dd1+2, …, dn
是可图的。

序列s1 中有n-1 个非负整数，s 序列中d1 后的前d1 个度数（即d2～dd1+1）减1 后构成s1 中的前d1 个数。
例如，判断序列s: 7, 7, 4, 3, 3, 3, 2, 1 是否是可图的。删除序列s 的首项7，对其后的7 项每项减1，得到：6, 3, 2, 2, 2, 1, 0。继续删除序列的首项6，对其后的6 项每项减1，得到：2, 1, 1, 1, 0, -1，到这一步出现了负数。由于图中不可能存在负度数的顶点，因此该序列不是可图的。
再举一个例子，判断序列s: 5, 4, 3, 3, 2, 2, 2, 1, 1, 1 是否是可图的。删除序列s 的首项5，对其后的5 项每项减1，得到：3, 2, 2, 1, 1, 2, 1, 1, 1，重新排序后为：3, 2, 2, 2, 1, 1, 1, 1, 1。继续删除序列的首项3，对其后的3 项每项减1，得到：1, 1, 1, 1, 1, 1, 1, 1。如此再陆续得到序列：1, 1, 1, 1, 1,1, 0；1, 1, 1, 1, 0, 0；1, 1, 0, 0, 0；0, 0, 0, 0。由此可判定该序列是可图的。
Havel-Hakimi 定理实际上给出了根据一个序列s 构造图（或判定s 不是可图的）的方法：把序列s 按照非增顺序排序以后，其顺序为d1, d2, …, dn；度数最大的顶点（设为v1），将它与度数次大的前d1 个顶点之间连边，然后这个顶点就可以不管了，即在序列中删除首项d1，并把后面的d1个度数减1；再把剩下的序列重新按非增顺序排序，按照上述过程连边；…；直到建出完整的图，或出现负度数等明显不合理的情况为止。
一般不合理的情形有两种：

(1) 某次对剩下序列排序后，最大的度数（设为d1）超过了剩下的顶点数；
(2) 对最大度数后面的d1 个度数各减1 后，出现了负数。

练习题：POJ 1659

一个无向图G 是二部图当且仅当G 中无奇数长度的回路

MST(最小生成树)

最小生成树是否唯一

prim判断（不正确）

prim过程中，在将某个顶点的时候，如果某个顶点的扩展方式不唯一，那么最小生成树不唯一。
利用这种思路判断最小生成树不唯一的方法为：
首先当前已经找到min = lowcost[v]，因此，待扩展的顶点是v，待扩展的边是(nearvex[v], v)。
接下来要判断在集合T 内是否还有其他顶点到v 的距离也等于lowcost[v]，根据以下四个条件来判定：

  1. nearvex[j] == -1：只考虑集合T 内的顶点；
  2. graph[v][j] < MAX：要排除min刚好等于∞的情况，这个条件实际上可以去掉；
  3. graph[v][j] == min：顶点j 到v 的距离刚好也等于min；
  4. nearvex[v] != j：而且j 不等于nearvex[v]。

如果以上四个条件同时成立，即可判定扩展顶点v 的方式不唯一，从而判定最小生成树不唯一。

说明
以上思路在判断出当前顶点扩展方式不唯一时能判定MST不唯一，但即使每个顶点的扩展方式均唯一也不能判定MST 唯一。以为prim在选第一个点的时候是随机的

正确思路

判定最小生成树是否唯一的一个正确思路为：

  1. 对图中每条边，扫描其他边，如果存在相同权值的边，则对该边作标记；
  2. 然后用Kruskal 算法（或Prim 算法）求MST；
  3. 求得MST 后，如果该MST中未包含作了标记的边，即可判定MST唯一；如果包含作了标记的边，则依次去掉这些边再求MST，如果求得的MST 权值和原MST 的权值相同，即可判定MST 不唯一。

（补充：求次小生成树应该也是可行的，但是没有写过）
例题：POJ 1679

单源最短路

Dijkstra

Bellman-Ford

SPFA

欧拉图

基本概念及定理

无向图：

1) 设G 是连通无向图，则称经过G 的每条边一次并且仅一次的路径为欧拉通路；
2) 如果欧拉通路是回路（起点和终点是同一个顶点），则称此回路为欧拉回路（Euler circuit）；
3) 具有欧拉回路的无向图G 称为欧拉图（Euler graph）。

有向图：

1) 设D 是有向图，D 的基图连通，则称经过D 的每条边一次并且仅一次的有向路径为有向欧拉通路；
2) 如果有向欧拉通路是有向回路，则称此有向回路为有向欧拉回路（directed Euler circuit）；
3) 具有有向欧拉回路的有向图D 称为有向欧拉图（directed Euler graph）。

定理及推论

定理 1

无向图G 存在欧拉通路的充要条件是：

G 为连通图，并且G 仅有两个奇度结点（度数为奇数的顶点）或者无奇度结点。

推论 1

1) 当G 是仅有两个奇度结点的连通图时，G 的欧拉通路必以此两个结点为端点。
2) 当G 是无奇度结点的连通图时，G 必有欧拉回路。
3) G 为欧拉图（存在欧拉回路）的充分必要条件是G 为无奇度结点的连通图。

定理 2

有向图D 存在欧拉通路的充要条件是：

D 为有向图，D 的基图连通，并且所有顶点的出度与入度都相等；或者除两个顶点外，其余顶点的出度入度都相等，而这两个顶点中一个顶点的出度与入度之差为1，另一个顶点的出度与入度之差为-1。

推论 2

1) 当 D 除出、入度之差为1，-1的两个顶点之外，其余顶点的出度与入度都相等时，D的有向欧拉通路必以出、入度之差为1 的顶点作为始点，以出、入度之差为-1 的顶点作为终点。
2) 当D 的所有顶点的出、入度都相等时，D 中存在有向欧拉回路。
3) 有向图D 为有向欧拉图的充分必要条件是D 的基图为连通图，并且所有顶点的出、入度都相等。

网络流

最大流

标记法求最大流

  1. /*
  2. ID: LinKArftc
  3. PROG: Demo.cpp
  4. LANG: C++
  5. */
  7. #include <map>
  8. #include <set>
  9. #include <cmath>
  10. #include <stack>
  11. #include <queue>
  12. #include <vector>
  13. #include <cstdio>
  14. #include <string>
  15. #include <utility>
  16. #include <cstdlib>
  17. #include <cstring>
  18. #include <iostream>
  19. #include <algorithm>
  20. using namespace std;
  21. #define eps 1e-8
  22. #define randin srand((unsigned int)time(NULL))
  23. #define input freopen("input.txt","r",stdin)
  24. #define debug(s) cout << "s = " << s << endl;
  25. #define outstars cout << "*************" << endl;
  26. const double PI = acos(-1.0);
  27. const int inf = 0x3f3f3f3f;
  28. const int INF = 0x7fffffff;
  29. typedef long long ll;
  31. const int maxn = 100;
  32. const int maxm = 10000;
  34. struct Arc {
  35.     int c, f; //容量，流量
  36. };
  37. Arc edge[maxn][maxn];
  38. int n, m;
  39. int flag[maxn]; //顶点状态：-1－未标号,0－已标号未检查,1－已标号已检查
  40. int prev[maxn]; //标号的第一个分量：指明标号从哪个顶点得到，以便找出可改进量
  41. int alpha[maxn]; //标号的第二个分量：可改进量α
  43. void ford() {
  44.     while (1) { //标号直至不存在可改进路
  45.         //标号前对顶点状态数组初始化
  46.         memset(flag, -1, sizeof(flag)); //将3 个数组各元素初始化为-1
  47.         memset(prev, -1, sizeof(prev));
  48.         memset(alpha, -1, sizeof(alpha));
  49.         flag[0] = 0;
  50.         prev[0] = 0;
  51.         alpha[0] = inf; //源点为已标号未检查顶点
  52.         queue <int> q;
  53.         q.push(0);
  54.         while (!q.empty() && flag[n-1]==-1) {
  55.             int u = q.front();
  56.             q.pop();
  57.             for (int v = 0; v < n; v ++) { //检查顶点v 的正向和反向"邻接"顶点
  58.                 if (flag[v] == -1) { //顶点i 未标号
  59.                     if (edge[u][v].c < inf && edge[u][v].f < edge[u][v].c) { //"正向"且未"满"
  60.                         flag[v] = 0;
  61.                         prev[v] = u; //给顶点i 标号(已标号未检查)
  62.                         alpha[v] = min(alpha[u], edge[u][v].c - edge[u][v].f);
  63.                         q.push(v);
  64.                     } else if (edge[v][u].c < inf && edge[v][u].f > 0) { //"反向"且有流量
  65.                         flag[v] = 0;
  66.                         prev[v] = -u; //给顶点i 标号(已标号未检查)
  67.                         alpha[v] = min(alpha[u], edge[v][u].f);
  68.                         q.push(v);
  69.                     }
  70.                 }
  71.             }
  72.             flag[u] = 1; //顶点v 已标号已检查
  73.         }
  74.         //当汇点没有获得标号，或者汇点的调整量为0，应该退出while 循环
  75.         if (flag[n-1] == -1 || alpha[n-1] == 0) break;
  76.         //当汇点有标号时,应该进行调整了
  77.         int k1 = n - 1, k2 = abs(prev[k1]);
  78.         int a = alpha[n-1]; //可改进量
  79.         while (1) {
  80.             if (edge[k2][k1].f < inf) //正向
  81.                 edge[k2][k1].f = edge[k2][k1].f + a;
  82.             else edge[k1][k2].f = edge[k1][k2].f - a; //反向
  83.             if (k2 == 0) break; //调整一直到源点v0
  84.             k1 = k2;
  85.             k2 = abs(prev[k2]);
  86.         }
  87.     }
  88.     //输出各条弧及其流量，以及求得的最大流量
  89.     int maxFlow = 0;
  90.     for (int i = 0; i < n; i ++) {
  91.         for (int j = 0; j < n; j ++) {
  92.             if (i == 0 && edge[i][j].f < inf)//求源点流出量，即最大流
  93.                 maxFlow += edge[i][j].f;
  94.             if (edge[i][j].f < inf) printf("%d->%d : %d\n", i, j, edge[i][j].f);
  95.         }
  96.     }
  97.     printf("maxFlow : %d\n", maxFlow);
  98. }
  99. int main() {
  100.     input;
  101.     int u, v, c, f;
  102.     scanf("%d%d", &n, &m);
  103.     memset(edge, 0x3f, sizeof(edge));
  104.     for (int i = 0; i < m; i ++) {
  105.         scanf("%d %d %d %d", &u, &v, &c, &f);
  106.         edge[u][v].c = c;
  107.         edge[u][v].f = f;
  108.     }
  109.     ford(); //标号法求网络最大流
  110.     return 0;
  111. }
  113. /*
  114. Sample Input
  115. 6 10
  116. 0 1 8 2
  117. 0 2 4 3
  118. 1 3 2 2
  119. 1 4 2 2
  120. 2 1 4 2
  121. 2 3 1 1
  122. 2 4 4 0
  123. 3 4 6 0
  124. 3 5 9 3
  125. 4 5 7 2
  127. Sample Output
  128. 0->1 : 4
  129. 0->2 : 4
  130. 1->3 : 2
  131. 1->4 : 2
  132. 2->1 : 0
  133. 2->3 : 1
  134. 2->4 : 3
  135. 3->4 : 0
  136. 3->5 : 3
  137. 4->5 : 5
  138. maxFlow : 8
  139. */
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注