2.1　基本概念和符号

一个图G是包含点集V（G）和边集E（G）的有序对，其中每条边是两个顶点的一个集合。一条边的顶点称为它的端点，用uv表示一条具有端点u和v的边。一条边的端点称为与这条边关联，反之亦然。与同一条边关联的两个点称为相邻的，与同一个顶点关联的两条边也称为相邻的。端点重合为一点的边称为环，有相同端点对的边称为重边。如果一个图既没有自环也没有重边，就称这个图为简单图，否则，称为重图。

一个图如果它的顶点集和边集都有限，则称为有限图。没有顶点的图称为零图。不含边的图称为空图。只有一个顶点的图称为平凡图，其他所有的图都称为非平凡图。

一条路是顶点被安排在一个线性序列里使得两个点是相邻的，当且仅当它们在这个序列里是连续的一个简单图。同样，一个圈是顶点被安排在一个圈序列里使得两个点是相邻的，当且仅当它们在这个序列里是连续的一个具有相同数目顶点和边的图。一条路或一个圈的长度是它们所包含边的数目。对一个圈，按照所含边的数目是奇数还是偶数，称这个圈是奇圈还是偶圈。图2-2描述了一条长为3的路和一个长为5的圈。

图2-2　一条长为3的路和一个长为5的圈

每对顶点之间均有一条边连接的简单图称为完全图。简单图G=（V，E）的一个团是指V中的一个子集S，使得G[S]是完全图。G的团数是G中所有团的最大顶点数。若G=（V，E）中，可以把顶点集合V分割为两个互补的子集S，T（S∪T=V，S∩T=⌀），使得每条边都有一个端点在S中，另一个端点在T中，则称G为二部图。这样一种分类（S，T）称为图G的一个二分类。完全二部图是具有二分类（S，T）的简单二部图，其中S中的每个顶点都与T中每个顶点相连。星是满足|S|=1或|T|=1的完全二部图。利用圈的概念，可以给出二部图的一个特征:一个图是二部图当且仅当它不包含奇圈。图2-3展示了一个完全图、一个完全二部图和一个星。

图2-3　三种特殊图

称图H是图G的子图（记为H⊆G），如果V（H）⊆V（G），E（H）⊆E（G），并且对于H边的顶点安排与G是相同的。当H⊆G，但H≠G时，则记为H⊂G，并且H称为G的真子图，G的生成子图是指满足V（H）=V（G）的子图H。

在G=（V，E）中，假设V'是V的一个非空子集。以V'为顶点集，以两端点均在V'中的边的全体为边集所组成的子图，称为G的由V'导出的子图，记为G[V']，G[V']称为G的导出子图。从G中删除V'中的顶点以及与这些顶点相关联的边所得到的子图，记为G-V'。若V'={v}，则把G-{v}简记为G-v。假设E'是E的一个非空子集，以E'为边集，以E'中边的端点全体为顶点集所组成的子图，称为G的由E'导出的子图，记为G[E']，G[E']称为G的边导出子图。从G中删除E'中的边所得到的子图，记为G-E'。类似地，在G中添加E'中的所有的边得到的图，记为G+E'。若E'={e}，则用G-e和G+e来代替G-{e}和G+{e}。图2-4中画出了这些不同类型的子图。

图2-4　图G的几种不同类型的子图

若图中的每条边都是有方向的，则称该图为有向图。有向图中的边是由两个顶点组成的有序对，有序对通常用尖括号表示，如<v_i，v_j>表示一条有向边，其中v_i是边的始点，v_j是边的终点。<v_i，v_j>和<v_j，v_i>代表两条不同的有向边。图2-5表示一个有向图D。

图2-5　有向图D

给定图G，对G的每条边都赋一个实数，这个实数称为这条边的权。并称这样的图G为赋权图。图2-6展示了5个顶点的一个赋权图。

图2-6　赋权图

赋权图在实际问题中非常有用。根据不同的实际情况，权值的含义可以各不相同。例如，可用权值代表两地之间的实际距离或行车时间，也可用权值代表某工序所需的加工时间等。赋权图在图的理论及其应用方面都有着重要的地位。赋权图不仅指出各个点之间的邻接关系，而且同时也表示出各点之间的数量关系。所以，赋权图被广泛应用于解决工程技术及科学生产管理等领域的最优化问题。最小支撑树问题就是赋权图上的最优化问题之一。