圖論課件第五章匹配與因子分解ppt課件(已修改)
2025-05-24 07:32 本頁面
【正文】 1 0 x t 0 1 2 ?1 ? 0 1 n 1 圖論及其應(yīng)用 應(yīng)用數(shù)學(xué)學(xué)院 1 0 x t 0 1 2 ?1 ? 0 1 n 2 第五章 匹配與因子分解 主要內(nèi)容 一、偶圖的匹配問題 二、圖的因子分解 三、匈牙利算法與最優(yōu)匹配算法 教學(xué)時數(shù) 安排 6學(xué)時講授本章內(nèi)容 1 0 x t 0 1 2 ?1 ? 0 1 n 3 本次課主要內(nèi)容 (一 )、圖的匹配與貝爾熱定理 (二 )、偶圖的匹配與覆蓋 (三 )、托特定理 偶圖的匹配問題 1 0 x t 0 1 2 ?1 ? 0 1 n 4 圖的匹配相關(guān)概念 (1)、匹配 M 如果 M是圖 G的邊子集 (不含環(huán)），且M中的任意兩條邊沒有共同頂點，則稱 M是 G的一個匹配或?qū)蜻叒?dú)立集。 (一 )、圖的匹配與貝爾熱定理 如果 G中頂點 v是 G的匹配 M中某條邊的端點，稱它為 M飽和點，否則為 M非飽和點。 v1 v7 v6 G v8 v2 v3 v5 v4 M1=｛ v6v7｝ M2=｛ v6v7, v1v8｝ M3=｛ v6v7, v1v8, v3v4｝ M1,M2,M3等都是 G的匹配。 1 0 x t 0 1 2 ?1 ? 0 1 n 5 (2)、最大匹配 M 如果 M是圖 G的包含邊數(shù)最多的匹配，稱 M是 G的一個最大匹配。特別是，若最大匹配飽和了 G的所有頂點，稱它為 G的一個完美匹配。 G的一個 最大匹配 G的一個完美匹配 注：一個圖 G不一定存在完美匹配。 1 0 x t 0 1 2 ?1 ? 0 1 n 6 (3)、 M交錯路 如果 M是圖 G的匹配， G中一條由 M中的邊和非 M中的邊交錯形成的路，稱為 G中的一條 M交錯路。特別地，若 M交錯路的起點與終點是 M非飽和點，稱這種 M交錯路為 M可擴(kuò)路 。 在下圖中： v1 v7 v6 G v8 v2 v3 v5 v4 設(shè) M=｛ v7v8 , v3v4｝，則： 路 v6v7v8v3v4與 v1v7v8v2都是 M交錯路。其中后者是 M可擴(kuò)路。 1 0 x t 0 1 2 ?1 ? 0 1 n 7 貝爾熱定理 定理 1 (貝爾熱， 1957) G的匹配 M是最大匹配，當(dāng)且僅當(dāng) G不包含 M可擴(kuò)路。 證明：“必要性” 若 G包含一條 M可擴(kuò)路 P,則可令該可擴(kuò)路為： 1 2 3 2 2 1kkP v v v v v ?? 顯然， P中 M中的邊比非 M中的邊少一條。于是作新的匹配 M1,它當(dāng)中的邊由 P中非 M中邊組成。 M1中邊比M中多一條，這與 M是 G的最大匹配矛盾。 “充分性” 若不然，設(shè) M1是 G的一個最大匹配，則 |M1||M|。 1 0 x t 0 1 2 ?1 ? 0 1 n 8 令 H = M1ΔM。 容易知道： G[H]的每個分支或者是由 M1與
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1