2.1.1 圖的定義與類型
用
表示非空集
的所有
-元子集構成的集族，
。基于此，給出圖的定義：設
是一個非空集，
，則把有序對
稱為一個圖，記作
，并將稱為的頂點集，
稱為的邊集；中的元素稱為的頂點，中的元素稱為的邊。對于給定圖，有時也用
和
分別表示的頂點集和邊集。設
，通常用
來代替
，并稱頂點
與頂點
相鄰，稱頂點（或）與邊（相互）關聯。設
，
或
表示圖中所有與頂點相鄰的頂點構成的集合，稱為的鄰域集。如果圖中的兩條邊
、
與同一個頂點關聯，則稱它們相鄰。設
，如果
中的任意兩個頂點均不相鄰，則稱是的一個獨立集。類似地，設
，若
中的任意兩條邊均不相鄰，則稱是的匹配，或稱是的一個邊獨立集。
注2.1 由于集合中元素不允許重復，因此與中均無重復的元素，且
為無序2元子集構成的集族。這就意味著：①中沒有重復的邊；②中的每條邊
中的兩個關聯頂點不同；③
。滿足上述3點的圖又稱簡單無向圖。
若與中元素的數量均有限，則稱為有限圖，否則稱為無限圖。本書提到的圖皆為有限圖。通常，稱
為的階，
為的規模，并把具有
個頂點、
條邊的圖稱為(n,m)-圖。
圖可在平面上用一個幾何圖形來表示：頂點用一個小圓點（稱為點）表示，若頂點與相鄰，則在與之間連接一條線。這種將畫在平面上的方法稱為的圖解。用圖解表示圖，能更直觀、清晰地展示圖的結構，有助于理解圖的性質，這也是圖論的魅力所在。
設
是一個階簡單圖，
。若
，則稱為
階完全圖，記作
；圖2.1（a）（b）所示為
的兩種不同的圖解。完全圖的特征是：每對頂點均相鄰。與完全圖恰恰相反的是：若中每對頂點均不相鄰，即
，則稱為階空圖，又稱階零圖，記作
，在不考慮頂點數時，通常稱為空圖或零圖。
圖若滿足
且
，則稱為
長路或
路，記作
，圖2.1（c）所示為
的一種圖解；若，
，則稱為-圈，記作
。圖2.1（d）所示為
的一種圖解。
（a） （b） （c） （d）
圖2.1 
、
和
的圖解
（a）
的第一種圖解 （b）的第二種圖解 （c）
的一種圖解 （d）
的一種圖解
注2.2 對于一個圖的圖解，我們不關心頂點和邊的幾何特征，即頂點的大小、形狀、空心還是實心，以及邊的長短、粗細、曲直等。
例2.1 設
是簡單圖，其中
，
，則此圖為著名的彼得松圖（Peterson Graph），如圖2.2（a）所示。圖2.2（b）（c）所示為該圖的兩種圖解。
若對中每個頂點標名稱，則稱為標定圖，否則稱為非標定圖。圖2.2（a）所示為標定圖，圖2.2（b）（c）所示均為非標定圖。
（a） （b） （c）
圖2.2 彼得松圖及圖解
（a）彼得松圖 （b）彼得松圖的圖解之一 （c）彼得松圖的圖解之二
在簡單圖的定義中，邊集中的元素是互不相同的，即邊互不相同。如果去掉這個限制，即允許有相同元素，會導致圖G中一對頂點之間可能有
（i＞1）條邊，稱為
-重邊。具有重邊的圖稱為重圖。更詳細的論述如下。
將
擴展成一個允許含重復元素[2]的新集族，記作
。有序對
稱為一個重圖，記作
，其中
；重復出現的元素稱為重邊。
[2]
中的元素在
中出現任意次。
例2.2 設
，其中
，
，
，
，
，
，
，則是重圖。圖2.3（a）所示為它的一種圖解。
重圖的基礎圖是一個基于
的簡單圖，記作
：頂點集
，且
中任意一對頂點相鄰當且僅當該對頂點在中至少有一條邊相連。重圖的基礎圖
，其中
，
，如圖2.3（b）所示；圖2.3（c）所示為它的一個圖解。
（a） （b） （c）
圖 2.3 重圖
的一種圖解，基礎圖
及它的邊賦權圖
（a）重圖
的一種圖解 （b）的基礎圖
（c）的邊賦權圖
在簡單圖與重圖的定義中，任意邊
所關聯的兩個頂點不同，即
。如果去掉這個限制，即一條邊所關聯的兩個頂點相同，則這種邊稱為圖的自環，且含有自環的圖稱為偽圖。確切地講，在簡單圖或重圖中，可將
（或）擴展為允許含
中一個或多個元素[3]的新集族（記作
），這時有序對
稱為一個偽圖，記作
。其中，
，元素
稱為自環，
。
[3]
中的元素在
中出現任意次。
例2.3 圖
是一個偽圖，其中
，
。在
中，
與
均為自環，如圖2.4所示。
圖2.4 一個含自環的圖
注2.3 在重圖中，邊集
必含重邊；在偽圖中，邊集EO必含自環。
在重圖中，如果把關聯同一對頂點的邊的數量標于該邊在基礎圖中對應的邊上，則相當于給邊賦權值。例如，對于圖2.3（a）所示的重圖
，按邊的重數定義各邊的賦權w分別為
、
、
、
，則邊賦權圖如圖2.3（c）所示。更一般地，邊賦權圖G可表示為一個三元有序組
，其中(V, E)是一個簡單圖。令
，則
為賦權向量，
（
）為邊
的權值。按此定義，在圖2.3（c）所示的邊賦權圖中，
。
邊賦權圖的應用場景較多，如交通網絡和生物神經網絡。在交通網絡中，頂點表示城市，邊表示兩個城市之間的公路、鐵路、飛行航線或航海線等，邊的權值則表示兩個城市之間的距離（包括公路距離、鐵路距離、飛行距離和航海距離等）。在生物神經網絡中，頂點表示生物體（如人）的神經元，邊表示兩個神經元之間的突觸，邊的權值表示對應突觸的厚度。人腦約有
個神經元，以及
～
個突觸，但關于突觸厚度的研究相對較少，這方面的深入研究對腦科學的研究至關重要。
與邊賦權圖相似，下面給出點賦權圖的定義：一個三元有序組
稱為一個點賦權圖，其中為簡單圖，
為
的頂點賦權向量，
（
）是頂點
的權值。圖2.5所示為一個點賦權圖，其中
，
。注意，該例中，中每個頂點的權值屬于
，且每條邊的兩端權值不同。因此，這種點賦權可視為對該圖的頂點著色，其中權值代表顏色，顏色集為。
點賦權圖的應用場景也較多，如用于解決交通信號燈設計問題、調度問題和航線規劃問題等[2]。
圖2.5 一個點賦權圖
對一個簡單圖的頂點與邊同時賦權的圖，稱為混合型賦權圖（通常將它簡稱為賦權圖），它具有更豐富的應用場景。混合型賦權圖是一個四元組
，其中為簡單圖，
分別為定義在、上的賦權向量，與邊賦權圖中的
、點賦權圖中的
相同，這里不贅述。
綜上所述，無向圖可分為簡單圖、重圖、偽圖、賦權圖。賦權圖可進一步分為邊賦權圖、點賦權圖及混合型賦權圖。
注2.4 若無特別聲明，本書提及的圖皆為有限簡單無向圖。
在圖的定義中，把中的無序改成有序，便得到有向圖的概念。
設
，
表示中所有有序對之集，并把從到
的有序對記作
，簡記為
（
）。如
，
。基于，可類似地定義有向圖如下。
設是非空集，
，則有序對
為一個簡單有向圖，記作
，并稱為的頂點集、
為的弧集，即中的元素為的頂點，中的元素為的弧。設
且
，則
為從連接到的弧，為的尾，為的頭。在有些情況下，可稱關聯和、鄰接于、控制等。
形如和
的一對弧為對稱弧。設是一個有向圖，它的逆記作
，定義為
，
。有向圖的基礎圖記作
，是指用無向圖的邊來代替中的每一條弧而得到的圖。圖2.6所示為有向圖、它的逆，以及它的基礎圖。
（a） （b） （c）
圖2.6 有向圖D、它的逆
，以及它的基礎圖
（a）
（b）
（c）
完全對稱圖是每對頂點之間恰有一對對稱弧連接的有向圖，圖2.7（a）所示為一個5階完全對稱有向圖。競賽圖是一類具有較多應用場景的有向圖，它的每對頂點之間恰有一條弧。換言之，競賽圖就是基礎圖為完全圖的有向圖。圖2.7（b）所示為一個5階競賽圖。
上述有向圖均為簡單有向圖。與無向圖的分類相似，有向圖也可分為4類：簡單有向圖、多重有向圖、偽有向圖及賦權有向圖。其中，賦權有向圖可進一步分為弧賦權有向圖、點賦權有向圖和混合型賦權有向圖。
本書主要考慮無向圖，故本小節僅簡要介紹有向圖的基本概念與分類，更系統的有向圖理論可查閱文獻[2]。無向圖的詳細定義、記號及基本理論可查閱文獻[3-4]。
（a） （b）
圖2.7 5階完全對稱有向圖及5階競賽圖