前言
-
七桥问题
-
四色问题
-
汉密尔顿回路
-
欧拉及拓扑
基本定义
顶点（vertex）
图中带数字的圆圈就是顶点，表示某个事物或对象。由于图的术语没有标准化，因此，称顶点为点、节点、结点、端点等都是可以的。
边（edge）
图中顶点之间的黑色的线条就是边，表示事物与事物之间的关系。需要注意的是边表示的顶点之间的逻辑关系，粗细长短都无所谓的。包括上面的顶点也一样，表示逻辑事物或对象，画的时候大小形状都无所谓。
图
图是由一个顶点的集合 \(V\)(vetex) 和一个顶点间关系（边）的集合 \(E\)(edge) 组成的数据结构，记作 \(G=(V,E)\)。
\(V\)：顶点的优先非空集合。
\(E\)：顶点间关系的有限集合（边集）。
有向/无向图(Directed Graph/Undirected Graph)
最基本的图通常被定义为“无向图”，与之对应的则被称为“有向图”。两者唯一的区别在于，有向图中的边是有方向性的，无向图中图的边没有方向，可以双向。其中有向图是从属关系，无向图是并列关系。
完全图、稠密图和稀疏图
假设图中有 \(n\) 个顶点，\(e\) 条边，则：
- 含有 \(e=n(n-1)/2\) 条边的无向图称作为完全图。
- 含有 \(e=n(n-1)\) 条弧的有向图称作为有向完全图。
- 若边较少(\(e<n log n\))
同构（Isomorphism）
从图（graph）的角度出发，这 \(2\) 个图是一样的，即它们是同构的。前面提到顶点和边指的是事物和事物的逻辑关系，不管顶点的位置在哪，边的粗细长短如何，只要不改变顶点代表的事物本身，不改变顶点之间的逻辑关系，那么就代表这些图拥有相同的信息，是同一个图。
权重（weight）
边的权重（或者称为权值、开销、长度等）也是一个非常核心的概念，即每条边都有与之对应的值。有时候为了应对特殊情况，边的权重可以是零或者负数，也别忘了“图”是用来记录关联的东西，并不是真正的地图。
顶点的度、入度和出度（Degree）
-
无向图
顶点 \(v\) 的度是指与顶点 \(v\) 相连的边的数目 \(D(v)\)。
此图中 \(D(2)=3\)。 -
有向图
入度：以该顶点为终点的边的数目和。此图中 \(ID(3)=2\)。
出度：以该顶点为起点的边的数目和。此图中 \(OD(2)=1\)。
有向图的度：等于该顶点的入度与出度之和。
此图中，\(D(5)=ID(5)+OD(5)=1+1=2\)。
度数为奇数的顶点叫做奇点，度数为偶数的点叫做偶点。
结论：
-
每个图中，节点度数（有向图就直接求入度+出度）之和等于边数的两倍。
-
每个图中，度数为奇数的节点个数是偶数个。
-
在任何有向图中，所有节点入度之和等于所有节点出度之和。
路径/最短路径（path/shortest path）
在图上任取两顶点，分别作为起点和终点，我们可以规划许多条由起点到终点的路线。不会来来回回绕圈子、不会重复经过同一个点和同一条边的路线，就是一条“路径”。两点之间存在路径，则称这两个顶点是连通（connected）的。
路径也有权重，路径经过的每一条边，沿路加权重，权重总和就是路径的权重（通常只加边的权重，而不考虑顶点的权重）。其中路径权重最小的为最短路径。
连通图/连通分量（connected graph/connected component）
如果在图G中，任意2个顶点之间都存在路径，那么称G为连通图（注意是任意2顶点）。如左图，每个城市之间都有路径，因此是连通图。而右图中，顶点8和顶点2之间就不存在路径，因此下图不是一个连通图，当然该图中还有很多顶点之间不存在路径。
剩下的假期补。咕咕。