2.1　基本概念和符號

一個圖G是包含點集V（G）和邊集E（G）的有序對，其中每條邊是兩個頂點的一個集合。一條邊的頂點稱為它的端點，用uv表示一條具有端點u和v的邊。一條邊的端點稱為與這條邊關聯，反之亦然。與同一條邊關聯的兩個點稱為相鄰的，與同一個頂點關聯的兩條邊也稱為相鄰的。端點重合為一點的邊稱為環，有相同端點對的邊稱為重邊。如果一個圖既沒有自環也沒有重邊，就稱這個圖為簡單圖，否則，稱為重圖。

一個圖如果它的頂點集和邊集都有限，則稱為有限圖。沒有頂點的圖稱為零圖。不含邊的圖稱為空圖。只有一個頂點的圖稱為平凡圖，其他所有的圖都稱為非平凡圖。

一條路是頂點被安排在一個線性序列里使得兩個點是相鄰的，當且僅當它們在這個序列里是連續的一個簡單圖。同樣，一個圈是頂點被安排在一個圈序列里使得兩個點是相鄰的，當且僅當它們在這個序列里是連續的一個具有相同數目頂點和邊的圖。一條路或一個圈的長度是它們所包含邊的數目。對一個圈，按照所含邊的數目是奇數還是偶數，稱這個圈是奇圈還是偶圈。圖2-2描述了一條長為3的路和一個長為5的圈。

每對頂點之間均有一條邊連接的簡單圖稱為完全圖。簡單圖G=（V，E）的一個團是指V中的一個子集S，使得G[S]是完全圖。G的團數是G中所有團的最大頂點數。若G=（V，E）中，可以把頂點集合V分割為兩個互補的子集S，T（S∪T=V，S∩T=?），使得每條邊都有一個端點在S中，另一個端點在T中，則稱G為二部圖。這樣一種分類（S，T）稱為圖G的一個二分類。完全二部圖是具有二分類（S，T）的簡單二部圖，其中S中的每個頂點都與T中每個頂點相連。星是滿足|S|=1或|T|=1的完全二部圖。利用圈的概念，可以給出二部圖的一個特征:一個圖是二部圖當且僅當它不包含奇圈。圖2-3展示了一個完全圖、一個完全二部圖和一個星。

稱圖H是圖G的子圖（記為H?G），如果V（H）?V（G），E（H）?E（G），并且對于H邊的頂點安排與G是相同的。當H?G，但H≠G時，則記為H?G，并且H稱為G的真子圖，G的生成子圖是指滿足V（H）=V（G）的子圖H。

在G=（V，E）中，假設V'是V的一個非空子集。以V'為頂點集，以兩端點均在V'中的邊的全體為邊集所組成的子圖，稱為G的由V'導出的子圖，記為G[V']，G[V']稱為G的導出子圖。從G中刪除V'中的頂點以及與這些頂點相關聯的邊所得到的子圖，記為G-V'。若V'={v}，則把G-{v}簡記為G-v。假設E'是E的一個非空子集，以E'為邊集，以E'中邊的端點全體為頂點集所組成的子圖，稱為G的由E'導出的子圖，記為G[E']，G[E']稱為G的邊導出子圖。從G中刪除E'中的邊所得到的子圖，記為G-E'。類似地，在G中添加E'中的所有的邊得到的圖，記為G+E'。若E'={e}，則用G-e和G+e來代替G-{e}和G+{e}。圖2-4中畫出了這些不同類型的子圖。

若圖中的每條邊都是有方向的，則稱該圖為有向圖。有向圖中的邊是由兩個頂點組成的有序對，有序對通常用尖括號表示，如<v_i，v_j>表示一條有向邊，其中v_i是邊的始點，v_j是邊的終點。<v_i，v_j>和<v_j，v_i>代表兩條不同的有向邊。圖2-5表示一個有向圖D。

給定圖G，對G的每條邊都賦一個實數，這個實數稱為這條邊的權。并稱這樣的圖G為賦權圖。圖2-6展示了5個頂點的一個賦權圖。

賦權圖在實際問題中非常有用。根據不同的實際情況，權值的含義可以各不相同。例如，可用權值代表兩地之間的實際距離或行車時間，也可用權值代表某工序所需的加工時間等。賦權圖在圖的理論及其應用方面都有著重要的地位。賦權圖不僅指出各個點之間的鄰接關系，而且同時也表示出各點之間的數量關系。所以，賦權圖被廣泛應用于解決工程技術及科學生產管理等領域的最優化問題。最小支撐樹問題就是賦權圖上的最優化問題之一。