《圖論課件第五章匹配與因子分解》ppt課件-全文預(yù)覽
【正文】 1,0),和 (x1 ,x2,…,x n1,1) 之間的全體邊所成之集為 M. 顯然， M中的邊均不相鄰接，所以作成 k方體的匹配，又容易知道： |M|= M是完美匹配。所以 k方體是偶圖。 (1) 證明一：證明每個 k方體都是 k正則偶圖。 Hall是一名雅致的學(xué)者，對學(xué)生特別友好，當(dāng)他覺得有必要批評學(xué)生時，他都會以一種十分溫和的方式建議他們改正。 (5) Hall (19041982) 英國人， 20世紀(jì)最偉大的數(shù)學(xué)家之一。 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的匹配。 令 M*是 G的一個最大匹配，但是不飽和 X的頂點 u. u 示意圖 G 1 0 x t 0 1 2 ?1 ? 0 1 n 15 又 令 Z是通過 M*與點 u相連形成的所有 M*交錯路上的點集。 G : d, e, f, g 。 C : b, e 。 G : d, e, f, g 。 C : b, e 。下面看一個例子： 問題的提出 1 0 x t 0 1 2 ?1 ? 0 1 n 10 有 7名研究生 A, B, C, D, E, F, G畢業(yè)尋找工作。Nash的生活被改編成電影 《 美麗的心靈 》 ，獲 02年奧斯卡金像獎。他不僅在圖論領(lǐng)域做出了許多貢獻(xiàn)，而且四處奔波傳播圖論，推動了圖論的普及和發(fā)展。這與條件矛盾。 “充分性” 若不然，設(shè) M1是 G的一個最大匹配，則 |M1||M|。 1 0 x t 0 1 2 ?1 ? 0 1 n 7 貝爾熱定理 定理 1 (貝爾熱， 1957) G的匹配 M是最大匹配，當(dāng)且僅當(dāng) G不包含 M可擴(kuò)路。 1 0 x t 0 1 2 ?1 ? 0 1 n 6 (3)、 M交錯路 如果 M是圖 G的匹配， G中一條由 M中的邊和非 M中的邊交錯形成的路，稱為 G中的一條 M交錯路。 v1 v7 v6 G v8 v2 v3 v5 v4 M1=｛ v6v7｝ M2=｛ v6v7, v1v8｝ M3=｛ v6v7, v1v8, v3v4｝ M1,M2,M3等都是 G的匹配。 (一 )、圖的匹配與貝爾熱定理 如果 G中頂點 v是 G的匹配 M中某條邊的端點，稱它為 M飽和點，否則為 M非飽和點。 G的一個 最大匹配 G的一個完美匹配 注：一個圖 G不一定存在完美匹配。其中后者是 M可擴(kuò)路。 M1中邊比M中多一條，這與 M是 G的最大匹配矛盾。 在每個偶圈中， M1與 M中邊數(shù)相等；但因 |M1||M|，所以，至少有一條路 P，其起點和終點都是 M非飽和點，于是，它是 G的一條 M可擴(kuò)路。他的 《 無限圖理論及其應(yīng)用 》 (1958) 是繼哥尼之后的圖論歷史上的第二本圖論專著。在博弈領(lǐng)域，他引入了 Nash均衡之外的另一種均衡系統(tǒng)。 (二 )、偶圖的匹配與覆蓋 在日常生活，工程技術(shù)中，常常遇到求偶圖的匹配問題。 B : a, b, d, f, g 。 F : c, e 。 B : a, b, d, f, g 。 F : c, e 。 1 0 x t 0 1 2 ?1 ? 0 1 n 14 證明：“必要性”
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1