圖論課件第五章匹配與因子分解ppt課件(編輯修改稿)
2025-06-08 07:32 本頁面
【文章內(nèi)容簡介】 所以，不存在飽和 X每個頂點的匹配。 下面我們證明 Hall定理。 1 0 x t 0 1 2 ?1 ? 0 1 n 14 證明：“必要性” 如果 G存在飽和 X每個頂點的匹配，由匹配的定義，X的每個頂點在 Y中至少有一個鄰接點，所以 : , ( )S X N S S? ? ?對有 “充分性” 如果 G是滿足條件 (*)的偶圖 ,但是不存在飽和 X每個頂點的匹配。 令 M*是 G的一個最大匹配，但是不飽和 X的頂點 u. u 示意圖 G 1 0 x t 0 1 2 ?1 ? 0 1 n 15 又 令 Z是通過 M*與點 u相連形成的所有 M*交錯路上的點集。 因 M*是最大匹配，所以 u是所有交錯路上唯一的一個未飽和點。 令 S=X∩Z , T=Z∩Y 顯然， S｛ u｝中點與 T中點在 M*下配對，即： |T| = |S| 1 |S| 即： |N(S)| = |T| = |S| 1 |S| ，與條件矛盾。 u T S 注 : (1) G=(X,Y)存在 飽和 X每個頂點的匹配 也常說成存在 由 X到 Y的匹配 。 1 0 x t 0 1 2 ?1 ? 0 1 n 16 (2) Hall定理也可表述為：設(shè) G=(X,Y)是偶圖，如果存在X的一個子集 S,使得 |N(S)| |S| ，那么 G中不存在由 X到 Y的匹配。 (3) Hall定理也稱為“婚姻定理”，表述如下： “婚姻定理” ：在一個由 r個女人和 s個男人構(gòu)成的人群中，1≦r≦s 。在熟識的男女之間可能出現(xiàn) r對婚姻的充分必要條件是，對每個整數(shù) k(1≦k≦r), 任意 k個女人共認(rèn)識至少 k個男人。 (4) Hall定理是在偶圖中求最大匹配算法的理論基礎(chǔ)，即匈牙利算法基礎(chǔ)。 (5) Hall (19041982) 英國人， 20世紀(jì)最偉大的數(shù)學(xué)家之一。主要功績是在代數(shù)學(xué)領(lǐng)域。在劍橋大學(xué)工作期間，主要研究群論， 1932年發(fā)表的關(guān)于素數(shù)冪階群論文是他最有名 1 0 x t 0 1 2 ?1 ? 0 1 n 17 的工作。匹配定理是他 1935年在劍橋大學(xué)做講師時發(fā)表的結(jié)果。 Hall是一名雅致的學(xué)者，對學(xué)生特別友好，當(dāng)他覺得有必要批評學(xué)生時，他都會以一種十分溫和的方式建議他們改正。 推論：若 G是 k (k0)正則偶圖，則 G存在完美匹配。 證明：一方面，由于 G是 k (k0)正則偶圖 ,所以 k|X|=k|Y|,于是得 |X| = |Y|； 另一方面，對于 X的任一非空子集 S, 設(shè) E1與 E2分別是與 S和 N(S)關(guān)聯(lián)的邊集，顯然有： 即： 12EE?12 ()E k S E k N S? ? ? 由 Hall定理，存在由 X到 Y的匹配 .又 |X| = |Y|，所以 G存在完美匹配。 1 0 x t 0 1 2 ?1 ? 0 1 n 18 例 2 (1) 證明：每個 k方體都有完美匹配 (k大于等于 2) (2) 求 K2n和 Kn,n中不同的完美匹配的個數(shù)。 (1) 證明一：證明每個 k方體都是 k正則偶圖。 事實上，由 k方體的構(gòu)造： k方體有 2k個頂點，每個頂點可以用長度為 k的二進(jìn)制碼來表示，兩個頂點連線當(dāng)且僅當(dāng)代表兩個頂點的二進(jìn)制碼只有一位坐標(biāo)不同。 如果我們劃分 k方體的 2k個頂點，把坐標(biāo)之和為偶數(shù)的頂點歸入 X，否則歸入 Y。顯然， X中頂點互不鄰接， Y中頂點也如此。所以 k方體是偶圖。 又不難知道 k方體的每個頂點度數(shù)為 k,所以 k方體是
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1