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