1.1 图的基本定义

在数学中，图由顶点（Vertex）以及连接顶点的边（Edge）构成。顶点表示研究的对象，边表示两个对象之间特定的关系。

图可以表示为顶点和边的集合，记为G=（V，E），其中V是顶点集合，E是边集合。同时，我们设图G的顶点数为N，边数为M（如无特殊说明，本书中的图均如此表示）。一条连接顶点vi，vj∈V的边记为（vi，vj）或者eij。如图1-1所示，V={v1，v2，v3，v4，v5}，E={（v1，v2），（v1，v3），（v2，v4），（v2，v3），（v3，v4），（v4，v5）}。

图1-1 图G的定义