【正文】 中應(yīng)用廣泛。 本文首先闡述了平面圖、對(duì)偶圖和色數(shù)的相關(guān)概念和定理，然后分別探究了其實(shí)際應(yīng)用。 關(guān)鍵詞 ： 平 面圖，對(duì)偶圖，色數(shù)，應(yīng)用探究。接著中斷了 170 多年。 發(fā)現(xiàn)了平面圖判定準(zhǔn)則后，這方面的研究才開(kāi)始復(fù)蘇。如今，平面問(wèn)題的研究成果已經(jīng)在交通網(wǎng)絡(luò)和印刷線路的設(shè)計(jì)等方面得到應(yīng)用。平面圖的染色問(wèn)題是與四色問(wèn)題緊密相聯(lián) 的。如果對(duì)給定圖的全部邊都涂上顏色，使相鄰的邊有不同的顏色，問(wèn)至少需要幾種顏色？這個(gè)問(wèn)題叫做邊的著色問(wèn)題，邊的著色問(wèn)題可以轉(zhuǎn)化為點(diǎn)著色問(wèn)題。 2 相關(guān)概念和定理 圖的相關(guān)概念 定義 1 一個(gè)圖是一個(gè)三元組 ?? GGEGV ),(),( , 其中 ? ? ?? nvvvGV , 21 ?? 為有限非空結(jié)點(diǎn)集合 , iv 稱(chēng)為結(jié)點(diǎn) , ? ? ? ?meeGE ,1 ?? 為有限的邊集合 , ie 稱(chēng)為邊 , G是從邊集合 E 到結(jié)點(diǎn)對(duì)集合上的函數(shù) . 圖可簡(jiǎn)記為 : ??? EVG , . 定義 2 如果 E 中邊 ie 對(duì)應(yīng) V 中的結(jié)點(diǎn)對(duì)是無(wú)序的 ? ?vu, , 稱(chēng) ie 是無(wú)向邊 , 記? ?vuei ,? , 稱(chēng) u ,v 是 ie 的兩個(gè)端點(diǎn) . 如果 ie 與結(jié)點(diǎn)有序?qū)??? vu, 相對(duì)應(yīng) , 稱(chēng) ie 是有向邊 , 記 ??? vuei , , 稱(chēng) u 為 ie 的始點(diǎn) , v 為 ie 的終點(diǎn) . 定義 3 每條邊均為無(wú)向邊的圖稱(chēng)為無(wú)向圖 . 每條邊均為有向邊的圖稱(chēng)為有向圖 . 有些邊是無(wú)向邊 , 有些邊是有向邊的圖稱(chēng)為混合圖 . 定義 4 設(shè) ??? EVG , , ?????? EVG , 為兩個(gè)圖 (同時(shí)為無(wú)向圖或有向圖 ), 若 ２ VV?? 且 EE?? , 則稱(chēng) G? 為 G 的子圖 , G 為 G? 的母圖 , 記作 GG?? . 若 G? 是 G 的子圖 , 且 VV?? 或 EE?? , 則稱(chēng) G? 為 G 的真子圖 . 若 G? 是 G 的子圖 , 且VV?? , 則稱(chēng) G? 為 G 的生成子圖 . 定義 5 兩個(gè)圖 ??? 111 ,EVG 和 ??? 222 ,EVG , 如果它們的結(jié)點(diǎn)間存在一一對(duì)應(yīng)關(guān)系（雙射） , 而且這種對(duì)應(yīng)關(guān)系也反映在表示邊的結(jié)點(diǎn)對(duì)中 (如果是有向邊則對(duì)應(yīng)的結(jié)點(diǎn)對(duì)還保持相同的順序 ), 則稱(chēng)這兩圖是同構(gòu)的 , 記作 21 GG? . 特別申明 , 本文所涉及到的圖均指無(wú)向圖 . 平面圖的相關(guān)概念和定理 定義 1 設(shè)圖 ??? EVG , 是一個(gè)無(wú)向圖 , 如果能夠把 G 的所有結(jié)點(diǎn)和邊畫(huà)在平面上 , 且使得任何兩條邊除了端點(diǎn)外沒(méi)有其他的交點(diǎn) , 就稱(chēng) G 是一個(gè)平面圖 . 注意 : 有些圖從表面上看有幾條邊是相交的 , 但是改畫(huà)之后 , 仍然是平面圖 . A 1 D 1B 1 C1C 1D 1B 1A 1 圖 1 E 2D 2C 2B 2A 2E 2D 2C 2B 2A 2 圖 2 ３ C 3B3A 3D 3E 3F 3 圖 3 E 4D 4C 4B 4A 4 圖 4 定義 2 設(shè) G 是一個(gè)連通平面圖 , 由圖中的邊所包圍的區(qū)域 , 在區(qū)域內(nèi)既不包含圖的結(jié)點(diǎn) , 也不包含圖的邊 , 這樣的區(qū)域稱(chēng)為 G 的一個(gè)面 , 包圍該面的諸邊所構(gòu)成的回路稱(chēng)為這個(gè)面的邊界 . 面的邊界的回路長(zhǎng)度稱(chēng)作該面的次數(shù) , 記為??rdeg . 定義 3 路圖 , 即 每個(gè)點(diǎn)只與其相鄰的 2 個(gè)或 1 個(gè)點(diǎn)相連 ,首位不連的平面圖 , 如圖 5. 1?n 個(gè)頂點(diǎn) ,n 條邊的路圖用 nP 表示 . EDCBA 圖 5 定義 4 圈圖 , 即 首尾相連的路圖 ,如圖 6. n 個(gè)頂點(diǎn) ,n 條邊的圈圖用 nC 表示 . 圖 3 是非平面圖 圖 4 是非平面圖 ４ CBA CBA 圖 6 定義 5 輪圖 , 即 圈圖的中間還有一個(gè)點(diǎn) ,該點(diǎn)與圈上每個(gè)點(diǎn)有一條連線的平面圖 , 如圖 7. 1?n 個(gè)頂點(diǎn) , n2 條邊的輪圖用 nW 表示 . CBAO 圖 7 定義 6 完全圖 , 即每?jī)蓚€(gè)頂點(diǎn)之間都有一條邊相連的平面圖 , 如圖 8. n 個(gè)頂點(diǎn) , ? ?21?nn 條邊的完全圖用 nK 表示 . EDCBA 圖 8 定義 7 數(shù)圖 , 即 不包含圈的圖 , 如圖 9. A 4A 9A 5A 11A 3A 10A 8A 2A 7A 6A 1 圖 9 ５ 定理 1 （歐拉定理）設(shè)有一個(gè)連通的平面圖 G , 共有 v 個(gè)結(jié)點(diǎn) e 條邊和 r 個(gè)面 ,則歐拉公式 2??? rev 成立 . 定理 2 設(shè) G 是一個(gè)有 v 個(gè)結(jié)點(diǎn) e 條邊的連通簡(jiǎn)單平面圖 , 若 3?v , 則63 ?? ve . 推論 如果圖 ??? EVG , 是連通的簡(jiǎn)單平面圖 , 若 3?v , 且每個(gè)區(qū)域至少由四條邊圍成 , 則有 42 ?? ve . 對(duì)偶圖的相關(guān)概念 定義 1 給定平面圖 ??? EVG , , 它具有面 1F , 2F ,? , nF , 若有圖 ??? ??? EVG ,滿(mǎn)足下列條件 : (a) 對(duì)于圖的任何一個(gè)面 iF , 內(nèi)部有且僅有一個(gè)結(jié)點(diǎn) ???Vvi 。 (c) 當(dāng)且僅當(dāng) ke 只是一個(gè)面 iF 的邊界時(shí) , iv? 存在一個(gè)環(huán) ke? 與 ke 相交 , 則稱(chēng)?G 是 G 的對(duì)偶圖 . 定義 2 若圖 G 的對(duì)偶圖 ?G 同構(gòu)于 G , 則稱(chēng) G 是自對(duì)偶圖 . 定理 1 設(shè) ?G 是連通平面圖 G 的對(duì)偶圖 , ?n , *m , ?r 和 n , m , r 分別為 ?G 和 G 的頂點(diǎn) 數(shù)、 邊數(shù)和面數(shù) , 則 (1) rn?? 。 (3) nr?? 。(2) mm?? 。(4) 設(shè) ?iV 位于 G 的面 iR 中 , 則 ? ? ? ?ii RVdG deg??? , 其中?n , *m , ?r , n , m , r 同前 .