7.1 图的定义

图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G（V，E），其中，G 表示一个图，V 是图 G 中顶点的集合，E 是图 G 中边的集合。
特点：

无向图：若顶点 Vi 到 Vj 之间的边没有方向，则这条边称为无向边（Edge），表示为（Vi, Vj）。如果图任意顶点的边都为无向边，则称该图为无向图（Undirected graphs）。
下图表示为 G1 = (V1, {E1})，V1 = { A, B, C, D }; E1 = { (A, B), (B, C), (C, D), (D, A), (A, C) }**
有向图：若顶点 Vi 到 Vj 之间的边有方向，则这条边称为有向边，也称为弧（Arc）。表示为，Vi 称为弧尾（Tail），Vj 称为弧头（Head）。如果图任意顶点之间的边都为有向边，则称为有向图（Directed graphs）。
下图表示为 G2 = (V2, {E2})，V2 = { A, B, C, D }; E1 = { , , , }
无向完全图：在无向图中，任意顶点之间都存在边。
n个顶点边的数量公式为。
有向完全图：在有向图中，任意顶点之间都存在互为相反的两条弧。
n个顶点边的数量公式为 n * (n-1)。
稀疏图与稠密图：根据边的数量多少来定义，为模糊的概念。
网（Network）：带权值的图称为网。
子图：有两个图 G = (V, {E}) 和 G’ = (V’, {E’})。如果且，则称 G’ 为 G 的子图（Subgraph）。
下图右侧为左侧的子图。

7.1.2 图的顶点与边之间的关系
对于无向图：
顶点 V 的度记作；
对于 n 个顶点的无向图来说，边的数量为各个顶点之间度数和的一半，多出的一半为重复两次计数导致。数学公式为