图基本概念

图是什么？先用通俗易懂的语言去理解，然后引入严谨的定义。

根据维基百科上描述：在数学上，一个图是表示物件（对象）与物件之间关系的方法，是图论的基本研究对象。一个图看起来是由一些小圆点（称为顶点或结点）和连接这些圆点的直线或曲线（称为边）组成的。

由上述描叙可知图是由点的集合(vertex set)和边的集合(edge set)组成的。

首先研究边：

在数学里，两个点才能确定一条直线。

比如有两个点A，B，可以从任意一点出发，得到一条线段。如果规定了方向将会得到AB或BA，这样的情况称之为有向边,否则则称为无向边。

在图中，如果边的集合是有向的称为有向图，否则称为无向图。

此时A和B是相邻的，同在一个图中，称为邻接点。A是B的邻接点，B也是A的邻接点，这样A、B互为邻接点。

有时候为了表示AB之间的关系，比如AB边的长度，这样叫着权值。

带有权值的图称为网。

下面研究点：

往往一个点可能是连接好几条边，我们把边数称为度。

对于有向图来说边是有方向的，所以又分为出度和入度。顾名思义，出度是指以该点为起点，而入度则为终点。

有时候存在一种现象起点和终点是同一个点，称为环。

两点之间如果连通，存在的轨迹称为路径。

路径上边的数目，称为路径长度。

如果路径中不出现重复的点，称为简单路径。

在无向图中，如果任意两个顶点都能连通，称为连通图。

在有向图中，从点A到点B连通，B到A也连通，称为强连通图。

图G1的所有顶点是图G的顶点，G1的所有的边是G的边，那么G1是G的子图。

生成树，是指含有连通图的全部顶点的一个极小连通子图。

定义如下：

其中， V是顶点的有穷非空集合， E是V中顶点偶对的有穷集，

这些顶点偶对称为边。通常V(G)和E(G)分别称为图的顶点集合和边集合。

注意：E(G)可以为空集。

图的数据结构的形式化定义

G = ( V , E )

其中 V = { x | x∈dataObject }

E ={VR}

VR={<x,y>| p(x,y) ∩( x , y ∈V ) }

VR是两顶点间的关系的集合，即边的集合。

参考资料：