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