第一章圖課件

第1章圖第一章圖數(shù)學(xué)與軟件科學(xué)數(shù)學(xué)與軟件科學(xué)學(xué)院第1章圖1.1從哥尼斯堡七橋問題談起哥尼斯堡七橋問題四色問題哈密頓周游世界問題渡河問題數(shù)學(xué)與軟件科學(xué)學(xué)院第1章圖哥尼斯堡七橋問題Konigsberg城中有一條名叫Pregel的河流橫經(jīng)其中，河上有兩個小島，有七座橋把兩個島與河岸聯(lián)系起來．有人提出一個問題：怎樣才能一次走過所有七座橋，每座橋只能經(jīng)過一次而且起點(diǎn)與終點(diǎn)必須是同一地點(diǎn)？數(shù)學(xué)與軟件科學(xué)學(xué)院第1章圖四色問題1852年，畢業(yè)于倫敦大學(xué)的FrancisGuthrie來到一家科研單位搞地圖著色工作時，發(fā)現(xiàn)了一種有趣的現(xiàn)象：“看來，每幅地圖都可以用四種顏色著色，使得有共同邊界的國家都被著上不同的顏色．”這個現(xiàn)象能不能從數(shù)學(xué)上加以嚴(yán)格證明呢？格思里把這個猜想告訴了正在念大學(xué)的弟弟．弟弟認(rèn)真思考了這個問題，結(jié)果既不能證明，也沒有找到反例，于是向自己的老師、著名數(shù)學(xué)家DeMorgan請教．德·摩根解釋不清，當(dāng)天就寫信告訴自己的同行、天才的Hamilton．與德摩根的熱情相反，哈密爾頓對這個問題絲毫不感興趣．他在三天后的回信中告訴德摩根，他“不會嘗試解決這個四元顏色問題”數(shù)學(xué)與軟件科學(xué)學(xué)院第1章圖四色問題的一個實(shí)例用四種顏色替中國大陸分省地圖染色數(shù)學(xué)與軟件科學(xué)學(xué)院第1章圖問題的證明一波三折1872年，英國當(dāng)時最著名的數(shù)學(xué)家Cayley正式向倫敦?cái)?shù)學(xué)學(xué)會提出了這個問題，于是四色猜想成了世界數(shù)學(xué)界關(guān)注的問題．1878～1880年兩年間，著名的律師兼數(shù)學(xué)家肯普AlfredKempe和PeterGuthrieTait兩人分別提交了證明四色猜想的論文，宣布證明了四色定理，大家都認(rèn)為四色猜想從此也就解決了．1890年，在牛津大學(xué)就讀的年僅29歲的Heawood以自己的精確計(jì)算指出了肯普在證明上的漏洞．他指出肯普說沒有極小五色地圖能有一國具有五個鄰國的理由有破綻．不久，泰勒的證明也被人們否定了．人們發(fā)現(xiàn)他們實(shí)際上證明了一個較弱的命題——五色定理．?dāng)?shù)學(xué)與軟件科學(xué)學(xué)院第1章圖令閔可夫斯基尷尬的一堂課一天，HermannMinkowski剛走進(jìn)教室，一名學(xué)生就遞給他一張紙條，上面寫著：“如果把地圖上有共同邊界的國家涂成不同顏色，那么只需要四種顏色就足夠了，您能解釋其中的道理嗎？”閔可夫斯基微微一笑，對學(xué)生們說：“這個問題叫四色問題，是一個著名的數(shù)學(xué)難題．其實(shí)，它之所以一直沒有得到解決，僅僅是由于沒有第一流的數(shù)學(xué)家來解決它．”為證明紙條上寫的不是一道大餐，只是小菜一碟，閔可夫斯基決定當(dāng)堂掌勺，問題就會變成定理……下課鈴響了，可“菜”還是生的．一連好幾天，他都掛了黑板．后來有一天，閔可夫斯基走進(jìn)教室時，忽然雷聲大作，他借此自嘲道：“哎，上帝在責(zé)備我狂妄自大呢，我解決不了這個問題．”數(shù)學(xué)與軟件科學(xué)學(xué)院第1章圖計(jì)算機(jī)幫助人們圓夢1976年WolfgangHaken與KennethAppel在伊利諾伊大學(xué)的IBM360機(jī)上分1482種情況檢查，歷時1200個小時，作了100億個判斷，最終證明了四色定理．四色定理是第一個主要由電腦證明的理論，這一證明并不被所有的數(shù)學(xué)家接受，因?yàn)椴捎玫姆椒ú荒苡扇斯ぶ苯域?yàn)證．最終，人們必須對電腦編譯的正確性以及運(yùn)行這一程序的硬件設(shè)備充分信任．不少數(shù)學(xué)家并不滿足于計(jì)算機(jī)取得的成就，他們認(rèn)為應(yīng)該有一種簡捷明快的書面證明方法．直到現(xiàn)在，仍有不少數(shù)學(xué)家和數(shù)學(xué)愛好者在尋找更簡潔的證明方法．?dāng)?shù)學(xué)與軟件科學(xué)學(xué)院第1章圖哈密頓周游世界問題1859年，英國數(shù)學(xué)家兼物理學(xué)家哈密頓提出以下周游世界問題：用一個正十二面體的二十個頂點(diǎn)表示二十個城市，怎樣才能從一個城市出發(fā)，沿著棱經(jīng)過每個城市恰好一次，最后返回到出發(fā)點(diǎn)？數(shù)學(xué)與軟件科學(xué)學(xué)院第1章圖渡河問題河岸上有一只狼，一頭羊，一筐菜，擺渡人要把他們送過河去，由于船太小，每次只能載一樣?xùn)|西，顯然狼和羊，羊和菜不能在無人監(jiān)視情況下留在一起，問擺渡人將如何把它們送過河去？數(shù)學(xué)與軟件科學(xué)學(xué)院第1章圖渡河問題的數(shù)學(xué)化描述渡河問題就歸結(jié)為下述問題了：“在圖G中找一條連接頂點(diǎn)MWSV與φ，并且包含邊數(shù)最少的路”．如果我們設(shè)G的每條邊的長度都是1，那末也可以把渡河問題歸結(jié)為：“找一條連接MWSV與的最短路”．?dāng)?shù)學(xué)與軟件科學(xué)學(xué)院第1章圖1.2圖的基本概念圖的定義一個示例相關(guān)術(shù)語握手定理同構(gòu)定義邊圖定義數(shù)學(xué)與軟件科學(xué)學(xué)院第1章圖圖的定義把數(shù)學(xué)結(jié)構(gòu)G＝{V(G)，E(G)，ΨG}稱為一個圖，其中V(G)是非空集合，ΨG是E(G)到{(a,b)|a,b∈V(G)}的一個映射，則稱G是一個以V(G)為頂集合、以E(G)為邊集合的有向圖．V(G)中的元素稱為頂點(diǎn)，E(G)中的元素稱為邊，ΨG稱為關(guān)聯(lián)函數(shù)．V(G)所含元素的個數(shù)即頂點(diǎn)個數(shù)稱為圖的階，用|V(G)|表示．E(G)所含元素的個數(shù)稱為G的邊數(shù)，用|E(G)|表示．我們用G(p，q)表示一個階為p、邊數(shù)為q的圖G，這時也說G是一個(p，q)圖．?dāng)?shù)學(xué)與軟件科學(xué)學(xué)院第1章圖一個示例——例1.1V(G)={v1,v2,v3,v4,v5}，E(G)={e1,e2,e3,e4,e5,e6,e7,e8}ΨG定義如下：ΨG(e1)=v1v2，ΨG(e2)=v2v3，ΨG(e3)=v3v3，ΨG(e4)=v3v4，ΨG(e5)=v2v4，ΨG(e6)=v4v5，ΨG(e7)=v2v5，ΨG(e6)=v5v2，數(shù)學(xué)與軟件科學(xué)學(xué)院第1章圖圖的相關(guān)術(shù)語（1）e=uv時，稱e與u、v相關(guān)聯(lián)同一條邊的兩個端點(diǎn)與同一個頂相關(guān)聯(lián)的兩條邊只與一個頂相關(guān)聯(lián)的邊ΨG(e1)=ΨG(e2)=uv邊與頂相關(guān)聯(lián)鄰頂鄰邊環(huán)重邊e=uv時，稱頂u與v是邊e的端點(diǎn)邊的端點(diǎn)數(shù)學(xué)與軟件科學(xué)學(xué)院第1章圖圖的相關(guān)術(shù)語（2）任二頂皆相鄰的圖，記為KnX中以及Y中任二頂不相鄰K1,n當(dāng)且僅當(dāng)兩頂不在同一Vi中，二頂相鄰記成d(v)，d(v)=d1(v)+2l(v)完全圖二分圖星完全r分圖頂v的次數(shù)無環(huán)無重邊的圖單圖數(shù)學(xué)與軟件科學(xué)學(xué)院第1章圖完全圖、二分圖、星、完全三分圖數(shù)學(xué)與軟件科學(xué)學(xué)院第1章圖k次正則圖我們把d(v)≡k的圖叫做k次正則圖．?dāng)?shù)學(xué)與軟件科學(xué)學(xué)院第1章圖握手定理定理1.1(Euler,1736)推論圖中奇次頂總數(shù)是偶數(shù)．

證令V(G)＝Ve∪Vo，其中Ve是偶次頂集合，Vo是奇次頂集合，由定理1.1有而是偶數(shù)，故亦為偶數(shù)，但Vo中的次數(shù)d(v)是奇數(shù)，故|Vo

|必為偶數(shù)．?dāng)?shù)學(xué)與軟件科學(xué)學(xué)院第1章圖握手定理的應(yīng)用舉例（1）例1.2晚會上大家握手言歡，試證握過奇次手的人數(shù)是偶數(shù)．例1.3空間中不可能有這樣的多面體存在，它的面數(shù)是奇數(shù)，而且每個面是奇數(shù)條線段圍成的．例1.4碳?xì)浠衔镏袣湓觽€數(shù)是偶數(shù)．?dāng)?shù)學(xué)與軟件科學(xué)學(xué)院第1章圖握手定理的應(yīng)用舉例（2）例1.5大于7公斤的重量都可以僅用一些3公斤和5公斤的兩條砝碼來稱量．證只需證明對任意給定的自然數(shù)n≥8，存在二分圖G(n)，其X頂子集有n個頂點(diǎn)，每頂皆一次，Y頂子集中的頂是3次或5次的．下面用數(shù)學(xué)歸納法證明．當(dāng)n=8時，結(jié)論顯然成立．假設(shè)對于G(k)，結(jié)論已成立．在G(k)的X頂子集中添加一項(xiàng)xk+1；由歸納假設(shè)知，在G(k)的Y中頂是3次或5次的．(i)若Y中皆3次頂，取y1、y2、y3，將其重合成一個頂y123，再于y123與xk+1之間連一條邊，最后把y123劈開成兩個5次頂，則得滿足要求的G(k+1)．(ii)若Y中有5次頂，設(shè)d(yi)=5，在yi與xk+1之間連一邊，再把yi劈開成兩個3次頂，則得滿足要求的二分圖G(k+1)．?dāng)?shù)學(xué)與軟件科學(xué)學(xué)院第1章圖同構(gòu)定義1.2G與H是兩個圖，存在可逆映射θ:V(G)→V(H)；φ:E(G)→E(H)，使得當(dāng)且僅當(dāng)ΨH(φ(e))=θ(u)θ(v)時，ΨG(e)=uv，則說這兩個圖同構(gòu)，記為G≌H．?dāng)?shù)學(xué)與軟件科學(xué)學(xué)院第1章圖Ulam猜想U(xiǎn)lam猜想(1929)：G與H是兩個圖，|V(G)|＝|V(H)|，V(G)={v1,v2,…,vn},V(H)={u1,u2,…un}，且G-vi≌H-ui(i=1,2,…,n)，則G≌H．?dāng)?shù)學(xué)與軟件科學(xué)學(xué)院第1章圖邊圖定義1.3設(shè)G是一個圖，L(G)是另一個圖，滿足V(L(G))=E(G)，L(G)中兩頂相鄰當(dāng)且僅當(dāng)它們是G中的兩條相鄰的邊，則稱L(G)是G的邊圖．?dāng)?shù)學(xué)與軟件科學(xué)學(xué)院第1章圖邊圖的性質(zhì)若uv∈E(G)，則在L(G)中uv對應(yīng)的頂?shù)拇螖?shù)是d(u)+d(v)-2，其中d(u)與d(v)是頂u、v在G中的次數(shù)．若任兩圖G1≌G2，則L(G1)≌L(G2)．G≌L(G)當(dāng)且僅當(dāng)G是一個多邊形．?dāng)?shù)學(xué)與軟件科學(xué)學(xué)院第1章圖1.3軌道與圈軌道與圈子圖概念定理1-2相關(guān)例題數(shù)學(xué)與軟件科學(xué)學(xué)院第1章圖道路、軌道、回路、圈、連通定義1.4在頂邊交錯鏈w=v0e1v1e2v2…ekvk中，vi是頂點(diǎn)，ei是邊，對于1≤i≤n，ei=vi-1vi，則稱W是圖G的一條道路，其中允許vi=vj或ei=ej．v0和vk分別稱為W的起點(diǎn)和終點(diǎn)，而v1,v2,…,vk-1稱為W的內(nèi)點(diǎn)，整數(shù)k稱為路長．各邊相異的道路稱為行跡，各頂相異的道路稱為軌道，記成P(v0,vk)．起點(diǎn)與終點(diǎn)重合的道路稱為回路；起點(diǎn)與終點(diǎn)重合的軌道叫做圈，長k的圈稱為k階圈；u、v兩頂?shù)木嚯x是指u與v為起止點(diǎn)的最短軌道之長度，記成d(u,v)．若存在道路以u、v為起止頂，則稱u與v在圖G中連通，G中任二頂皆連通時，稱G為連通圖．?dāng)?shù)學(xué)與軟件科學(xué)學(xué)院第1章圖子圖、導(dǎo)出子圖、連通片定義1.5設(shè)S和G是兩個圖，如果并且，那么S是G的子圖，記成；若，但S與G不同構(gòu)，則稱S是G的真子圖，記成；若，且，則稱S是G的生成子圖；若，且，E(S)是由兩端皆在中邊構(gòu)成，則稱S是由導(dǎo)出的G的導(dǎo)出子圖，記成；若，且，V(S)是中邊的端點(diǎn)組成的集合，則稱S是由導(dǎo)出的G的邊導(dǎo)出子圖．若，當(dāng)且僅當(dāng)二頂同在子集Vi時，二頂連通，則稱是G的個連通片．?dāng)?shù)學(xué)與軟件科學(xué)學(xué)院第1章圖子圖示例GG的一個生成子圖G[{3,4,6}]G[{a,c,e,g,h}]數(shù)學(xué)與軟件科學(xué)學(xué)院第1章圖例1.6例1.6有2k部電話交換臺，每臺至少與k個臺有直通線路，證明任兩臺之間可以通話．證把交換臺作為一個圖G的頂，僅當(dāng)兩臺之間有直通線路時，在相應(yīng)的兩頂間連一條邊，于是圖G有2k個頂，每頂次數(shù)至少為k，下面證明G是連通圖．設(shè)G不連通，則存在連通片G1，|V(G1)|≤k，在G1上，次數(shù)最大的頂?shù)拇螖?shù)不超過k-1，與G中每頂次數(shù)至少為k相矛盾，故G連通．證畢．?dāng)?shù)學(xué)與軟件科學(xué)學(xué)院第1章圖例1.7例1.7在僅兩個奇次頂?shù)膱D中，此二奇次頂連通．證如果圖G中恰有兩個奇次頂u、v，但在G中這兩個奇次頂u、v不連通，則存在G的兩個連通片G1與G2，使得u∈V(G1)，v∈V(G2)．對于連通圖G1與G2而言，皆有1個奇次頂，與推論1.1相矛盾．證畢．?dāng)?shù)學(xué)與軟件科學(xué)學(xué)院第1章圖定理1.2定理1.2圖G是二分圖當(dāng)且僅當(dāng)G中無奇圈．證不妨設(shè)G是連通圖，不然分別討論它的每個連通片．若G是二分圖，但G中無圈，自然無奇圈．若G中有圈C=v1v2…vkv1，不妨設(shè)v1∈X，則v1,v3,…,v1在X集合中，v2,v4,…,vk在Y集合中，其中X∪Y=V(G)，由此可知k是偶數(shù)，即C是偶圈，故G中無奇圈．若G中無奇圈，下面證G是二分圖．為此在G上任指定一個頂v0，把V(G)劃分成V(G)=X∪Y，其中X={w|w∈V(G),d(v0,w)是偶數(shù)}，Y=V(G)-X．下面證明這是G的一個二分劃．?dāng)?shù)學(xué)與軟件科學(xué)學(xué)院第1章圖定理1.2（續(xù)）任取u,v∈X，設(shè)P

(v0,u)是從v0到u的最短軌，Q(v0,v)是從v0到v的最短軌，u1是P和Q的最后一個公共頂點(diǎn)，因?yàn)镻和Q是最短通路，P和Q的(v0,u1)-節(jié)也是從v0,到u1的最短軌，因此具有相同的長度．又因P和Q的長度是偶數(shù)，所以P上(u1,u)-節(jié)P1的長度與Q上(u1,v)-節(jié)Q1的長度具有相同的奇偶性．若u與v鄰接，則P1∪Q1∪uv圍成一個奇圈，此與假設(shè)矛盾，故X中任意兩點(diǎn)均不鄰接，同理Y中任意兩個頂點(diǎn)也不鄰接，因此G是二分圖．證畢．?dāng)?shù)學(xué)與軟件科學(xué)學(xué)院第1章圖例1.8例1.8一只老鼠在3×3×3的立方體蛋糕塊上吃出一個洞，這個洞通過1×1×1的每個小立方體蛋糕的中心，它從大立方體的一角咬起，只要還有未被它嘗過的1×1×1的小點(diǎn)心塊，就繼續(xù)向前咬．問這只老鼠能否在3×3×3的立方體中心停止？假設(shè)這只老鼠是從一個1×1×1的小立體中心沿與側(cè)面垂直的方向向未咬過的小點(diǎn)心塊咬過去．?dāng)?shù)學(xué)與軟件科學(xué)學(xué)院第1章圖例1.9例1.9無零次與1次頂?shù)膯螆D中有圈．證由于此圖G中無零次與1次頂，所以對于每個頂v，d(v)≥2，且存在一條最長軌P(u0,v0)，u0與v0還各有一條不在P(u0,v0)上的邊與之關(guān)聯(lián)，這種邊的另一端必在P(u0,v0)上，不然P(u0,v0)還可以加長，與P(u0,v0)最長相矛盾；于是造成如圖所示的情形．從而G中有圈．?dāng)?shù)學(xué)與軟件科學(xué)學(xué)院第1章圖例1.10例1.10若G是連通圖，，|V(H)|≤|V(G)|，則G中有不屬于H的邊e，e的一端屬于V(H)，另一端不屬于V(H)．證因G是連通圖，又|V(H)|≤|V(G)|，則可以找到，v∈V(H)，存在軌P(u,v)．從u出發(fā)沿P(u,v)前進(jìn)，遇到H中第一頂w為止，則P(u,v)上的一段P(u,w)的最后一條邊即為題中所稱的邊e．證畢．?dāng)?shù)學(xué)與軟件科學(xué)學(xué)院第1章圖例1.11例1.11G是單圖，每頂次數(shù)不小于3，則G中有偶圈．證設(shè)v0v1v2…vm是G中最長軌，由于d(v0)≥3，由“最長軌方法”，存在vi≠vj，1<i<j≤m，vi與vj皆與v0相鄰，如圖．若i與j中有奇數(shù)，例如，i是奇數(shù)，則由v0v1v2…vi與邊v0vi合成一個偶圈，其長為i+1；若i與j皆為偶數(shù)，則由vivi+1…vj與邊v0vi,v0vj合成一個偶圈，其長為j-i+2．證畢．?dāng)?shù)學(xué)與軟件科學(xué)學(xué)院第1章圖例1.12例1.12若G是單圖，每頂次數(shù)不小于3，則G中各圈長的最大公約數(shù)是1或2．證只需證G中各圈長無大于2的公因數(shù)．由例1.11，G中有長i+1，j+1和j-i+2的圈．若i+1，j+1，j-i+2有公因數(shù)k>2，則k可除盡(j+1)-(i+1)=j-i(j>i)，于是k能除盡(j-i+2)-(j-i)=2，與k>2相矛盾．證畢．?dāng)?shù)學(xué)與軟件科學(xué)學(xué)院第1章圖周長、圍長、直徑、中心、半徑定義1.6單圖G最長的圈之長稱為該圖的周長；最短的圈之長稱為該圖的圍長；兩頂點(diǎn)距離中的最大值稱為直徑，記成d(G)，即d(G)=max{d(u,v)|u,v∈V(G)}；圖G的中心是指使的頂u；稱為G的半徑．?dāng)?shù)學(xué)與軟件科學(xué)學(xué)院第1章圖

補(bǔ)圖定義1.7單圖G的補(bǔ)圖記成GC，GC是這樣一個圖，V(GC)=V(G)當(dāng)且僅當(dāng)在G中兩頂不相鄰時，該二頂在GC中相鄰．?dāng)?shù)學(xué)與軟件科學(xué)學(xué)院第1章圖例1.13例1.13單圖G與其補(bǔ)圖不能都不連通．證由于G與GC的相補(bǔ)性，下面設(shè)G不連通時，證明GC是連通的．設(shè)G1，G2，…，Gω是G的連通片，ω>1，任取G的兩個頂u、v，若u,v∈G(Vi)，設(shè)w是不在Gi上的頂．由于ω>1，所以w是存在的．于是uw，vw∈E(GC)，即在GC中u與v連通．若u、v分居于G的兩個連通片Gk、Gl，則uv∈E(GC)，即u與v在GC中連通，由u與v的任意性，知GC是連通圖．證畢．?dāng)?shù)學(xué)與軟件科學(xué)學(xué)院第1章圖例1.14例1.14棱長為n（自然數(shù)）的立方體被與它的側(cè)面平行的平面切成n3個單位立方體，其中有多少對公共頂點(diǎn)不多于2的單位立方體？解以單位立方體為頂，僅當(dāng)二單位立方體有公共側(cè)面時，在此二頂間加一邊，構(gòu)成一個圖G，GC的邊數(shù)即為所求．G的邊數(shù)為3n2(n-1)．而

的邊數(shù)是．故GC的邊數(shù)是．?dāng)?shù)學(xué)與軟件科學(xué)學(xué)院第1章圖1.5求最短軌長度的算法最短軌長建模Dijkstra算法數(shù)學(xué)與軟件科學(xué)學(xué)院第1章圖最短軌長度的圖論模型若干城市被鐵路網(wǎng)連通，任意指定其中甲乙兩座城市，試求出從甲到乙最近的鐵路路線．把這些城市設(shè)為頂點(diǎn)，僅當(dāng)兩城間有一段鐵路，而這段鐵路中途無其他火車站，則在相應(yīng)二頂間連一邊，對每條邊一個權(quán)重w(e)表示e的長度，得加權(quán)連通圖G．設(shè)P(u,v)是G中以u,v為端點(diǎn)的軌集合，用W(P(u,v))表示軌P(u,v)上邊權(quán)之和．目標(biāo)是求P(u,v)中的一條軌道P0(u,v)，使得且把稱為頂點(diǎn)u與v的距離，記成d(u,v)．?dāng)?shù)學(xué)與軟件科學(xué)學(xué)院第1章圖Dijkstra算法關(guān)于求最短通路問題，Dijkstra算法(1959)是最有名的方法之一，它的基本思想是：把G的頂點(diǎn)分為S，T兩類，若u0到某個頂點(diǎn)x的最短通路已求出，則將x歸入S，其余點(diǎn)歸入T，開始