目录
9.1 若干定义
一个图(graph)\(G=(V, E)\)由顶点(vertex)的集\(V\)和边(edge)/弧(arc)的集\(E\)组成。
每一条边就是一幅点对\((v, w)\)，其中\(v, w\in V\)。如果点对是有序的，那么图就是有向(directed)的——有向图(digraph)。
顶点\(v\)和\(w\)邻接(adjacent)当且仅当\((v, w)\in E\)。在一个具有边\((v, w)\)从而具有边\((w, v)\)的无向图(undigraph)中，\(w\)和\(v\)邻接且\(v\)也和\(w\)邻接。
有时候边还具有第三种成分，称作权(weight)或值(cost)。
图中的一条路径(path)是一个顶点序列\(w_1, w_2, w_3, …, w_N\)使得\((w_i, w_{i+1})\in E\)，\(1\leqslant i<N\)。这样一条路径的长(length)是该路径上的边数\(N-1\)。
如果图含有一条从一个顶点到它自身的边\((v, v)\)，那么路径\(v, v\)有时候也叫作一个环(loop)。（我们要讨论的图一般是无环的）
简单路径：其上的所有顶点都是互异的，但第一个顶点和最后一个顶点可能相同。
有向图中的圈(cycle)是满足\(w_1=w_N\)且长至少为1的一条路径；如果该路径是简单路径，那么这个圈就是简单圈。如果一个有向图没有圈，则称其为无圈的(acyclic)。一个有向无圈图有时也简称为DAG。（无向图中\((u, v)\)和\((v, u)\)是同一条边，圈无意义）
一个无向图中从每一个顶点到每个其他顶点都存在一条路径——连通的(connected)。
一个有向图中从每一个顶点到每个其他顶点都存在一条路径——强连通的(strongly connected)。
一个有向图不是强连通的，但其基础图(underlying graph)，即其弧上去掉方向所形成的图，是连通的——弱连通的(weakly connected)。
每一对顶点间都存在一条边——完全图(complete graph)。