圖論相關概念
本頁面概述了圖論中的一些概念，這些概念並不全是在 OI 中常見的，對於 OIer 來説，只需掌握本頁面中的基礎部分即可，如果在學習中碰到了不懂的概念，可以再來查閲。
Warning
圖論相關定義在不同教材中往往會有所不同，遇到的時候需根據上下文加以判斷。
圖
圖 (graph) 是一個二元組 \(G=(V(G), E(G))\)。其中 \(V(G)\) 是非空集，稱為 點集 (vertex set)，對於 \(V\) 中的每個元素，我們稱其為 頂點 (vertex) 或 節點 (node)，簡稱 點；\(E(G)\) 為 \(V(G)\) 各結點之間邊的集合，稱為 邊集 (edge set)。
常用 \(G=(V,E)\) 表示圖。
當 \(V,E\) 都是有限集合時，稱 \(G\) 為 有限圖。
當 \(V\) 或 \(E\) 是無限集合時，稱 \(G\) 為 無限圖。
圖有多種，包括 無向圖 (undirected graph)，有向圖 (directed graph)，混合圖 (mixed graph) 等。
若 \(G\) 為無向圖，則 \(E\) 中的每個元素為一個無序二元組 \((u, v)\)，稱作 無向邊 (undirected edge)，簡稱 邊 (edge)，其中 \(u, v \in V\)。設 \(e = (u, v)\)，則 \(u\) 和 \(v\) 稱為 \(e\) 的 端點 (endpoint)。
若 \(G\) 為有向圖，則 \(E\) 中的每一個元素為一個有序二元組 \((u, v)\)，有時也寫作 \(u \to v\)，稱作 有向邊 (directed edge) 或 弧 (arc)，在不引起混淆的情況下也可以稱作 邊 (edge)。設 \(e = u \to v\)，則此時 \(u\) 稱為 \(e\) 的 起點 (tail)，\(v\) 稱為 \(e\) 的 終點 (head)，起點和終點也稱為 \(e\) 的 端點 (endpoint)。並稱 \(u\) 是 \(v\) 的直接前驅，\(v\) 是 \(u\) 的直接後繼。
為什麼起點是 tail，終點是 head？
邊通常用箭頭表示，而箭頭是從「尾」指向「頭」的。
若 \(G\) 為混合圖，則 \(E\) 中既有 有向邊，又有 無向邊。
若 \(G\) 的每條邊 \(e_k=(u_k,v_k)\) 都被賦予一個數作為該邊的 權，則稱 \(G\) 為 賦權圖。如果這些權都是正實數，就稱 \(G\) 為 正權圖。
圖 \(G\) 的點數 \(\left| V(G) \right|\) 也被稱作圖 \(G\) 的 階 (order)。
形象地説，圖是由若干點以及連接點與點的邊構成的。
相鄰
在無向圖 \(G = (V, E)\) 中，若點 \(v\) 是邊 \(e\) 的一個端點，則稱 \(v\) 和 \(e\) 是 關聯的 (incident) 或 相鄰的 (adjacent)。對於兩頂點 \(u\) 和 \(v\)，若存在邊 \((u, v)\)，則稱 \(u\) 和 \(v\) 是 相鄰的 (adjacent)。
一個頂點 \(v \in V\) 的 鄰域 (neighborhood) 是所有與之相鄰的頂點所構成的集合，記作 \(N(v)\)。
一個點集 \(S\) 的鄰域是所有與 \(S\) 中至少一個點相鄰的點所構成的集合，記作 \(N(S)\)，即：
簡單圖
自環 (loop)：對 \(E\) 中的邊 \(e = (u, v)\)，若 \(u = v\)，則 \(e\) 被稱作一個自環。
重邊 (multiple edge)：若 \(E\) 中存在兩個完全相同的元素（邊）\(e_1, e_2\)，則它們被稱作（一組）重邊。
簡單圖 (simple graph)：若一個圖中沒有自環和重邊，它被稱為簡單圖。具有至少兩個頂點的簡單無向圖中一定存在度相同的結點。（鴿巢原理）
如果一張圖中有自環或重邊，則稱它為 多重圖 (multigraph)。
Warning
在無向圖中 \((u, v)\) 和 \((v, u)\) 算一組重邊，而在有向圖中，\(u \to v\) 和 \(v \to u\) 不為重邊。
Warning
在題目中，如果沒有特殊説明，是可以存在自環和重邊的，在做題時需特殊考慮。
度數
與一個頂點 \(v\) 關聯的邊的條數稱作該頂點的 度 (degree)，記作 \(d(v)\)。特別地，對於邊 \((v, v)\)，則每條這樣的邊要對 \(d(v)\) 產生 \(2\) 的貢獻。
對於無向簡單圖，有 \(d(v) = \left| N(v) \right|\)。
握手定理（又稱圖論基本定理）：對於任何無向圖 \(G = (V, E)\)，有 \(\sum_{v \in V} d(v) = 2 \left| E \right|\)。
推論：在任意圖中，度數為奇數的點必然有偶數個。
若 \(d(v) = 0\)，則稱 \(v\) 為 孤立點 (isolated vertex)。
若 \(d(v) = 1\)，則稱 \(v\) 為 葉節點 (leaf vertex)/懸掛點 (pendant vertex)。
若 \(2 \mid d(v)\)，則稱 \(v\) 為 偶點 (even vertex)。
若 \(2 \nmid d(v)\)，則稱 \(v\) 為 奇點 (odd vertex)。圖中奇點的個數是偶數。
若 \(d(v) = \left| V \right| - 1\)，則稱 \(v\) 為 支配點 (universal vertex)。
對一張圖，所有節點的度數的最小值稱為 \(G\) 的 最小度 (minimum degree)，記作 \(\delta (G)\)；最大值稱為 最大度 (maximum degree)，記作 \(\Delta (G)\)。即：\(\delta (G) = \min_{v \in G} d(v)\)，\(\Delta (G) = \max_{v \in G} d(v)\)。
在有向圖 \(G = (V, E)\) 中，以一個頂點 \(v\) 為起點的邊的條數稱為該頂點的 出度 (out-degree)，記作 \(d^+(v)\)。以一個頂點 \(v\) 為終點的邊的條數稱為該節點的 入度 (in-degree)，記作 \(d^-(v)\)。顯然 \(d^+(v)+d^-(v)=d(v)\)。
對於任何有向圖 \(G = (V, E)\)，有：
若對一張無向圖 \(G = (V, E)\)，每個頂點的度數都是一個固定的常數 \(k\)，則稱 \(G\) 為 \(k\)- 正則圖 (\(k\)-regular graph)。
如果給定一個序列 a，可以找到一個圖 G，以其為度數列，則稱 a 是 可圖化 的。
如果給定一個序列 a，可以找到一個簡單圖 G，以其為度數列，則稱 a 是 可簡單圖化 的。
路徑
途徑 (walk)：途徑是連接一連串頂點的邊的序列，可以為有限或無限長度。形式化地説，一條有限途徑 \(w\) 是一個邊的序列 \(e_1, e_2, \ldots, e_k\)，使得存在一個頂點序列 \(v_0, v_1, \ldots, v_k\) 滿足 \(e_i = (v_{i-1}, v_i)\)，其中 \(i \in [1, k]\)。這樣的途徑可以簡寫為 \(v_0 \to v_1 \to v_2 \to \cdots \to v_k\)。通常來説，邊的數量 \(k\) 被稱作這條途徑的 長度（如果邊是帶權的，長度通常指途徑上的邊權之和，題目中也可能另有定義）。
跡 (trail)：對於一條途徑 \(w\)，若 \(e_1, e_2, \ldots, e_k\) 兩兩互不相同，則稱 \(w\) 是一條跡。
路徑 (path)（又稱 簡單路徑 (simple path)）：對於一條跡 \(w\)，若其連接的點的序列中點兩兩不同，則稱 \(w\) 是一條路徑。
迴路 (circuit)：對於一條跡 \(w\)，若 \(v_0 = v_k\)，則稱 \(w\) 是一條迴路。
環/圈 (cycle)（又稱 簡單迴路/簡單環 (simple circuit)）：對於一條迴路 \(w\)，若 \(v_0 = v_k\) 是點序列中唯一重複出現的點對，則稱 \(w\) 是一個環。
Warning
關於路徑的定義在不同地方可能有所不同，如，「路徑」可能指本文中的「途徑」，「環」可能指本文中的「迴路」。如果在題目中看到類似的詞彙，且沒有「簡單路徑」/「非簡單路徑」（即本文中的「途徑」）等特殊説明，最好詢問一下具體指什麼。
子圖
對一張圖 \(G = (V, E)\)，若存在另一張圖 \(H = (V', E')\) 滿足 \(V' \subseteq V\) 且 \(E' \subseteq E\)，則稱 \(H\) 是 \(G\) 的 子圖 (subgraph)，記作 \(H \subseteq G\)。
若對 \(H \subseteq G\)，滿足 \(\forall u, v \in V'\)，只要 \((u, v) \in E\)，均有 \((u, v) \in E'\)，則稱 \(H\) 是 \(G\) 的 導出子圖/誘導子圖 (induced subgraph)。
容易發現，一個圖的導出子圖僅由子圖的點集決定，因此點集為 \(V'\)(\(V' \subseteq V\)) 的導出子圖稱為 \(V'\) 導出的子圖，記作 \(G \left[ V' \right]\)。
若 \(H \subseteq G\) 滿足 \(V' = V\)，則稱 \(H\) 為 \(G\) 的 生成子圖/支撐子圖 (spanning subgraph)。
顯然，\(G\) 是自身的子圖，支撐子圖，導出子圖；無邊圖 是 \(G\) 的支撐子圖。原圖 \(G\) 和無邊圖都是 \(G\) 的平凡子圖。
如果一張無向圖 \(G\) 的某個生成子圖 \(F\) 為 \(k\)- 正則圖，則稱 \(F\) 為 \(G\) 的一個 \(k\)- 因子 (\(k\)-factor)。
如果有向圖 \(G = (V, E)\) 的導出子圖 \(H = G \left[ V^\ast \right]\) 滿足 \(\forall v \in V^\ast, (v, u) \in E\)，有 \(u \in V^\ast\)，則稱 \(H\) 為 \(G\) 的一個 閉合子圖 (closed subgraph)。
連通
無向圖
對於一張無向圖 \(G = (V, E)\)，對於 \(u, v \in V\)，若存在一條途徑使得 \(v_0 = u, v_k = v\)，則稱 \(u\) 和 \(v\) 是 連通的 (connected)。由定義，任意一個頂點和自身連通，任意一條邊的兩個端點連通。
若無向圖 \(G = (V, E)\)，滿足其中任意兩個頂點均連通，則稱 \(G\) 是 連通圖 (connected graph)，\(G\) 的這一性質稱作 連通性 (connectivity)。
若 \(H\) 是 \(G\) 的一個連通子圖，且不存在 \(F\) 滿足 \(H\subsetneq F \subseteq G\) 且 \(F\) 為連通圖，則 \(H\) 是 \(G\) 的一個 連通塊/連通分量 (connected component)（極大連通子圖）。
有向圖
對於一張有向圖 \(G = (V, E)\)，對於 \(u, v \in V\)，若存在一條途徑使得 \(v_0 = u, v_k = v\)，則稱 \(u\) 可達 \(v\)。由定義，任意一個頂點可達自身，任意一條邊的起點可達終點。（無向圖中的連通也可以視作雙向可達。）
若一張有向圖的節點兩兩互相可達，則稱這張圖是 強連通的 (strongly connected)。
若一張有向圖的邊替換為無向邊後可以得到一張連通圖，則稱原來這張有向圖是 弱連通的 (weakly connected)。
與連通分量類似，也有 弱連通分量 (weakly connected component)（極大弱連通子圖）和 強連通分量 (strongly connected component)（極大強連通子圖）。
相關算法請參見 強連通分量。
割
在本部分中，有向圖的「連通」一般指「強連通」。
對於連通圖 \(G = (V, E)\)，若 \(V'\subseteq V\) 且 \(G\left[V\setminus V'\right]\)（即從 \(G\) 中刪去 \(V'\) 中的點）不是連通圖，則 \(V'\) 是圖 \(G\) 的一個 點割集 (vertex cut/separating set)。大小為一的點割集又被稱作 割點 (cut vertex)。
對於連通圖 \(G = (V, E)\) 和整數 \(k\)，若 \(|V|\ge k+1\) 且 \(G\) 不存在大小為 \(k-1\) 的點割集，則稱圖 \(G\) 是 \(k\)- 點連通的 (\(k\)-vertex-connected)，而使得上式成立的最大的 \(k\) 被稱作圖 \(G\) 的 點連通度 (vertex connectivity)，記作 \(\kappa(G)\)。（對於非完全圖，點連通度即為最小點割集的大小，而完全圖 \(K_n\) 的點連通度為 \(n-1\)。）
對於圖 \(G = (V, E)\) 以及 \(u, v\in V\) 滿足 \(u\ne v\)，\(u\) 和 \(v\) 不相鄰，\(u\) 可達 \(v\)，若 \(V'\subseteq V\)，\(u, v\notin V'\)，且在 \(G\left[V\setminus V'\right]\) 中 \(u\) 和 \(v\) 不連通，則 \(V'\) 被稱作 \(u\) 到 \(v\) 的點割集。\(u\) 到 \(v\) 的最小點割集的大小被稱作 \(u\) 到 \(v\) 的 局部點連通度 (local connectivity)，記作 \(\kappa(u, v)\)。
還可以在邊上作類似的定義：
對於連通圖 \(G = (V, E)\)，若 \(E'\subseteq E\) 且 \(G' = (V, E\setminus E')\)（即從 \(G\) 中刪去 \(E'\) 中的邊）不是連通圖，則 \(E'\) 是圖 \(G\) 的一個 邊割集 (edge cut)。大小為一的邊割集又被稱作 橋 (bridge)。
對於連通圖 \(G = (V, E)\) 和整數 \(k\)，若 \(G\) 不存在大小為 \(k-1\) 的邊割集，則稱圖 \(G\) 是 \(k\)- 邊連通的 (\(k\)-edge-connected)，而使得上式成立的最大的 \(k\) 被稱作圖 \(G\) 的 邊連通度 (edge connectivity)，記作 \(\lambda(G)\)。（對於任何圖，邊連通度即為最小邊割集的大小。）
對於圖 \(G = (V, E)\) 以及 \(u, v\in V\) 滿足 \(u\ne v\)，\(u\) 可達 \(v\)，若 \(E'\subseteq E\)，且在 \(G'=(V, E\setminus E')\) 中 \(u\) 和 \(v\) 不連通，則 \(E'\) 被稱作 \(u\) 到 \(v\) 的邊割集。\(u\) 到 \(v\) 的最小邊割集的大小被稱作 \(u\) 到 \(v\) 的 局部邊連通度 (local edge-connectivity)，記作 \(\lambda(u, v)\)。
點雙連通 (biconnected) 幾乎與 \(2\)- 點連通完全一致，除了一條邊連接兩個點構成的圖，它是點雙連通的，但不是 \(2\)- 點連通的。換句話説，沒有割點的連通圖是點雙連通的。
邊雙連通 (\(2\)-edge-connected) 與 \(2\)- 邊雙連通完全一致。換句話説，沒有橋的連通圖是邊雙連通的。
與連通分量類似，也有 點雙連通分量 (biconnected component)（極大點雙連通子圖）和 邊雙連通分量 (\(2\)-edge-connected component)（極大邊雙連通子圖）。
Whitney 定理：對任意的圖 \(G\)，有 \(\kappa(G)\le \lambda(G)\le \delta(G)\)。（不等式中的三項分別為點連通度、邊連通度、最小度。）
稀疏圖/稠密圖
若一張圖的邊數遠小於其點數的平方，那麼它是一張 稀疏圖 (sparse graph)。
若一張圖的邊數接近其點數的平方，那麼它是一張 稠密圖 (dense graph)。
這兩個概念並沒有嚴格的定義，一般用於討論 時間複雜度 為 \(O(|V|^2)\) 的算法與 \(O(|E|)\) 的算法的效率差異（在稠密圖上這兩種算法效率相當，而在稀疏圖上 \(O(|E|)\) 的算法效率明顯更高）。
補圖
對於無向簡單圖 \(G = (V, E)\)，它的 補圖 (complement graph) 指的是這樣的一張圖：記作 \(\bar G\)，滿足 \(V \left( \bar G \right) = V \left( G \right)\)，且對任意節點對 \((u, v)\)，\((u, v) \in E \left( \bar G \right)\) 當且僅當 \((u, v) \notin E \left( G \right)\)。
反圖
對於有向圖 \(G = (V, E)\)，它的 反圖 (transpose graph) 指的是點集不變，每條邊反向得到的圖，即：若 \(G\) 的反圖為 \(G'=(V, E')\)，則 \(E'=\{(v, u)|(u, v)\in E\}\)。
特殊的圖
若無向簡單圖 \(G\) 滿足任意不同兩點間均有邊，則稱 \(G\) 為 完全圖 (complete graph)，\(n\) 階完全圖記作 \(K_n\)。若有向圖 \(G\) 滿足任意不同兩點間都有兩條方向不同的邊，則稱 \(G\) 為 有向完全圖 (complete digraph)。
邊集為空的圖稱為 無邊圖 (edgeless graph)、空圖 (empty graph) 或 零圖 (null graph)，\(n\) 階無邊圖記作 \(\overline{K}_n\) 或 \(N_n\)。\(N_n\) 與 \(K_n\) 互為補圖。
Warning
零圖 (null graph) 也可指 零階圖 (order-zero graph) \(K_0\)，即點集與邊集均為空的圖。
若有向簡單圖 \(G\) 滿足任意不同兩點間都有恰好一條邊（單向），則稱 \(G\) 為 競賽圖 (tournament graph)。
若無向簡單圖 \(G = \left( V, E \right)\) 的所有邊恰好構成一個圈，則稱 \(G\) 為 環圖/圈圖 (cycle graph)，\(n\)(\(n \geq 3\)) 階圈圖記作 \(C_n\)。易知，一張圖為圈圖的充分必要條件是，它是 \(2\)- 正則連通圖。
若無向簡單圖 \(G = \left( V, E \right)\) 滿足，存在一個點 \(v\) 為支配點，其餘點之間沒有邊相連，則稱 \(G\) 為 星圖/菊花圖 (star graph)，\(n + 1\)(\(n \geq 1\)) 階星圖記作 \(S_n\)。
若無向簡單圖 \(G = \left( V, E \right)\) 滿足，存在一個點 \(v\) 為支配點，其它點之間構成一個圈，則稱 \(G\) 為 輪圖 (wheel graph)，\(n + 1\)(\(n \geq 3\)) 階輪圖記作 \(W_n\)。
若無向簡單圖 \(G = \left( V, E \right)\) 的所有邊恰好構成一條簡單路徑，則稱 \(G\) 為 鏈 (chain/path graph)，\(n\) 階的鏈記作 \(P_n\)。易知，一條鏈由一個圈圖刪去一條邊而得。
如果一張無向連通圖不含環，則稱它是一棵 樹 (tree)。相關內容詳見 樹基礎。
如果一張無向連通圖包含恰好一個環，則稱它是一棵 基環樹 (pseudotree)。
如果一張有向弱連通圖每個點的入度都為 \(1\)，則稱它是一棵 基環外向樹。
如果一張有向弱連通圖每個點的出度都為 \(1\)，則稱它是一棵 基環內向樹。
多棵樹可以組成一個 森林 (forest)，多棵基環樹可以組成 基環森林 (pseudoforest)，多棵基環外向樹可以組成 基環外向樹森林，多棵基環內向樹可以組成 基環內向森林 (functional graph)。
如果一張無向連通圖的每條邊最多在一個環內，則稱它是一棵 仙人掌 (cactus)。多棵仙人掌可以組成 沙漠。
如果一張圖的點集可以被分為兩部分，每一部分的內部都沒有連邊，那麼這張圖是一張 二分圖 (bipartite graph)。如果二分圖中任何兩個不在同一部分的點之間都有連邊，那麼這張圖是一張 完全二分圖 (complete bipartite graph/biclique)，一張兩部分分別有 \(n\) 個點和 \(m\) 個點的完全二分圖記作 \(K_{n, m}\)。相關內容詳見 二分圖。
如果一張圖可以畫在一個平面上，且沒有兩條邊在非端點處相交，那麼這張圖是一張 平面圖 (planar graph)。一張圖的任何子圖都不是 \(K_5\) 或 \(K_{3, 3}\) 是其為一張平面圖的充要條件。對於簡單連通平面圖 \(G=(V, E)\) 且 \(V\ge 3\)，\(|E|\le 3|V|-6\)。
同構
兩個圖 \(G\) 和 \(H\)，如果存在一個雙射 \(f : V(G) \to V(H)\)，且滿足 \((u,v)\in E(G)\)，當且僅當 \((f(u),f(v))\in E(H)\)，則我們稱 \(f\) 為 \(G\) 到 \(H\) 的一個 同構 (isomorphism)，且圖 \(G\) 與圖 \(H\) 是 同構的 (isomorphic)，記作 \(G \cong H\)。
從定義可知，若 \(G \cong H\)，必須滿足：
- \(|V(G)|=|V(H)|,|E(G)|=|E(H)|\)
- \(G\) 和 \(H\) 結點度的非增序列相同
- \(G\) 和 \(H\) 存在同構的導出子圖
無向簡單圖的二元運算
對於無向簡單圖，我們可以定義如下二元運算：
交 (intersection)：圖 \(G = \left( V_1, E_1 \right), H = \left( V_2, E_2 \right)\) 的交定義成圖 \(G \cap H = \left( V_1 \cap V_2, E_1 \cap E_2 \right)\)。
容易證明兩個無向簡單圖的交還是無向簡單圖。
並 (union)：圖 \(G = \left( V_1, E_1 \right), H = \left( V_2, E_2 \right)\) 的並定義成圖 \(G \cup H = \left( V_1 \cup V_2, E_1 \cup E_2 \right)\)。
和 (sum)/直和 (direct sum)：對於 \(G = \left( V_1, E_1 \right), H = \left( V_2, E_2 \right)\)，任意構造 \(H' \cong H\) 使得 \(V \left( H' \right) \cap V_1 = \varnothing\)(\(H'\) 可以等於 \(H\))。此時與 \(G \cup H'\) 同構的任何圖稱為 \(G\) 和 \(H\) 的和/直和/不交併，記作 \(G + H\) 或 \(G \oplus H\)。
若 \(G\) 與 \(H\) 的點集本身不相交，則 \(G \cup H = G + H\)。
比如，森林可以定義成若干棵樹的和。
並與和的區別
可以理解為，「並」會讓兩張圖中「名字相同」的點、邊合併，而「和」則不會。
特殊的點集/邊集
支配集
對於無向圖 \(G=(V, E)\)，若 \(V'\subseteq V\) 且 \(\forall v\in(V\setminus V')\) 存在邊 \((u, v)\in E\) 滿足 \(u\in V'\)，則 \(V'\) 是圖 \(G\) 的一個 支配集 (dominating set)。
無向圖 \(G\) 最小的支配集的大小記作 \(\gamma(G)\)。求一張圖的最小支配集是 NP 困難 的。
對於有向圖 \(G=(V, E)\)，若 \(V'\subseteq V\) 且 \(\forall v\in(V\setminus V')\) 存在邊 \((u, v)\in E\) 滿足 \(u\in V'\)，則 \(V'\) 是圖 \(G\) 的一個 出 - 支配集 (out-dominating set)。類似地，可以定義有向圖的 入 - 支配集 (in-dominating set)。
有向圖 \(G\) 最小的出 - 支配集大小記作 \(\gamma^+(G)\)，最小的入 - 支配集大小記作 \(\gamma^-(G)\)。
邊支配集
對於圖 \(G=(V, E)\)，若 \(E'\subseteq E\) 且 \(\forall e\in(E\setminus E')\) 存在 \(E'\) 中的邊與其有公共點，則稱 \(E'\) 是圖 \(G\) 的一個 邊支配集 (edge dominating set)。
求一張圖的最小邊支配集是 NP 困難 的。
獨立集
對於圖 \(G=(V, E)\)，若 \(V'\subseteq V\) 且 \(V'\) 中任意兩點都不相鄰，則 \(V'\) 是圖 \(G\) 的一個 獨立集 (independent set)。
圖 \(G\) 最大的獨立集的大小記作 \(\alpha(G)\)。求一張圖的最大獨立集是 NP 困難 的。
匹配
對於圖 \(G=(V, E)\)，若 \(E'\in E\) 且 \(E'\) 中任意兩條不同的邊都沒有公共的端點，且 \(E'\) 中任意一條邊都不是自環，則 \(E'\) 是圖 \(G\) 的一個 匹配 (matching)，也可以叫作 邊獨立集 (independent edge set)。如果一個點是匹配中某條邊的一個端點，則稱這個點是 被匹配的 (matched)/飽和的 (saturated)，否則稱這個點是 不被匹配的 (unmatched)。
邊數最多的匹配被稱作一張圖的 最大匹配 (maximum-cardinality matching)。圖 \(G\) 的最大匹配的大小記作 \(\nu(G)\)。
如果邊帶權，那麼權重之和最大的匹配被稱作一張圖的 最大權匹配 (maximum-weight matching)。
如果一個匹配在加入任何一條邊後都不再是一個匹配，那麼這個匹配是一個 極大匹配 (maximal matching)。最大的極大匹配就是最大匹配，任何最大匹配都是極大匹配。極大匹配一定是邊支配集，但邊支配集不一定是匹配。最小極大匹配和最小邊支配集大小相等，但最小邊支配集不一定是匹配。求最小極大匹配是 NP 困難的。
如果在一個匹配中所有點都是被匹配的，那麼這個匹配是一個 完美匹配 (perfect matching)。如果在一個匹配中只有一個點不被匹配，那麼這個匹配是一個 準完美匹配 (near-perfect matching)。
求一張普通圖或二分圖的匹配或完美匹配個數都是 #P 完全 的。
對於一個匹配 \(M\)，若一條路徑以非匹配點為起點，每相鄰兩條邊的其中一條在匹配中而另一條不在匹配中，則這條路徑被稱作一條 交替路徑 (alternating path)；一條在非匹配點終止的交替路徑，被稱作一條 增廣路徑 (augmenting path)。
托特定理：\(n\) 階無向圖 \(G\) 有完美匹配當且僅當對於任意的 \(V' \subset V(G)\)，\(p_{\text{odd}}(G-V')\leq |V'|\)，其中 \(p_{\text{odd}}\) 表示奇數階連通分支數。
托特定理（推論）：任何無橋 3 - 正則圖都有完美匹配。
點覆蓋
對於圖 \(G=(V, E)\)，若 \(V'\subseteq V\) 且 \(\forall e\in E\) 滿足 \(e\) 的至少一個端點在 \(V'\) 中，則稱 \(V'\) 是圖 \(G\) 的一個 點覆蓋 (vertex cover)。
點覆蓋集必為支配集，但極小點覆蓋集不一定是極小支配集。
一個點集是點覆蓋的充要條件是其補集是獨立集，因此最小點覆蓋的補集是最大獨立集。求一張圖的最小點覆蓋是 NP 困難 的。
一張圖的任何一個匹配的大小都不超過其任何一個點覆蓋的大小。完全二分圖 \(K_{n, m}\) 的最大匹配和最小點覆蓋大小都為 \(\min(n, m)\)。
邊覆蓋
對於圖 \(G=(V, E)\)，若 \(E'\subseteq E\) 且 \(\forall v\in V\) 滿足 \(v\) 與 \(E'\) 中的至少一條邊相鄰，則稱 \(E'\) 是圖 \(G\) 的一個 邊覆蓋 (edge cover)。
最小邊覆蓋的大小記作 \(\rho(G)\)，可以由最大匹配貪心擴展求得：對於所有非匹配點，將其一條鄰邊加入最大匹配中，即得到了一個最小邊覆蓋。
最大匹配也可以由最小邊覆蓋求得：對於最小邊覆蓋中每對有公共點的邊刪去其中一條。
一張圖的最小邊覆蓋的大小加上最大匹配的大小等於圖的點數，即 \(\rho(G)+\nu(G)=|V(G)|\)。
一張圖的最大匹配的大小不超過最小邊覆蓋的大小，即 \(\nu(G)\le\rho(G)\)。特別地，完美匹配一定是一個最小邊覆蓋，這也是上式取到等號的唯一情況。
一張圖的任何一個獨立集的大小都不超過其任何一個邊覆蓋的大小。完全二分圖 \(K_{n, m}\) 的最大獨立集和最小邊覆蓋大小都為 \(\max(n, m)\)。
團
對於圖 \(G=(V, E)\)，若 \(V'\subseteq V\) 且 \(V'\) 中任意兩個不同的頂點都相鄰，則 \(V'\) 是圖 \(G\) 的一個 團 (clique)。團的導出子圖是完全圖。
如果一個團在加入任何一個頂點後都不再是一個團，則這個團是一個 極大團 (maximal clique)。
一張圖的最大團的大小記作 \(\omega(G)\)，最大團的大小等於其補圖最大獨立集的大小，即 \(\omega(G)=\alpha(\bar{G})\)。求一張圖的最大團是 NP 困難 的。
參考資料
Wikipedia（以及相關概念的對應詞條）
離散數學（修訂版），田文成 周祿新 編著，天津文學出版社，P184-187
戴一奇，胡冠章，陳衞。圖論與代數結構 [M]. 北京：清華大學出版社，1995.
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用