图论的基本概念

一个图G是指一个有序三元组(V(G)，E(G)，)，其中V(G)是非空的顶点集，

GE(G) 是不与V(G)相交的边集，而是关联函数，它使G的每条边对应于G的无序G顶点对(不必相异)，若e是一条边，而u和v是使得 (e)=uv的顶点，则称e连接Gu和v；顶点U和v称为e的端点。

将己知图的顶点放在平面上，并绘制这些对应点和连通它们之间的边，这就是图的绘制，对于表示地图的应用，图绘制可能包含相当多的信息，因为顶点对应于平面中的点， 而且与它们之间的距离有关，我们称这类图为殴几米德图(Euclidean graph)。

G的一条途径(或通道)是指一个有限非空序列Wv0e1v1e2v2...e2vk，它的项交替为

顶点和边，使得对1≤i≤k，ei的端点vi1和vi。称w是从v0到vk的一条途径，或一条（v0，vk）途径顶点。v0和vk分别称为W的起点和终点，而v1，v2，....，vk1称为它的内部顶点。整数k称为w的长。若途径W的边e1，e2，…，ek互不相同，则W称为迹：这时W的长恰好是e（W）。又如果途径W顶点v1，v2，....，vk也互不相同，则称W为路。起点和终点相同的路是环。

如果在图中，从每个顶点到其他每个顶点之间都存在一条路径，则此图为连通图。无环连通图称为树，树的集合是森林。连通图的生成树是包括该图所有顶点的一个子图，是一棵单一树。图的生成森林是包括该图所有顶点的一个子图。是一个森林。

图的Hamilton性是一个非常重要的概念，它有着广泛的应用，尤其是在LRP的VRP问题中。如果图G存在一条长为|V(G)|的圈，则称图G是一个Hamilton图，或称该图具有Hamilton性。

到目前为止所定义的图都是无向图。在有向图中，边是单向的，定义每条边的顶点对看作是一个有序对，它指定了一个单向邻接，有向图中的边称为有向边，有时也称为弧t 有向边的第一个点称为是源或弧尾，边的最后一个点称为目标或弧首。出度是以一个顶点为弧尾的有向边的条数，入度是以一个顶点作为弧首的有向边的条数。