1.1 圖的基本定義

在數(shù)學(xué)中，圖由頂點（Vertex）以及連接頂點的邊（Edge）構(gòu)成。頂點表示研究的對象，邊表示兩個對象之間特定的關(guān)系。

圖可以表示為頂點和邊的集合，記為G=（V，E），其中V是頂點集合，E是邊集合。同時，我們設(shè)圖G的頂點數(shù)為N，邊數(shù)為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的定義