[ADN.cn][library]summary 图论总结 2013-12-21
(connected)；反之，称非连通(unconnected)。
强连通(strongly connected)：在有向图G中，两个顶点间，至少存在一条路径，称两个顶点强连通。
弱连通(weakly connected)：在有向图G中，两个顶点间，若不考虑G中边的方向的图才连通的，称原有向图为弱连通。
连通图(connected graph)：图G中任二顶点都连通。
连通分量或连通分支(connected branch, component)：非连通无向图的极大连通子图(maximally connected sub-graph)。具体说，若图G的顶点集V(G)可划分为若干非空子集使得两顶点属于同一子集当且仅当它们在G中连通，则称每个子图G[Vi]为图GV1,V2,?,V?，
的一个连通分支（i?1,2,?,?）。图G的连通分支是G的一个极大连通子图。图G连通当且仅当?＝1。
强连通分量(strongly connected branch)：非强连通图有向图的极大强连通子图。
割(cut)：
点割集(vertex cut)：点集V'?V，若G删除了V'后不连通，但删除了V'的任意真子集后G仍然连通。则称V'点割集。若某一结点就构成就了点割集，则称此结点割点(cut vertex)。点数最少的点割集称为点连通度k(G)。
边割集(edge cut set)：边集E'?E，若G删除了E'后不连通，但删除了E'的任意真子集后G仍然连通。则称E'点割集。若某一边就构成就了边割集，则称此结点割边(cut edge)或桥(bridge)。边数最少的边割集称为边连通度k’(G)。
记号[S,S?]表示一端在S中另一端在S?中的所有边的集合。 块(block)是指没有割点的极大连通子图。
1.1.5. 图论中特殊的集合 Sets in graph
点覆盖(集)(vertex covering (set))：V'?V，满足对于?e?E，有?v?V'，v关联e。即一个点集，使得所有边至少有一个端点在集合里。或者说是“点” 覆盖了所有“边”。极小点覆盖(minimal vertex covering)：本身为点覆盖，其真子集都不是。最小点覆盖(minimum vertex covering)：点最少的点覆盖。点覆盖数(vertex covering number)：最小点覆盖的点数，记为?V(G) 一般说覆盖集就是指点覆盖集。
边覆盖(集)(edge covering (set))：E'?E，满足对于?v?V，有?e?E'，e关联v。即一个边集，使得所有点都与集合里的边邻接。或者说是“边” 覆盖了所有“点”。 极小边覆盖(minimal edge covering)：本身是边覆盖，其真子集都不是。最小边覆盖(minimum edge covering)：边最少的边覆盖。边覆盖数(edge covering number)：最小边覆盖的边数，记为?E(G)。
独立集(independent set)：V'?V，满足对于?u,v?V'，有(u,v)?E。即一个点集，集合中任两个结点不相邻，则称V'为独立集。或者说是导出的子图是零图（没有边）的点集。极大独立集(maximal independent set)：本身为独立集，再加入任何点都不是。最大独立集(maximum independent set)：点最多的独立集。独立数(independent number)：最大独立集的点
6/33
[ADN.cn][library]summary 图论总结 2013-12-21
数，记为?V(G)。
团(clique)：V'?V，满足对于?u,v?V'，有(u,v)?E。即一个点集，集合中任两个结点相邻。或者说是导出的子图是完全图的点集。极大团(maximal clique)：本身为团，再加入任何点都不是。最大团(maximum clique)：点最多的团。团数(clique number)：最大团的点数，记为?(G)。
边独立集(edge independent set)：E'?E，满足对于?e,f?E'，有e,f不邻接。即一个边集，满足边集中的任两边不邻接。极大边独立集(maximal edge independent set)：本身为边独立集，再加入任何边都不是。最大边独立集(maximum edge independent set)：边最多的边独立集。边独立数(edge independent number)：最大边独立集的边数，记为?E(G)。
边独立集又称匹配(matching)，相应的有极大匹配(maximal matching)，最大匹配(maximum matching)，匹配数(matching number)。
支配集(dominating set)：V'?V，满足对于?u?V?V'，有?v?V'，(u,v)?E。即一个点集，使得所有其他点至少有一个相邻点在集合里。或者说是一部分的“点”支配了所有“点”。 极小支配集(minimal dominating set)：本身为支配集，其真子集都不是。最小支配集(minimum dominating set)：点最少的支配集。支配数(dominating number)：最小支配集的点数，记为?V(G)。
边支配集(edge dominating set)：E'?E，满足对于?e?E?E'，有?f?E'，e,f邻接。即一个边集，使得所有边至少有一条邻接边在集合里。或者说是一部分的“边”支配了所有“边”。极小边支配集(minimal edge dominating set)：本身是边支配集，其真子集都不是。最小边支配集(minimum edge dominating set)：边最少的边支配集。边支配数(edge dominating number)：最小边支配集的边数，记为?E(G)。
定理：若G中无孤立点，D为支配集，则D=V(G)-D也是一个支配集。 定理：一个独立集是极大独立集，当且仅当它是支配集。
关系：
定理：无向图G无孤立点，V1是极小支配集，则存在V2是极小支配集，且V1?V2??。 定理：无向图G无孤立点，V'是极大独立集，则V'是极小支配集。逆命题不成立。
?V(G)??V(G)。
定理：连通图中，V'是点覆盖，则V'是支配集。极小点覆盖不一定是极小支配集。支配集不一定是点覆盖。
定理：无向图G无孤立点，V'是(极，最小)点覆盖，充要于V?V'是(极，最大)独立集。
?V(G)??V(G)?|V|。
?(G)??V(G)。定理：无向图G，最大)团，充要于V'是G的(极，最大)独立集。 V'是G的(极，
7/33
[ADN.cn][library]summary 图论总结 2013-12-21
由上述定理知，?V(G)，?V(G)，?(G)三者互相确定，但都是NPC的。但是二分图中，点覆盖数是匹配数。
M是匹配，W是边覆盖，N是点覆盖，Y是点独立集。 定理：无向图G无孤立点，|M|<=|N|,|Y|<=|W|
定理：无向图G无孤立点，?E(G)??E(G)?|V|。先取一个最大匹配M，1条边盖两个点；剩下的一个未盖点要用一条边来覆盖，边覆盖数=|M| +(|V|-2|M|)= |V|-|M|。
定理：无向图G无孤立点，?E(G)=?V(G)，?V(G)=?E(G)。 定理：无向图G无孤立点，?(G)=?V(G)。
求匹配数是P的，所以边覆盖和匹配都是易求的。
最小路径覆盖(path covering)：是“路径” 覆盖“点”，即用尽量少的不相交简单路径覆盖有向无环图G的所有顶点，即每个顶点严格属于一条路径。路径的长度可能为0(单个点)。
最小路径覆盖数＝G的点数－最小路径覆盖中的边数。应该使得最小路径覆盖中的边数尽量多，但是又不能让两条边在同一个顶点相交。拆点：将每一个顶点i拆成两个顶点Xi和Yi。然后根据原图中边的信息，从X部往Y部引边。所有边的方向都是由X部到Y部。因此，所转化出的二分图的最大匹配数则是原图G中最小路径覆盖上的边数。因此由最小路径覆盖数＝原图G的顶点数－二分图的最大匹配数便可以得解。
1.1.6. 匹配 Matching
匹配(matching)是一个边集，满足边集中的边两两不邻接。匹配又称边独立集(edge independent set)。
在匹配中的点称为匹配点(matched vertex)或饱和点；反之，称为未匹配点(unmatched vertex)或未饱和点。
交错轨(alternating path)是图的一条简单路径，满足任意相邻的两条边，一条在匹配内，一条不在匹配内。 增广轨(augmenting path)：是一个始点与终点都为未匹配点的交错轨。
最大匹配(maximum matching)是具有最多边的匹配。 匹配数(matching number)是最大匹配的大小。
完美匹配(perfect matching)是匹配了所有点的匹配。
完备匹配(complete matching)是匹配了二分图较小部份的所有点的匹配。 增广轨定理：一个匹配是最大匹配当且仅当没有增广轨。
综上，在二分图中，最小覆盖数=最大匹配数。边覆盖数=最大独立数=|V|-最大匹配数。
1.1.7. 树 Tree
G=(V, E)为一个图，则下列命题等价：(1)G是一棵树；(2)G连通，且|E|=|V|-1；(3)G无圈，
8/33
[ADN.cn][library]summary 图论总结 2013-12-21
且|E|=|V|-1；(4)G的任何两个顶点之间存在唯一的一条路；(5)G连通，且将G的任何一条弧删去之后，该图成为非连通图；(6)G无圈，且在G的任何两个不相邻顶点之间加入一条弧之后，该图正好含有一个圈。
Cayley公式：在n阶完全图Kn中，不同生成树的个数为nn?2。
1.1.8. 组合优化 Combinatorial optimization
从若干可能的安排或方案中寻求某种意义下的最优安排或方案，数学上把这种问题称为(最)优化(optimization)问题。
所谓组合(最)优化(combinatorial optimization)又称离散优化(discrete optimization)，它是通过数学方法去寻找离散事件的最优编排、分组、次序或筛选等. 这类问题可用数学模型描述为：
minf(x)s..tg(x)?0,x?D
其中D表示有限个点组成的集合(定义域)，f为目标函数,F?{x|x?D,g(x)?0}为可行域。
网络优化(network optimization)就是研究与(赋权)图有关的组合优化问题。
常见的P类网络优化问题：最小生成树，最短路，最大流，最小费用最大流，最大匹配，中国邮路问题。
常见的NP类网络优化问题：旅行商问题。
参考文献：
[1]Dictionary of Algorithms and Data Structures NIST，http://www.nist.gov/dads/ [2]Wikipedia，http://en.wikipedia.org/wiki/Graph_theory [3]谢金星，清华大学数学科学系<<网络优化>>讲义 http://faculty.math.tsinghua.edu.cn/~jxie/courses/netopt
1.2. 图的表示 Expressions of graph
下面介绍几种表示图的数据结构。并统一用下图做例子：
9/33
[ADN.cn][library]summary 图论总结 2013-12-21
2
1 1 4 2 3 3 4
5 6 8 7 5
1.2.1. 邻接矩阵 Adjacency matrix
用二元数组A(u,v)，来表示图。这种表示法一般用于稠密图。当图不是简单图，邻接矩阵法不能用。
在无权图中，若边(u,v)存在，A(u,v)=1；否则A(u,v)=0。
?0,(u,v)?EA?(au,v)n?n?{0,1}n?n,au,v??
?1,(u,v)?E无权图的例子：
?0?0??0??0??01100?0010??1000?
?0101?0110??在有权图中, 若边(u,v)存在,则A(u,v)为它的权值；否则人为的规定A(u,v)=∞或-∞。∞是一个足够大的数。
A?(au,v)n?n,au,v?w(u,v),(u,v)?E?? ?,(u,v)?E?无向图中，邻接矩阵是按矩阵副对角线对称的。
1.2.2. 关联矩阵 Incidence matrix
用二元数组B(u,k)，来表示无权有向图。一般不用这种表示法。
若边k与点u关联，若k是u的出边，则B(u,k)=1；若k是u的入边B(u,k)=-1；否则
10/33