圖論 - 1 定義 - bipartite graph 二分圖 二部圖

前篇：圖論 - 1 定義 - 1

1️⃣ 簡易版定義

二部圖是一種特殊的圖，把所有「點」分成兩組，每條「邊」只能連 接不同組的點，同組內的點之間沒有任何邊。

舉個生活例子：把「棒球球員」放 A 組、「棒球球隊」放 B 組，邊代表「某球員曾效力某球隊」。同組內部不會連線 —— 這就是一個二部圖！

---

2️⃣ 專業版定義

設圖 G = (V, E)，其中 V 為點集合、E 為邊集合。

若存在一個分割 V = X ∪ Y，使得：

X ∩ Y = ∅

且所有邊 e ∈ E 均滿足：

e = {x, y},  x ∈ X, y ∈ Y

則稱 G 為二部圖（Bipartite Graph），(X, Y) 稱為其二部分割（bipartition）。

特殊情形——完全二部圖 K_m, n>：若 |X| = m、|Y| = n，且 X 中每點都與 Y 中每點相連，共有 m × n 條邊，則稱為完全二部圖。

📌 關鍵性質：一個圖是二部圖，若且唯若它不含奇數長度的環（odd cycle）。

---

3️⃣ 結構圖解（Mermaid 心智圖）

 
graph LR
  subgraph X組["X 組（左側點）"]
    x1((x₁))
    x2((x₂))
    x3((x₃))
  end
  subgraph Y組["Y 組（右側點）"]
    y1((y₁))
    y2((y₂))
    y3((y₃))
  end
  x1 --- y1
  x1 --- y2
  x2 --- y2
  x2 --- y3
  x3 --- y1
  x3 --- y3  

 

---

✅ 每條邊只跨越 X 與 Y 兩組之間，X 內、Y 內沒有任何邊。