图 原

基本概念

图是有限集V和E的有序对，即G=(V,E)。其中V的元素称为顶点（也称为节点或点），E的元素称为边（也称为弧或线）。每一条边连接两个不同的顶点，而且用元组(i,j)表示，其中i和j是边所连接的两个顶点。

带方向的边叫有向边（directed edge）,而不带方向的边叫无向边（undirected edge）。对无向边来说，（i,j）和(j,i)是一样的；而对有向边来说，它们是不同的，前者方向是从i到j，后者方向是从j到i。

当且仅当(i,j)是图的边，称顶点i和j是邻接的（adjacent）.边(i,j)关联(incident)于顶点i和j。

对有向图的邻接和关联的概念更精确的定义有时非常有用。有向图(i,j)是关联至（incident to）顶点j而关联于（incident from）顶点i。

如果图的所有边都是无向边，那么该图叫做无向图。

如果图的所有边都是有向边，那么该图叫做有向图。

一个图不能有重复的边。在无向图的任意两个顶点之间，最多只能有一条边。在有向图的任意两个顶点i和j之间，从顶点i到顶点j最多有一条边。从顶点j到i也最多有一条边。

一个图不可能包含自连边，即(i,i)形式的边。自连边也叫做环。

在图的一些应用中，我们可能要为每条边赋予一个表示成本的值。我们称之为权。这时的图称为加权有向图和加权无向图。

一个网络经常指一个加权有向图或加权无向图。实际上，所有的图都可以看做是特殊的网络————一个有向（无向）图可以看做是一个所有边上的权都相同的无向（有向）网络。

有向图、无向图和网络常常用于电子网络的分析、化合物（特别是碳氢化合物）的分子结构研究、空中航线和通信网络的描述、项目策划、遗传研究、统计、社会科学等很多种领域。

一条路径，如果除第一个和最后一个顶点之外，其余所有顶点均不同，那么该路径称为一条简单路径。如路径5,2,1是简单路径，而2,5,2,1不是。

图或有向图的每一条边都可以有长度。一条路径的长度时该路径的所有边长度之和。从路口i到路口j的最短路径是在相应的网络（即加权有向图）中从顶点i到顶点j的最短路径。

设G=(V,E)是一个无向图。G是连通的，当且仅当G的每一对顶点之间都有一条路径。

如果H的顶点和边的集合分别是G的顶点和边的集合的子集，那么称图H是图G的子图。一条始点和终点相同的简单路径称为环路（cycle）。

没有环路的连通无向图是一棵树。一个G的子图，如果包含G的所有顶点，且是一棵树，则称为G的生成树。

一个具有n顶点的连通无向图至少有n-1条边。

当连接网络的每条链路的建造成本都相同时，任意一棵生成树的的建设成本都可以将网络建设成本减至最小，并保证网络的连通。如果不同的链路有不同的建设成本，那么需要在一棵成本最小的生成树（生成树的成本是所有链路的成本之和）上建造链路。下图是一个图，和它的两棵生成树。

应用场景

假设你正在策划一次国际会议。所有发言人都只会说英语，而每一个与会人员所懂得的语言是L1，L2,……，Ln中的一种。翻译小组合一在有英语和其他语言之间互译。现在是任务是如何使翻译小组的人数最少。

我们可以准确的将这个任务表示为一个图的问题。在这个图中，有两组顶点：一组与翻译人员对应（i），一组与语言对应（j），i和j之间存在一条边，当且仅当翻译人员i能够将语言Lj互译。翻译人员i覆盖语言Li，当且仅当有一条边连接翻译人员i和语言Li。我们需要找到能够覆盖所有语言顶点的最小翻译人员顶点集。 如下图，对这个问题进行描述：

特性

在一个无向图中，与一个顶点i相关联的边数称为该顶点的度。

• 在无向图中，顶点的度之和是边数的2倍。

在无向图中，每一条边都与两个顶点相关联，因此顶点的度之和是边数的2倍。

• 一个顶点的度在0~n-1之间，因此度的和在n~n(n-1)之间，则边数在0~n(n-1)/2之间。
• 一个具有n个顶点和n(n-1)/2条边的无向图是一个完全图(complete graph)。

下面就是n=1,2,3,4时的完全无向图

• 设G是一个有向图。顶点i入度是指关联至该顶点的边数。顶点i的出度是指关联于该点的边数。
• 一个具有n个顶点的完全有向图恰好包含n(n-1)条有向边。

下图是n=1,2,3,4时的完全有向图。

在无向图中，入度和出度可以看做是度的同义词。

• 一个有向图是强连通的，当且仅当对于每一对不同顶点i和j，从i到j和从j到i都有一条有向路径。
• 对于每一个n(n>=1)，都存在一个恰有n-1条边的无向连通图。
• 对于每一个n(n>=2)，都存在一个恰有n条边的强连通有向图。
• 每一个具有n（n>=2）个顶点的强连通有向图，至少包含n条边