資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究匹配圖
匹配圖是圖的一個子圖，其中沒有邊彼此相鄰。簡單來說，任意兩條邊之間不應該有任何公共頂點。
匹配
設 'G' = (V, E) 為一個圖。如果 G 的每個頂點最多與 M 中的一條邊相關聯，則子圖稱為匹配 M(G)，即：
deg(V) ≤ 1 ∀ V ∈ G
這意味著在匹配圖 M(G) 中，頂點的度數應為 1 或 0，其中邊應來自圖 G。
符號 − M(G)
示例
.jpg)
在匹配中，
如果 deg(V) = 1，則 (V) 被稱為匹配的
如果 deg(V) = 0，則 (V) 未匹配。
在匹配中，沒有兩條邊是相鄰的。這是因為，如果任意兩條邊相鄰，則連線這兩條邊的頂點的度數將為 2，這違反了匹配規則。
最大匹配
如果不能將圖 'G' 的其他任何邊新增到 M，則稱圖 'G' 的匹配 M 為最大匹配。
示例
上圖中的 M1、M2、M3 是 G 的最大匹配。
最大匹配
也稱為最大最大匹配。最大匹配定義為具有最大邊數的最大匹配。
'G' 的最大匹配中的邊數稱為其匹配數。
示例
對於上面示例中給出的圖，M1 和 M2 是 'G' 的最大匹配，其匹配數為 2。因此，使用圖 G，我們最多隻能形成只有 2 條邊的子圖。因此，匹配數為 2。
完美匹配
如果圖 g (G) 的每個頂點都與匹配 (M) 的恰好一條邊相關聯，則稱圖 (G) 的匹配 (M) 為完美匹配，即：
deg(V) = 1 ∀ V
子圖中每個頂點的度數都應為1。
示例
在下圖中，M1 和 M2 是 G 的完美匹配示例。
注意 − 圖的每個完美匹配也是圖的最大匹配，因為在完美匹配圖中沒有機會新增更多邊。
圖的最大匹配不一定是完美的。如果圖 'G' 有一個完美匹配，則頂點數 |V(G)| 為偶數。如果是奇數，則最後一個頂點與另一個頂點配對，最終剩下一個單獨的頂點，無法與任何其他頂點配對，其度數為零。這顯然違反了完美匹配原則。
示例
注意 − 上述陳述的反面不一定為真。如果 G 的頂點數為偶數，則 M1 不一定是完美的。
示例
它是匹配，但不是完美匹配，即使它具有偶數個頂點。
340 次瀏覽
