黑蛇冰河世紀 2022-12-16

7。5 二部圖及匹配

7。5。1二部圖

在許多實際問題中常用到二部圖，本節先介紹二部圖的基本概念和主要結論，然後介紹它的一個重要應用—匹配。

定義7。5。1 若無向圖

G=\left<\begin{matrix}V，E\end{matrix}\right>

G=⟨

V，E

​

⟩

的頂點集

V

V

能分成兩個子集

V_{1}

V

1

​

和

V_{2}

V

2

​

，滿足

（1）

V=V_{1}∪V_{2}

V=V

1

​

∪V

2

​

，

V_{1}∩V_{2}=φ

V

1

​

∩V

2

​

=φ

；

（2）

∀e=（u，v）∈E

∀e=（u，v）∈E

，均有

u∈V_{1}

u∈V

1

​

，

v∈V_{2}

v∈V

2

​

。