图

• 图的定义

图(Graph)是一个顶点(vertex)集合加上一个连接不同顶点对的边(edge)集合。

• 连通图

如果在图中，从每个顶点到其他每个顶点之间都存在一条路径，则此图为连通图(connected graph)。非连通图包含一些连通分量，它们是最大连通子图(maximal connected subgraph)。
无环连通图称为树，树的集合称为森林。连通图的生成树(spanning tree)是包括该图所有顶点的一个子图，是一颗单一树。图的生成森林是包括该图所有顶点的一个子图，是一个森林。

• 简单图

一个图如果同时满足下面2个条件：

1. 没有两条边，它们所关联的两个点都相同（在有向图中，没有两条边的起点终点都分别相同）；
2. 每条边所关联的是两个不同的顶点
   则称为简单图（Simple graph）。

V个顶点的任何无环连通图均有V-1条边（简单图）
V个顶点的图至多有V(V - 1)/2条边。

• 二分图(Bipartite graph)

二分图(Bipartite graph)指图中的顶点可以分为两个集合，所有边连通一个集合中的顶点与另一个集合中的顶点。