算法合集之平面圖在信息學(xué)中的應(yīng)用(已修改)
2025-10-23 20:30 本頁(yè)面
【正文】 平面圖在信息學(xué)中的應(yīng)用 海南省海南中學(xué) 劉才良 引言 ?平面圖是圖論中一類(lèi)重要的圖，在實(shí)際生產(chǎn)中應(yīng)用非常廣泛。比如集成電路的設(shè)計(jì)就用到平面圖理論。在信息學(xué)中，雖然有關(guān)平面圖的題目并不多見(jiàn)，但對(duì)于某些題目，如果通過(guò)建模轉(zhuǎn)化，應(yīng)用平面圖的性質(zhì)，將大大提高算法的效率。因此，掌握一些平面圖理論會(huì)對(duì)我們有很大的幫助。 相關(guān)定義、定理及推論 ? 平面圖 – 一個(gè)無(wú)向圖 G=V， E，如果能把它畫(huà)在平面上，且除 V中的節(jié)點(diǎn)外，任意兩條邊均不相交，則稱(chēng)該圖 G為平面圖。 例如：圖 (a)經(jīng)變動(dòng)后成為 (b)，故圖 (a)為平面圖。而圖 (c)無(wú)論如何變動(dòng)，總出現(xiàn)邊相交，圖 (c)為非平面圖。 (a) (b) (c) 相關(guān)定義、定理及推論 ? 面 – 設(shè) G為一平面圖，若由 G的一條或多條邊所界定的區(qū)域內(nèi)不含圖 G的節(jié)點(diǎn)和邊，這樣的區(qū)域稱(chēng)為 G的一個(gè)面，記為 f。包圍這個(gè)區(qū)域的各條邊所構(gòu)成的圈，稱(chēng)為該面 f的邊界，其圈的長(zhǎng)度，稱(chēng)為該面 f的度，記為 d(f)。為強(qiáng)調(diào)平面圖 G中含有面這個(gè)元素，把平面圖表示為 G=V， E， F，其中 F是 G中所有面的集合。 相關(guān)定義、定理及推論 ? 定理 1：若 G=V， E， F是連通平面圖，則 ∑f∈ Fd(f)=2|E|. ? 定理 2：若 G=V， E， F是連通平面圖，則 |V||E|+|F|=2. 證明： 首先假定 G是樹(shù)，則 |E|=|V|1， G只有一個(gè)無(wú)限面， 因此 |V||E|+|F|=|V|(|V|1)+1=2. 現(xiàn)在假設(shè) G不是樹(shù)，由于 G是連通的，故 G中至少存在一個(gè)基本圈 C，于是 G必有一個(gè)有限面 f，而 f的邊界是由基本圈 C及可能連同計(jì)算兩次的一些邊組成 .如果從 G中刪去基本圈 C上的一條邊后得到的平面圖 G1=V1， E1， F1，則 |V1|=|V|， |E1|=|E|1，|F1|=|F|1，故 |V1||E1|+|F1|=|V||E|+|F|，仿此做下去，最終得到 G的一棵生成樹(shù) T0=V0， E0， F0，于是 |V||E|+|F|=|V0||E0|+|F0|=2. 相關(guān)定義、定理及推論 ? 推論 1：給定連通簡(jiǎn)單平面圖 G=V， E， F， 若 |V|≥3，則 |E|≤3|V
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1