圖論的基本算法(已修改)
2024-10-17 15:10 本頁(yè)面
【正文】 圖論 朱全民 圖 ? 圖的概念 G=(V,E) ? 圖的基本概念 ? 有向圖、頂點(diǎn)、入度、出度、弧、環(huán) ? 無向圖、邊、路徑、頂點(diǎn)的度、鄰接 ? 簡(jiǎn)單圖、完全圖 ? 平面圖、二分圖 圖的存儲(chǔ)結(jié)構(gòu) ? 鄰接矩陣 graph=Record vex:array[1..vtxptr] of vertex。 arc:array[vtxptr, vtxptr] of vertex。 ? 鄰接表 表節(jié)點(diǎn) type arcptr=^arode。 arode=record adjvex:vtxptr。 nextarc:arcptr。 info: … { 和弧有關(guān)的其他信息 } end。 vex=Record vexdata: …{ 和頂點(diǎn)有關(guān)的其他信息 } firstarc:arcptr。 end。 adjlist=array [vtxptr] of vexnode。 拓?fù)渑判? ? 網(wǎng)線從機(jī)房連接到辦公室 ? 在機(jī)房，所有網(wǎng)線從左到右編號(hào)為 1,2,3,…, N ? 給出每?jī)蓷l線是否交叉的信息，請(qǐng)計(jì)算辦公室內(nèi)從左到右各條線的編號(hào) ( a ) (b ) ? FUNC toporder(var dig:adjlisttp):boolean。 ? init(top2)。 m:=0。 ve[1..n]:=0 ? while Not empty(top1) do ? [ j:=pop(top1)。 push(top2,j)。 m:=m+1。 ? k:=firstadj(dig,j)。 ? while k0 do ? [ 入度 (k):=入度 (k)1。 ? if 入度 (k)=0 then push(top1,k)。 ? if ve[j]+dut(j,k)ve[k] then ve[k]:=ve[j]+dut(j,k)。 ? k:=nextadj(dig,j,k) ? ] ? ] ? if mn then return(false) else return(true)。 ? endF。 求拓?fù)湫蛄? 拓?fù)渑判? ? 核心問題：給一些序關(guān)系，排出全序！ ?一個(gè)一個(gè)排 ?先排最大 ?然后第二大 … ?具體實(shí)現(xiàn)？ ? 每次取 0出度點(diǎn) ? 枚舉所有點(diǎn)嗎？ ? 0出度只可能是 1出度變來的！ ? O(n+m) 歐拉道路和回路 ? 經(jīng)過每條邊一次且僅一次 ? 先看回路 ?必要條件：所有點(diǎn)度為偶數(shù) ?充分條件：還是“所有點(diǎn)度為偶數(shù)” ? 證明！ ? 把歐拉回路構(gòu)造出來 ? “圈套圈” ? 可能套不出來嗎？想一想 歐拉道路和回路 ? 有向的情形 ?入度 = 出度 ?如何套圈？ ? 道路 ?有兩個(gè)奇度點(diǎn) ?正好是起點(diǎn)和終點(diǎn) ? 哪個(gè)是起點(diǎn)，哪個(gè)是終點(diǎn)？ ? 有向 +無向怎么辦？ ?網(wǎng)絡(luò)流！不要求掌握 怎樣找歐拉回路 ? 幼兒園里有很多房屋 ?房屋與房屋之間連以走廊 ?走廊與房屋之間有一扇門 ?幼兒園長(zhǎng)想把門漆成綠色或者黃色，使得 ? 任意一條走廊兩頭門的顏色不同 ? 任意一間房屋上的門，綠色門的數(shù)量與黃色門的數(shù)量相差不超過 1。 ? 如何實(shí)現(xiàn)？ 分析 ? 如果每個(gè)房屋的門為偶數(shù)，那么幼兒園本身就是個(gè)歐拉回路。 ? 那么，如果從房屋踏上走廊，門被漆成綠色；從走廊踏進(jìn)房屋，門被漆成黃色。由于走廊只走一次，因此，每間房屋進(jìn)出的次數(shù)一樣，因此，任意一間房屋的門，綠色門和黃色門的數(shù)量一樣。 ? 如果門的數(shù)量為奇數(shù)，那么要對(duì)幼兒園門進(jìn)行改造，要使得門數(shù)量為奇數(shù)的房屋為偶數(shù)個(gè)，將這樣的房屋兩兩配對(duì)，并在新增加的門之間虛設(shè)一條走廊，這樣幼兒園就成為了歐拉回路。 ? 然后按規(guī)律給門油漆，然后撤去所有虛設(shè)的走廊和門，由于被撤去的房屋的門最多只有一個(gè)，所以同樣保證綠色門的數(shù)量和黃色的門的數(shù)量相差不超過 1。 另一個(gè)例子 ? 考古學(xué)家發(fā)現(xiàn)了一塊布，布上做有針線活，叫做“十字繡” ? 交替地在布的兩面穿線 ? 布是一個(gè) n m的網(wǎng)格 ? 線只能在網(wǎng)格的頂點(diǎn)處才能從布的一面穿到另一面。 ? 每一段線都覆蓋一個(gè)單位網(wǎng)格的兩條對(duì)角線之一 ? 而在繡的過程中，一針中連續(xù)的兩段線必須分處布的兩面 ? 給出布兩面的圖案（實(shí)線代表有線，虛線代表背面有線） ? 最少需要幾針才能繡出來？ ? 一針是指針不離開布的一次繡花過程。 ? 例如圖 (b)的圖案最少需要 4針。 分析 ? 抽象成圖 ?網(wǎng)格交叉點(diǎn)：頂點(diǎn) ?正面的線：正邊 ?背面的線：負(fù)邊 ?有邊相連：連通塊 ? 每個(gè)連通塊分別求 ?對(duì)于某個(gè)頂點(diǎn) i ? |正邊數(shù) 負(fù)邊數(shù) |=K0時(shí) ? 以
外語(yǔ)相關(guān)推薦
鄂ICP備17016276號(hào)-1