## 圖的定義 圖 (Graph) 是由若干給定的頂點及連接兩頂點的邊所構成的圖形，這種圖形通常用來描述某些事物之間的某種特定關系。 頂點用于代表事物，連接兩頂點的邊則用于表示兩個事物間具有這種關系。 圖論 (Graph theory) 是數學的一個分支，圖是圖論的主要研究對象。 表達式：G=(V, E) V：頂點（數據元素）的有窮非空集合。 E：邊的有窮集合。 Graph = (Vertex, Edge) ## 基本術語 **無向圖**：頂點之間相連的線我們稱為邊，每條邊都是無方向的。 **有向圖**：頂點之間相連的線我們稱為弧，每條弧都是有方向的。 **完全圖**：任意兩點都有一條邊相連。（右向完全圖和無向完全圖） **稀疏圖**：有很少邊或弧的圖。 **稠密圖**：有較多邊或弧的圖。 **網**：邊/弧帶權值的圖。 **鄰接**：有邊/弧相連的兩個頂點之間的關系。 **頂點的度**：與該頂點相關聯的邊的數目，有入度和出度。 **路徑**：連續的邊/弧構成的頂點序列。 **路徑長度**：路徑上邊或弧的數目/權值之和。 **回路（環）**：第一個頂點和最后一個頂點相同的路徑。 **權與網**：圖中邊或弧所具有的相關數稱為權。表明從一個頂點到另一個頂點的距離或耗費。帶權的圖稱為網。 **子圖**：設有兩個圖G=(V, {E})、G1=(V1, {E1})，若V1?V，E1?E，則稱G1是G的子圖。 **生成樹**：包含無向圖G所有頂點的極小連通子圖。 **生成森林**：對非連通圖，由各個連通分量的生成樹的集合。