图论总述

图的存储

图通常用G=（V,E）表示。V为顶点（vertex）集合，E为边(Edge)的集合。

图的物理存储，有两种方法。

1.邻接矩阵，就是二维数组，较直观，但不能存储重边。

2.邻接表，它是一种顺序与链式兼有的存储。

图的遍历

 二部图

二部图：存在一种划分方法，将图G的顶点划分为两个集合A和B，使得图中任意一条边的两个邻接顶点分属不同的顶点集。

匹配：二部图中没有公共顶点的边集。边数最多的匹配叫最大匹配。若图中每个顶点都被匹配边邻接，叫完美匹配。

未盖点：不与任何匹配边邻接的顶点。

增广路：从未盖点出发，经非匹配边、匹配边、非匹配边......交替进行，最终以未盖点结尾，此路径叫增广路。在增广路中，把原匹配边与非匹配边对换，则得到的新匹配比原来的多一条边。

匈牙利算法：不断寻找增广路，最终得到最大匹配。

二部图最小覆盖：选择尽量少的点，使得图中每条边至少有一个端点被选中。可以证明，最小覆盖数=最大匹配数。

 二部图的独立集：该集合中任意两点不相邻接。独立集中顶点个数=总顶点数-最大匹配中边的数目。

一个图G，若其顶点集V可划分为不相交的3个集合V1，V2，V3，使得不同集合的任意两点都邻接，但同一集合内的任意两点都不相邻，则称G为完全三部图。

网络流-概念

容量网络（capacity network）：设G(V, A)是一个有向网络，在V 中指定了一个顶点，称为源点（记为Vs），以及另一个顶点，称为汇点（记为Vt）；对于每一条弧<u, v>∈A，对应有一个权值c(u, v)＞0，称为弧的容量（capacity）。通常把这样的有向网络G 称为容量网络。从源点到汇点的最大可行流叫最大流。

可行流(Valid Flow):可行流f(u,v)表示顶点u到顶点v的流量。

前向弧：原图中的弧。

反向弧：对前向弧取反。

增广路（augmenting path）：

设f 是一个容量网络G 中的一个可行流，P 是从Vs 到Vt 的一条路径，若P 满足下列条件：

1) 在P 的所有前向弧<u, v>上，0 ≤ f(u, v) < c(u, v)，即每一条弧都是非饱和弧；

2) 在P 的所有后向弧<u, v>上，0 < f(u, v) ≤ c(u, v)，即每一条弧是非零流弧。

则称P 为关于可行流f 的一条增广路，简称为增广路。

增广-沿着增广路改进可行流的操作称为增广（augmenting）。

 增广路P上的所有弧<u, v>上的流量按下述规则变化：（始终满足可行流的2 个条件）

a) 在前向弧<u, v>上，f(u, v) = f(u, v) +x；

b) 在后向弧<u, v>上，f(u, v) = f(u, v) -x。

x应该等于每条前向弧上的c(u, v)–f(u, v)与每条后向弧上的f(u, v)的最小值。即：

x=min{ min{c(u,v)-f(u,v)}, min{f(u,v)}}。

 

最小割最大流

割——对于图G=(V,E),对顶点集合V进行划分，分为S和T。其中源点s∈S，汇点t∈T，且T=V-S。则称（S，T）为一个割。割的容量定义为capacity（S,T）=∑capacity（u，v），其中u∈S，v∈T。

对于任意s-t流f，和任意s-t割（S,T）,都有|f|<=capacity(S,T),因为流f必定跨过割中的若干条边。

当最后一条增广路被找到，下一次BFS找不到新的增广路时，把已标号的点看作集合S（对于其中的任意一点v都有a[v]>0），V-S看作T，此时的割就是最小割。

 

最小费用最大流

 

最小生成树

一个图的连通分量是该图的极大连通子图；而一个连通图的生成树是极小连通子图。若给边赋上权值，最小生成树就是权值和最小的生成树，算法有Prime与Kruskal。原图为G=（V,E）；生成树G1=（V1，E1）。

Prime：

1.初始化，V1、E1都为空，任选一点v加入V1。

2.求出具有最小权值的边（u,v），u属于V1，v属于V-V1。将v加入V1并将此边加入E1。

3.不断重复步骤2 ，直至V1=V。

复杂度为O（n*n）。

Kruskal：

1.将边按照从小到大的次序排序。置V1=V。

2.顺序遍历每个边edge[i]，若加入此边G1有环，则舍弃，否则加入E1。

复杂度为O（边数）。

最短路径

原图为G=（V,E），求s到任意顶点的最短路径。辅助数组dist[i]表示当前从源点s到顶点i的最短路径,辅助数组visited[ ]表示集合A。

1.初始化，置dist[i]=graph[s][i]，A中只有s点。

2.找到具有最小值的dist[x],x属于V-A。x加入A，更新所有的dist[ y ],y属于V-A。更新步骤为 if(dist[x]+graph[x][y]<dist[y]) {   dist [ y ]=dist[x]+graph[ x ] [ y ]  }

3.不断重复步骤2 ，直至V=A。

拓扑排序

对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一条弧(u,v)，顶点u在顶点v之前。
基本思想见下。
1.统计所有顶点的入度。顶点x的入度即为弧的终点为指向顶点x的弧的条数。
2.寻找入度为0的顶点x，将其放入线性序列，并将该点从图中删除。
3.不断重复第二步，直至所有顶点输出。若顶点未完全输出却找不到入度为0的顶点，说明此图存在环，排序失败。