图

图的应用极为广泛，已渗入到诸如物理、化学、电信工程、计算机科学，以及数学等其他分支中。在离散数学中，图论是专门研究图的性质的数学分支，而在数据结构中，则应用图论的知识讨论如何在计算机上实现图的操作，因此主要学习图的存储结构，以及若干图的操作的实现。

图的定义和基本术语

图的定义

图（Graph）$G$由两个集合$V$（Vertex）和$E$（Edge）组成，记为$G = (V,E)$，其中$V$是顶点的有穷非空集合，$E$是$V$中顶点偶对的有穷集合，这些顶点偶对称为边。$V(G)$和$E(G)$通常分别表示图$G$的顶点集合和边集合，$E(G)$可以表示为空集。若$E(G)$为空，则图$G$只有顶点而没有边。

对于图$G$，若边集$E(G)$为有向边的集合，则称该图为有向图；若边集$E(G)$为无向边的集合，则称该图为无向图。

$<x, y>$是有序的，有向图。$<x, y>$也称作一条弧，则$x$为弧尾，$y$为弧头。
$(x, y)$是无序的，偶对，无向图。无向图中称为边。

图的基本术语

子图：假设有两个图 $G = (v, E)$ 和 $G^{'}=(V^{'}, E^{'})$ ，如果 $V^{'} \subseteq V 且 E^{'} \subseteq E$，则称 $G^{'}$ 为 $G$ 的子图。
无向完全图和有向完全图：对于无向图，若具有 $n(n - 1)/2$ 条边，则称为无向完全图 (任意两个顶点之间一条边)。对于有向图，若具有 $n(n - 1)$ 条弧，则称为有向完全图(任意两个顶点之间都有两条边)。
稀疏图和稠密图：有很少条边或弧（如 $e < nlog_{2}n$ ）的图称为稀疏图，反之称为稠密图。
权和网：在实际应用中，每条边可以标上具有某种含义的数值，该数值称为该边上的权。这些权可以表示从一个顶点到另一个顶点的距离或耗费。这种带权的图通常称为网。
邻接点：对于无向图 $G$ ，如果图的边 $(v, v^{'}) \subseteq E$ ，则称顶点 $v$ 和 $v^{'}$ 互为邻接点，即 $v$ 和 $v^{'}$ 相邻接。边 $(v, v^{'})$ 依附于顶点 $v$ 和 $v^{'}$ ，或者说边 $(v, v^{'})$ 与顶点 $v$ 和 $v^{'}$ 相关联。
度、入度和出度：顶点 $v$ 的度是指和 $v$ 相关联的边的数目，记为 $TD(v)$ 。对于有向图，顶点 $v$ 的度分为入度和出度。入度是以顶点 $v$ 为头的弧的数目，记为 $ID(v)$ ；出度是以顶点 $v$ 为尾的弧的数目，记为 $OD(v)$ 。顶点 $v$ 的度为 $TD(v) = ID(v) + OD(v)$ 。一般地，如果顶点 $v_{i}$ 的度记为 $TD(v_{i})$ ，那么一个有 $n$ 个顶点 $e$ 条边的图，满足如下关系 $$ e = \frac{1}{2} \sum_{i = 1}^{n}TD(v_{i}) $$
路径和路径长度：在无向图 $G$ 中，从顶点 $v$ 到顶点 $v^{'}$ 的路径是一个顶点序列$(v = v_{i, 0}, v_{i, 1}, ... v_{i, m} = v^{'})$ ，其中 $(v_{i, j - 1}, v_{i, j}) \subseteq E, 1 \le j \le m$ 。如果 $G$ 是有向图，则路径也是有向的，顶点序列应满足 $<v_{i, j-1}, v_{i, j}> \subseteq E, 1 \le j \le m$ 。路径长度是一条路径上经过的边或弧的数目。
回路或环：第一个顶点和最后一个顶点相同的路径称为回路或环。
简单路径、简单回路或简单环：序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路，称为简单回路或简单环。
连通、连通图和连通量：在无向图 $G$ 中，如果从顶点 $v$ 到顶点 $v_{'}$ 有路径，则称 $v$ 和 $v_{'}$ 是连通的。如果对于图中任意两个顶点 $v_{i}、v_{j} \subseteq V$，$v_{i}$ 和 $v_{j}$ 都是连通的，则称 $G$ 是 连通图。所谓连通分量 ，指的是无向图中的极大连通子图。
- 极大连通子图：存在无向图$G$，$G^{'}$是$G$的连通子图。如果将$G$中任意不在$G^{'}$中的顶点加入$G^{'}$，$G^{'}$不再连通，则称$G^{'}$为极大连通子图。
强连通图和强连通分量：在有向图 $G$ 中，如果对于每一对 $v_{i}，v_{j} \subseteq V$ ， $v_{i} \ne v_{j}$ ，从 $v_{i}$ 到 $v_{j}$ 和从 $v_{j}$ 到 $v_{i}$ 都存在路径，则称 $G$ 是强连通图。有向图中的极大强连通子图称作有向图的强连通分量。
连通图的生成树：一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的 $n - 1$ 条边，这样的连通子图称为连通图的生成树（简单说就是包含无向图$G$所有顶点的极小连通子图）。
- 极小连通子图：存在无向图$G$，$G^{'}$是$G$的连通子图。如删除$G^{'}$中任意一条边，$G^{'}$不再连通，则称$G^{'}$为极小连通子图。
有向树和生成森林：有一个顶点的入度为0，其余顶点的入度均为1的有向图称为有向树。一个有向图的生成森林是由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。