摘要：
1，图论起源
2，图的定义
3，图的基本术语
4，图的分类
5，图的基本概念
6，相关定理
7，常见考点与总结
1，图论起源
关于图论最著名的就是瑞士数学家欧拉(E. Euler)在1736年提出的“哥尼斯堡的七座桥”问题。当时东普鲁士的柯尼斯堡有条河，河上有两个小岛，小岛与河的两岸有七条桥连接。问怎样在所有桥都只能走一遍的前提下，最后又回到出发点。
后来欧拉把它转化为一笔画问题，只有在奇点数是 0 或者 2 的时候才有可能走完，并且只有奇点数是 0 的时候才有可能回到起始点，而柯尼斯堡七桥问题中有4个奇点，很明显是不行的。
一个图要能一笔画完成必须符合两个条件：
1，图是连通的；
2，图中的奇点个数为 0 或 2 。
1，奇点数为 0 的连通图，一定可以一笔画成。画时把任一顶点为起始点，最后一定能回到起始点。
2，只有两个奇点的连通图，也可以一笔画成。画时必须以一个奇点为起点，另一个奇点为终点。
3，其他情况的图都不能一笔画出。(奇点数除以 2 可算出此图需几笔画成)
2，图的定义
图（Graph）是一种非线性的数据结构，上面讲的哥尼斯堡的七座桥问题就可以把它抽象成一个图。除此之外，比如交通运输网，地铁网络，朋友关系等等也可以抽象成图结构。
图 G 是由两个集合 V(G) 和 E(G) 组成的，记为 G=(V,E) ，其中 V(G) 是顶点（Vertexes）的非空有限集，称为点集， E(G) 是边（Edges）的有限集合，称为边集。E(G)边集可以为空，但V(G)点集不能为空。图可以是无向的，也可以是有向的，还可以是带权的或不带权的。
3，图的基本术语
顶点(Vertex)：图中的基本单位，也称为节点或结点。
边(Edge)：连接两个顶点的线，可以是无向的或有向的，也可能带有权重。
顶点v的出度(out-degree)：在有向图中，以 v 为起点有向边数目。
顶点v的入度(indegree)：在有向图中，以 v 为终点有向边数目。
顶点v的度(Degree)：与 v 相连的边的数目，如果是有向图，顶点 v 的度等于其入度和出度之和。
路径(Path)：路径就是从某个顶点到另一个顶点所要经过的顶点序列。
路径长度：路径上边的数目称为路径长度。
最短路径：从起点到终点经过边的权重和最小的路径。
环(Cycle)：第一个顶点和最后一个顶点相同的路径称为环或回路。
边的权(Weight)：在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权。
网(Network)：边上带有权值的图称为带权图，也称网。
图的密度：图中边的数量与顶点数量的比值。
邻接(Adjacent)：如果两个顶点之间有边相连，则称这两个顶点是邻接的。
阶(Order)：图G中顶点集 V 的大小称作图G的阶，比如一个包含 5 个顶点的图可以称为 5 阶图。
自环(Loop)：若一条边的两个顶点为同一顶点，则此边称作自环。
弧：有向图中的有向边也称为弧。
弧头：有向边的终点称为弧头（带箭头的一边）。
弧尾：有向边的起始点称为弧尾（不带箭头的一边）。
桥(Bridge)：若去掉一条边，便会使得整个图不连通，该边称为桥，也可以理解为当且仅当删除这条边后，图的连通分量数量会增加。
4，图的分类
无向图(undirected graph)
如果一个图结构中，每条边都是无方向的，那么这种图称为无向图。无向图类似于情侣关系，比如在情侣中 A 喜欢 B ，那么 B 也喜欢 A 。由于无向图中的边没有方向，所以在表示边的时候对两个顶点的顺序没有要求，用小括号 (v,w) 表示边。
如下图所示 ，顶点 V2 和顶点 V4 之间的边，可以表示为 (V2，V4) ，也可以表示为(V4，V2) 。
对应的顶点集合与边集合如下：
V（G）= {V1，V2，V3，V4，V5}
E（G）= {(V1,V2)，(V1，V3)，(V2，V4)，(V2，V5)，(V3，V4)，(V4，V5)}有向图(oriented graph)
如果一个图结构中，所有的边都有方向，那么这种图称为有向图。有向图类似于单相思，比如 A 喜欢 B ，但 B 不一定喜欢 A 。在有向图中，与一个顶点相关联的边有出边和入边之分。
由于有向图的边是有方向的，所以在表示边的时候对两个顶点的顺序就有要求。用尖括号 表示边，也称作一条弧，其中 w 为弧头， u 为弧尾。如下图所示， 表示从顶点 V1 到顶点 V3 ，而 表示从顶点 V3 到顶点 V1 。
对应的顶点集合与边集合如下：
V（G）= {V1，V2，V3，V4，V5}
E（G）= {
，
，
，
，
，
，
，
}
无向完全图(Undirected Complete Graph)
在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。也可以说恰有n(n-1)/2条边的无向简单图称无向完全图，其中 n 是图中顶点的数量。
有向完全图(Directed Complete Graph)
在有向图中如果任意两个顶点之间都存在两条方向相反的边，则称该图为有向完全图。也可以说恰有n(n-1)条边的有向简单图称为有向完全图，其中 n 是图中顶点的数量。
简单图(Simple graph)
在无向图中如果任意两顶点之间最多只有一条边，在有向图中如果两顶点之间每个方向最多只有一条边，且不存在顶点到自身的边，这样的图称为简单图。也可以理解为既不含平行边也不含自环的图为简单图，如下图所示，都不属于简单图。
有向无环图(DAG,Directed acyclic graph)
如果一个有向图无法从某个顶点出发经过若干条边回到该点，则这个图是一个有向无环图，如下图所示。
连通图(connected graph)
在无向图中对于任一对顶点 vi 和 vj 有路径相连，则称此图是连通图，如下图所示。连通图是对无向图图来说的，若是有向图则分为强连通图和若连通图。
如果一个无向图是连通的，那么边E的数量大于等于顶点的数量减 1 ，即|E|>=|V|-1，而反之不成立。
没有回路（环）的无向图是连通图当且仅当它是一颗树，即|E|=|V|-1。
强连通图(Strongly Connected Graph)
在有向图中，若对于图中任意两个不同的顶点 vi 和 vj，都存在从 vi 到 vj 以及从 vj 到 vi 的路径，则称此图是强连通图。
如果一个有向图是强连通图，当且仅当此图中至少存在一个回路，它至少包含图中每个顶点一次。这个可以证明一下，如果一个回路包含所有顶点，那么这些顶点之间肯定都是可达的，所以该图是强连通图。
如果一个图是强连通图，那么这个图中任意两个顶点都是可达的，所以可以做一个回路经过所有点。所以一个强连通图至少有一个回路包含所有的顶点。
有 n 个顶点的强连通图最多有n(n-1)条边，最少有 n 条边。如果有n(n-1)条边，就是一个有向完全图，如果有 n 条边，就像上面图中所有顶点首尾相连构成一个环。
弱连通图
将有向图G的所有的有向边替换为无向边，就会得到一个无向图，如果该无向图是连通图，那么这个有向图G就是若连通图。
单向连通图(unilateral connected digraph)
如果图G=(V，E)是有向图，对于任意顶点 vi ，vj ，如果至少存在从 vi 到 vj 或者从 vj 到 vi 的一条路径，则称图G为单向连通图(unilateral connected digraph)。
也就是在单向连通图中存在从 vi 到 vj 的路径，但未必存在从 vj 到 vi 的路径。如下图所示：v1 可以到达 v2 ，但 v2 到达不了 v1 。
如果图G=(V，E)是单向连通图，则当且仅当图G中存在一条路径，它包含所有顶点。注意这里说的是路径，不是回路，如果是回路，图G就是强连通图，强连通图也是单向连通图。
通过强连通图、连通图、单向连通图三者之间的关系我们可以发现，强连通图必然是单向连通图，单向连通图必然是弱连通图，但反之未必。
我们可以看到无论是强连通图还是弱连通图还是单向连通图都是对于有向图来说的。
子图(subgraph)
对于两个图 G=(V,E) 和 G'=(V',E') ，如果 V' 是 V 的子集并且 E' 也是 E 的子集，我们称 G' 是 G 的子图。也可以理解为顶点集和边集分别是另一个图的节点集的子集和边集的子集的图，如下图所示。
加权图
对图 G 的每一条边 e 来说，都对应于一个值 v ，我们把这个 v 称为 e 的权，把这样的图 G 称为加权图。这个 v 可以表示两点之间的距离，花费时间等。
如果每条边没有对应的值，我们称它为非加权图，对于非加权图，两点之间如果有边我们可以用 1 表示，如果没边可以用 0 表示。
基图
在有向图中，把有向边全变成无向边，得到一个无向图，这个无向图称为原图的基图。
补图(Complementary Graph)
在一个 n 阶无向简单图中，使它成为无向完全图所添加的边构成的图称为原题的补图，也可以说补图就是完全图的边集减去现有图的边集。显然，对于任意顶点 u 和 v ，若 u 和 v 在原图中不连接，则 u 和 v 在补图中连接，若 u 和 v 在原图中连接，则 u 和 v 在补图中不连接。
补图的性质：
如果原图不连通，则它的补图必连通。
无边图的补图是完全图，反之亦然。
二分图(Bipartite Graph)
如果G=(V,E)是一个无向图，他的顶点集 V 可分割为两个互不相交的子集，并且图G中每条边的两个顶点都分别属于这两个互不相交的子集，则称图G为一个二分图。
如下图所示，两个虚线框中的顶点是两个子集，图G所有边的两个顶点都分别属于不同的子集。
任何无回路的无向图均为二分图。
如果一个无向图G有回路，则他是二分图的充要条件是其所有回路的路径长度必须都是偶数。也可以理解为如果一个无向图中没有路径长度为奇数的环，那么这个无向图就是一个二分图。
完全二分图(complete bipartite graph)
如果一个无向图G是一个二分图，对于两个不同的子集 X ,Y ，如果 X 中的任一顶点与 Y 中所有顶点都有唯一的一条边相连，则称G为完全二分图或完全偶图。
竞赛图
在无向完全图中为每条边任意分配方向而得到一个有向图，那么这个有向图就是竞赛图。也就是说在竞赛图中任何两个点都有一条有向边相连。也可以说每对顶点之间都有一条边相连的有向图称为竞赛图。
正则图(regular graph)
每个顶点的度均相同的无向简单图称为正则图，即从每个顶点出发，所连接到的点的数目都相同。
混合图(mixed graph)
在一个图中，既有无方向，也有有方向的图称为混合图。
稀疏图(sparse graph)
边的数量 e 远小于|V|²，(如e
稠密图(dense graph)
条的数量 e 接近|V|² 的图，称为稠密图。
赋权图(Weighted graph)
每条边都有一个非负实数对应的图称为赋权图，这个实数称为这条边的权。
平凡图(Trivial graph)
只有一个顶点的图称为平凡图。
空图(empty graph)
顶点集为空集的图为空图。
零图(null graph)
只有顶点没有边的图称为零图。
多重图(multigraph)
含有平行边的图称为多重图，或者是顶点通过同一条边和自己相连的图称为多重图。多重图的定义和简单图是相对的。
5，图的基本概念
简单路径：在路径序列中，顶点不重复的路径称为简单路径，如下图所示，1->2->3 就是一条简单路径，1->2->3->1 是一个简单回路。
简单回路：除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。
距离：从顶点 u 出发到顶点 v 的最短路径若存在，则此路径的长度称为从 u 到 v 的距离。若从 u 到 v 路径不存在，则该距离为无穷大（∞）。
匹配(Matching)：是指图中边的一个子集，这个子集中的任何两条边都没有公共顶点，这些边被称为匹配边，匹配边的端点被称为匹配点。如下图所示，红色的边就是一个匹配。
最大匹配(Maximum Matching)：在图G的所有匹配中，所含匹配边数最多的匹配称为最大匹配。如下图所示，红边就是最大匹配，如果再添加任何一条边都会出现公共顶点。
完美匹配(Perfect Matching)：图中的每个顶点都被匹配中的边所覆盖，如下图所示，所有顶点都被匹配边锁覆盖。
最大权匹配(Maximum Weight Matching)：在带权图中，使得边权之和最大的匹配。
连通分量(Connected Component)：在无向图中子图必须连通，且包含尽可能多的顶点和边，以至于它再加上一个点或者边之后就不再是连通的。它强调的是“极大性”，即无法再通过添加顶点或边来扩展该子图，同时保持其连通性。
任何连通图的连通分量只有一个，即其自身。对于非连通的无向图，它会有多个连通分量，如下面的图中有 3 个连通分量。
连通分量中的任意两个顶点都是连通的，即它们之间存在一条路径。不同的连通分量之间没有边相连，即它们之间没有直接的路径。
强连通分量(Strongly Connected Component,SCC)：一个有向图的一个强连通分量是它的最大子图，该子图中任意两个顶点都是强连通的，并且该子图不能再加入其他的顶点或边使其仍然保持强连通。并且从子图内的任一顶点出发，都可以通过一系列边到达该子图中的任何其他顶点，并且可以回到原点。
在强连通分量中，任意两个顶点之间都存在双向可达的路径。
强连通图只有一个强连通分量，即是其自身。非强连通的有向图有多个强连通分量。
树(Tree)：树是一种特殊的图，它是一个无环的连通图。
生成树(Spanning Tree)：连通图的生成树是包含图中全部顶点但边数最少的连通子图，且其边的数量等于顶点数减 1 。一个图的生成树可能有多个，带权图的生成树中，总权值最小的称为最小生成树。
求最小生成树常见的有克鲁斯克尔算法和普林姆算法，一个是通过选择边一个是通过选择点实现的，后面我们都会介绍。
生成森林(Forest)：在非连通图中，多个连通分量各自对应的生成树构成了生成森林。生成森林是非连通图的一个子集，因为它对应的是非连通图中的多个连通分量。
生成森林中的边不形成任何环。如果存在环，则它不是一棵树，因为树是无环的。生成森林中的每一棵树都是独立的，一棵树中的顶点和边不与另一棵树中的顶点和边重叠。
在生成森林中，边的总数等于顶点的总数减去树的数量。这个很好理解，因为一个连通图的生成树中边的数量是顶点数量减 1 。在非连通图中会有 x 棵生成树，所以边的总数就等于顶点的总算减去树的数量。
欧拉回路(Eulerian Circuit)：欧拉回路是指通过图中每条边恰好一次并且最后回到起始顶点的简单回路。也就是说它经过图中的每一条边恰好一次，并且起点和终点是同一个顶点，形成一个闭合的环。因此，如果一个图是连通的并且每个顶点的度都是偶数，那么这个图就存在欧拉回路。
欧拉路径(Eulerian Path)：欧拉路径是指通过图中每条边恰好一次（但不必回到起始顶点）的路径。
欧拉图(Eulerian Graph)：如果一个图包含欧拉回路，那么这个图被称为欧拉图。
半欧拉图(Semi-Eulerian Graph)：半欧拉图是指存在欧拉路径但不存在欧拉回路的图。
6，相关定理
定理1：无向图中所有顶点的度之和等于边数的 2 倍（因为一条边连接两个点，增加一条边相当于增加两个度）。
定理2：有向图中所有顶点的入度之和等于所有顶点的出度之和（有向图中任意一条边，一边是出度一边是入度，所以出度的数量和入度的数量是相等的）。
定理3：任意一个无向图一定有偶数个奇点（度为奇数的顶点）。
定理4：无论是有向图还是无向图，所有顶点的度之和都是偶数，并且是边数的两倍。即顶点数 n ，边数 E 和度之间对应关系：E=(d[v1]+d[v2]+…+d[vn])/2。
定理5：（欧拉公式）设图G有 e 条边， v 个顶点和 r 个面的平面图，则 v-e+r=2。
7，常见考点与总结