【正文】 3正則圖非 H圖，有 38個(gè)點(diǎn)。 托特 (19172022) 英國著名數(shù)學(xué)家。但是，他的興趣是數(shù)學(xué)。二戰(zhàn)后，托特回到劍橋攻讀數(shù)學(xué)研究生。在他的數(shù)學(xué)博士論文中，復(fù)興了擬陣?yán)碚?(惠特尼引入的 ).1948年博士畢業(yè)后，受 20世紀(jì)偉大的幾何學(xué)家 Coxeter邀請前往多倫多大學(xué)任教，成為組合數(shù)學(xué)杰出學(xué)者。 托特是 20世紀(jì)偉大的數(shù)學(xué)家之一，在近代數(shù)學(xué)史上占有一定的地位。 托特還喜歡寫詩，在 1969年寫了一首反映圖論的詩： 哥尼斯堡的一些市民， 漫步在河畔。 “Euler,我們一起散步吧！” 那些市民在召喚。” “你們做不到”， Euler大聲吼道。 從哥尼斯堡到哥尼的書， 圖論的傳說正是如此， 而且越來越精彩， 綻放在密歇根和耶魯 該猜想錯(cuò)誤。 納什 —威廉斯猜想：每個(gè) 4連通 4正則圖是 H圖。 該猜想錯(cuò)誤。 托特猜想：每個(gè) 3連通 3正則偶圖是 H圖。 普魯默猜想：每個(gè) 2連通圖的平方是 H圖。 定理：每個(gè) 3正則 H圖至少有 3個(gè)生成圈。 90年在 《 系統(tǒng)科學(xué)與數(shù)學(xué) 》 學(xué)報(bào)上發(fā)表文章：“有限循環(huán)群上 Cayley有向圖的 H回路”，得到了該類圖的 H圈的計(jì)數(shù)公式。因?yàn)槲覀兛梢圆毁M(fèi)力地找到 : (1) E圖但非 H圖； (2) E圖且 H圖； (3) H圖但非E圖 。對于 G中任一頂點(diǎn) v，關(guān)聯(lián)于該頂點(diǎn)的 d(v)條邊將產(chǎn)生 L(G)中 條邊。 (4) 若圖 G和 G1有同構(gòu)的線圖，則除了一個(gè)是 K3而另一個(gè)是 K1,3外， G和 G1同構(gòu)。 G S(G) 又記： 1( ) ( ( ) )nnL G L S G??定理 3 (1)若 G是 E圖，則 L(G) 既是 E圖又是 H圖。 注：該定理逆不成立。 G L3(G) L(G) L2(G) 作業(yè) 請總結(jié)本章內(nèi)容 Email: 圖論及其應(yīng)用 任課教師：楊春 應(yīng)用數(shù)學(xué)學(xué)院 第五章 匹配與因子分解 主要內(nèi)容 一、偶圖的匹配問題 二、圖的因子分解 三、匈牙利算法與最優(yōu)匹配算法 教學(xué)時(shí)數(shù) 安排 6學(xué)時(shí)講授本章內(nèi)容 本次課主要內(nèi)容 (一 )、圖的匹配與貝爾熱定理 (二 )、偶圖的匹配與覆蓋 (三 )、托特定理 偶圖的匹配問題 圖的匹配相關(guān)概念 (1)、匹配 M 如果 M是圖 G的邊子集 (不含環(huán)），且M中的任意兩條邊沒有共同頂點(diǎn)，則稱 M是 G的一個(gè)匹配或?qū)蜻叒?dú)立集。 v1 v7 v6 G v8 v2 v3 v5 v4 M1=｛ v6v7｝ M2=｛ v6v7, v1v8｝ M3=｛ v6v7, v1v8, v3v4｝ M1,M2,M3等都是 G的匹配。特別是，若最大匹配飽和了 G的所有頂點(diǎn)，稱它為 G的一個(gè)完美匹配。 (3)、 M交錯(cuò)路 如果 M是圖 G的匹配， G中一條由 M中的邊和非 M中的邊交錯(cuò)形成的路，稱為 G中的一條 M交錯(cuò)路。 在下圖中： v1 v7 v6 G v8 v2 v3 v5 v4 設(shè) M=｛ v7v8 , v3v4｝，則： 路 v6v7v8v3v4與 v1v7v8v2都是 M交錯(cuò)路。 貝爾熱定理 定理 1 (貝爾熱， 1957) G的匹配 M是最大匹配，當(dāng)且僅當(dāng) G不包含 M可擴(kuò)路。于是作新的匹配 M1,它當(dāng)中的邊由 P中非 M中邊組成。 “充分性” 若不然，設(shè) M1是 G的一個(gè)最大匹配，則 |M1||M|。 容易知道： G[H]的每個(gè)分支或者是由 M1與 M中邊交替組成的偶圈，或者是由 M1與 M中邊交替組成的路。這與條件矛盾。 貝爾熱 (19262022) 法國著名數(shù)學(xué)家。他不僅在圖論領(lǐng)域做出了許多貢獻(xiàn)，而且四處奔波傳播圖論，推動了圖論的普及和發(fā)展。 貝爾熱在博弈論、拓?fù)鋵W(xué)領(lǐng)域里也有杰出貢獻(xiàn)。Nash的生活被改編成電影 《 美麗的心靈 》 ，獲 02年奧斯卡金像獎。他也是一位象棋高手，還創(chuàng)作過小說 《 誰殺害了 Densmore公爵 》 。下面看一個(gè)例子： 問題的提出 有 7名研究生 A, B, C, D, E, F, G畢業(yè)尋找工作。每名學(xué)生申請的職位如下： A : b, c 。 C : b, e 。 E : a, c, d, f 。 G : d, e, f, g 。于是，得到反映學(xué)生和職位之間的狀態(tài)圖： 問題轉(zhuǎn)化為求飽和 X每個(gè)頂點(diǎn)的一個(gè)匹配！ A : b, c 。 C : b, e 。 E : a, c, d, f 。 G : d, e, f, g 。 下面我們證明 Hall定理。 令 M*是 G的一個(gè)最大匹配，但是不飽和 X的頂點(diǎn) u. u 示意圖 G 又 令 Z是通過 M*與點(diǎn) u相連形成的所有 M*交錯(cuò)路上的點(diǎn)集。 令 S=X∩Z , T=Z∩Y 顯然， S｛ u｝中點(diǎn)與 T中點(diǎn)在 M*下配對，即： |T| = |S| 1 |S| 即： |N(S)| = |T| = |S| 1 |S| ，與條件矛盾。 (2) Hall定理也可表述為：設(shè) G=(X,Y)是偶圖，如果存在X的一個(gè)子集 S,使得 |N(S)| |S| ，那么 G中不存在由 X到 Y的匹配。在熟識的男女之間可能出現(xiàn) r對婚姻的充分必要條件是，對每個(gè)整數(shù) k(1≦k≦r), 任意 k個(gè)女人共認(rèn)識至少 k個(gè)男人。 (5) Hall (19041982) 英國人， 20世紀(jì)最偉大的數(shù)學(xué)家之一。在劍橋大學(xué)工作期間，主要研究群論， 1932年發(fā)表的關(guān)于素?cái)?shù)冪階群論文是他最有名 的工作。 Hall是一名雅致的學(xué)者，對學(xué)生特別友好，當(dāng)他覺得有必要批評學(xué)生時(shí)，他都會以一種十分溫和的方式建議他們改正。 證明：一方面，由于 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) 證明一：證明每個(gè) k方體都是 k正則偶圖。 如果我們劃分 k方體的 2k個(gè)頂點(diǎn)，把坐標(biāo)之和為偶數(shù)的頂點(diǎn)歸入 X，否則歸入 Y。所以 k方體是偶圖。 由推論： k方體存在完美匹配。 設(shè) k方體頂點(diǎn)二進(jìn)制碼為 (x1 ,x2,…,x n),我們?nèi)?(x1 ,x2,…,x n1,0),和 (x1 ,x2,…,x n1,1) 之間的全體邊所成之集為 M. 顯然， M中的邊均不相鄰接，所以作成 k方體的匹配，又容易知道： |M|= M是完美匹配。 K2n的任意一個(gè)頂點(diǎn)有 2n1中不同的方法被匹配。 證明：若不然，設(shè) M1與 M2是樹 T的兩個(gè)不同的完美匹配，那么 M1ΔM2≠Φ,且 T[M1ΔM2]每個(gè)頂點(diǎn)度數(shù)為 2，即它存在圈，于是推出 T中有圈，矛盾。 G的一個(gè)包含點(diǎn)數(shù)最少的點(diǎn)覆蓋稱為 G的最小點(diǎn)覆蓋，其包含的點(diǎn)數(shù)稱為 G的覆蓋數(shù)，記為 α (G). (a) 一個(gè)覆蓋 (b) 一個(gè)最小覆蓋 定理 2 設(shè) M是 G的匹配， K是 G的覆蓋，若 |M|=|K|,則M是最大匹配，而 G是最小覆蓋。