數(shù)模-圖論及其算法-資料下載頁(yè)
2025-10-09 15:45本頁(yè)面
【正文】 匹配算法 給定圖 G的一個(gè)匹配 M。 （ 1）找出關(guān)于 M的交替鏈 P1； （ 2）刪去 P1中 M的邊，添加 P1中不屬于 M的邊，形成新集合 M1，它是圖 G的匹配； （ 3）重復(fù)這一過(guò)程直至沒(méi)有關(guān)于 M的交替鏈，便可獲得最大匹配。 十三、平面圖 1. 平面圖 平面圖的定義： 給定無(wú)向圖 G=V,E，如果能把它圖示在一個(gè)平面上，使得邊只與頂點(diǎn)相交，則稱(chēng)此圖為 平面圖 。 注意： 1）將平面圖“圖示在平面上”，也可說(shuō)成“把平面圖嵌入一個(gè)平面上”。 2）平面圖將平面分成了獨(dú)立的面，面的邊界為圖的邊組成。如果面的面積有限，該面稱(chēng)為 有限面 ，否則，稱(chēng)為 無(wú)限面 。無(wú)限面唯一。 Euler公式： 給定平面圖 G=V,E， |V|=n， |E|=m。設(shè)平面圖的面有 k個(gè)，則有 nm+k=2。 定理 10 給定任意簡(jiǎn)單平面圖 (n,m)（ n4）都有 推論 101 K5是非平面圖。 定理 11 每個(gè)面用四條邊或更多邊圍成的任何連通平面圖都有 推論 111 K3,3不是平面圖。 63 ?? nmmn ?? 422. 對(duì)偶圖 給定平面圖 G=V,E，構(gòu)造一個(gè)新圖 G*=V*,E*如下： V*是圖 G的面數(shù)，如果 G的兩個(gè)面（對(duì)應(yīng) G*的兩個(gè)頂點(diǎn)）有公共邊，則將 G*的這兩個(gè)頂點(diǎn)相連形成一個(gè)邊。這樣形成的圖 G*稱(chēng)為圖 G的對(duì)偶圖。 定義 無(wú)向圖 G的頂點(diǎn)子集 S稱(chēng)為圖的 割集 ，當(dāng)且僅當(dāng)，刪去 S中的所有邊時(shí)， G的連通分圖個(gè)數(shù)將增加，而刪去任何 S的真子集都不會(huì)增加 G的連通分圖個(gè)數(shù)．尤其是， |S|=1時(shí)，我們稱(chēng)這條邊為 G的 橋邊． 3. 五色問(wèn)題 對(duì)圖中每個(gè)頂點(diǎn)著色，如果任何兩相鄰頂點(diǎn)的顏色都不相同，則稱(chēng)這種著色為圖的 正常著色 ． 四色猜想（定理） 用四種顏色可以給任何簡(jiǎn)單平面圖正常著色。 十四、圖論小結(jié) 一、圖的主要概念 ：無(wú)環(huán)、無(wú)向、無(wú)平行邊、連通的圖； （有向圖）：圖中每條邊都賦有實(shí)數(shù)權(quán)； ：圖中各結(jié)點(diǎn)次數(shù)相同， k正則圖 — 圖中各結(jié)點(diǎn)次數(shù)都為 k； ：給定圖 G=V,E，如果 G0=V0,E0滿足 V0?V， E0? E，則稱(chēng)圖 G0是圖 G的子圖。尤其是，如果 V0=V，則稱(chēng)圖 G0是圖 G的生成子圖 ；如果子圖 G0中沒(méi)有孤立結(jié)點(diǎn)， G0由 E0唯一決定，則稱(chēng) G0由邊集 E0導(dǎo)出的子圖；如果任意兩結(jié)點(diǎn) u,v? V0 ,都有 [u,v] ? E0 ，則稱(chēng) G0由頂點(diǎn)集 V0 導(dǎo)出的子圖； （有向）圖：圖中任意兩頂點(diǎn)之間都有邊（相反方向的兩條邊）相連； ：具有 Euler回路的圖； ：具有 Hamilton圈的圖； G=V,E的逆圖 G1=V,E1：圖 G=V,E的鄰接矩陣 A的轉(zhuǎn)置矩陣 AT對(duì)應(yīng)的圖； ：將圖的頂點(diǎn)集分成兩部分 X和 Y，且它們中的任意兩點(diǎn)都不相鄰，記為G=X,E,Y； ：一個(gè)圖能夠嵌入到平面上，滿足邊與邊之間除頂點(diǎn)以外沒(méi)有交點(diǎn)。 ：將平面圖的不同面作為頂點(diǎn)，具有公共邊的面相連作為邊，由此形成的圖稱(chēng)為原圖的對(duì)偶圖。 ：沒(méi)有回路的連通圖； ：除根（引入次數(shù)為 0）以外的結(jié)點(diǎn)的引入次數(shù)恒為 1的有向樹(shù)圖。 二、實(shí)用的圖論術(shù)語(yǔ) V0 ：圖 G=V,E的頂點(diǎn)子集 V0，如果不在 V0中的點(diǎn)至少與該集的一個(gè)頂點(diǎn)相鄰；如果一個(gè)支配集的任何真子集都不是支配集，則稱(chēng)為最小支配集； ：無(wú)向圖的頂點(diǎn)子集稱(chēng)為獨(dú)立集，如果該集中任何兩點(diǎn)都不相鄰接； ：沒(méi)有重復(fù)邊的路徑； （鏈）：沒(méi)有重復(fù)點(diǎn)的路徑； ：圖中兩頂點(diǎn)的距離定義為兩點(diǎn)之間的最短路徑長(zhǎng)度； （回路）：通過(guò)圖中每條邊一次且僅一次的路徑（回路）； （圈）：通過(guò)圖中每個(gè)頂點(diǎn)一次且僅一次的路徑（回路）； ：圖中頂點(diǎn)對(duì)距離的最大值； G=X,E,Y的匹配：沒(méi)有公共端點(diǎn)的圖的邊集的子集；邊數(shù)最多的匹配稱(chēng)為圖的最大匹配； ：破壞圖的連通性的最大邊子集； ：給圖的頂點(diǎn)染色，如果圖中任意相鄰兩點(diǎn)的顏色不同，則稱(chēng)為正常著色； （支撐樹(shù)）：圖的生成子圖是樹(shù)，稱(chēng)為支撐樹(shù)； ：賦權(quán)圖中權(quán)最小的生成樹(shù)。 三、圖的算法 1. Dijkstra算法 — 最短路算法； 2. 最鄰近算法（巡回售貨員問(wèn)題 — Hamilton圈）； （交替鏈）； （增加、刪去邊算法）； ； 。 四、圖論研究課題 ； ； ； ； 。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1