平面圖、對偶圖和色數(shù)的應(yīng)用探究-畢業(yè)論(編輯修改稿)
2025-07-08 22:42 本頁面
【文章內(nèi)容簡介】 每兩個頂點(diǎn)之間都有一條邊相連的平面圖 , 如圖 8. n 個頂點(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 , 共有 v 個結(jié)點(diǎn) e 條邊和 r 個面 ,則歐拉公式 2??? rev 成立 . 定理 2 設(shè) G 是一個有 v 個結(jié)點(diǎn) e 條邊的連通簡單平面圖 , 若 3?v , 則63 ?? ve . 推論 如果圖 ??? EVG , 是連通的簡單平面圖 , 若 3?v , 且每個區(qū)域至少由四條邊圍成 , 則有 42 ?? ve . 對偶圖的相關(guān)概念 定義 1 給定平面圖 ??? EVG , , 它具有面 1F , 2F ,? , nF , 若有圖 ??? ??? EVG ,滿足下列條件 : (a) 對于圖的任何一個面 iF , 內(nèi)部有且僅有一個結(jié)點(diǎn) ???Vvi 。 (b) 對于圖的面 iF 和 jF 的公共邊界 ke , 有且僅有一條邊 ???Eek , 使得? ?jik vve ??? ? , , 且 ke? 與 ke 相交 。 (c) 當(dāng)且僅當(dāng) ke 只是一個面 iF 的邊界時 , iv? 存在一個環(huán) ke? 與 ke 相交 , 則稱?G 是 G 的對偶圖 . 定義 2 若圖 G 的對偶圖 ?G 同構(gòu)于 G , 則稱 G 是自對偶圖 . 定理 1 設(shè) ?G 是連通平面圖 G 的對偶圖 , ?n , *m , ?r 和 n , m , r 分別為 ?G 和 G 的頂點(diǎn) 數(shù)、 邊數(shù)和面數(shù) , 則 (1) rn?? 。 (2) mm?? 。 (3) nr?? 。 (4) 設(shè) ?G 的頂點(diǎn) iv? 位于 G 的面 iR 中 , 則 ? ? ? ?ii RvGd deg?? ? . 定理 2 設(shè) ?G 是具有 w 個連通分支的平面圖 G 的對偶圖 , 則 (1) rn?? 。(2) mm?? 。(3) 1???? wnr 。(4) 設(shè) ?iV 位于 G 的面 iR 中 , 則 ? ? ? ?ii RVdG deg??? , 其中?n , *m , ?r , n , m , r 同前 . 色數(shù)的相關(guān)概念和定理 圖中頂點(diǎn)的 著色 定義 1 圖 G 的一種著色 , 即 對無環(huán)圖 G 的每個頂點(diǎn)涂上一種顏色 , 使相鄰頂點(diǎn)涂不同的顏色 . ６ 定義 2 對 G 進(jìn)行 k 著色（ G 是 ?k 可著色的） , 即 能用 k 種顏色給 G 的頂點(diǎn)著色 . 定義 3 G 的色數(shù) ? ? kG?? , 即 G 是 ?k 可著色的 , 但不是 ? ???1k 可著色的 . 定理 1 ? ? 1?G? 當(dāng)且僅當(dāng) G 為零圖 . 定理 2 ? ? nKn ?? . 定理 3 設(shè) G 中至少含有一條邊 , 則 ? ? 2?G? 當(dāng)且僅當(dāng) G 為二部圖 . 定理 4 對于任意無向圖 G , 均有 ? ??G? ?? ? 1?G . 定理 5 圈圖著色定理 : 用 k (k 為正整數(shù) ) 種顏色給圈圖 nC 的頂點(diǎn)著色 , 方法數(shù)為 : ? ? ? ? ? ?111, ????? kkf nnkn , 其中 2?n , kf k ?,1 . 定理 6 輪圖著色定理 : 用 k (k 為正整數(shù) )種顏色給輪圖 nW 的頂點(diǎn)著色 , 方法數(shù)為 : )]2()1()2[( 2, ????? kkkg nkn ,其中 2?n , )1(,1 ?? kkg k , 2,1, ?? ? nkfg knkn . 推論 1 圈圖 nC 上一個指定的頂點(diǎn)染指定的顏色 , 方法數(shù)為 kf kn, , 1?k . 推論 2 圈圖 nC 上兩個指定相鄰的頂點(diǎn)染指定的不同的顏色 , 方法數(shù)為)1( ,?kkf kn, 2?k . 邊著色 定義 1 對圖 G 邊的一種著色 , 即對圖 G 的每條邊涂上一種顏色 , 使相鄰的邊涂不同的顏色 . 定義 2 G 是 ?k 邊可著色的 , 即能用 k 種顏色給 G 的邊著色 . 定義 3 G 的邊色數(shù) ? ?G?? k? , 即 G 是 ?k 邊可著色的 , 但不是 ? ???1k 邊可著色的 , 也就是說 最少用 k 種顏色給 G 的邊著色 . 定理 1 G 為 簡單平面圖 , 則 ???G ? ? ?G?? ? ?? ? 1?G . 定理 2 若 G 是二部圖 , 則 ? ???G? ?. ７ 面著色 定義 1 G 是 ?k 面可著色的 , 即能用 k 種顏色給 G 的面著色 , 就稱對 G 的面進(jìn)行了 k 著色 . 定義 2 G 的面色數(shù) ? ?G?? k? , 即 G 是 ?k 面可著色的 , 但不是 ? ???1k 面可著色的 , 也就是說 最少用 k 種顏色給 G 的面著色 . 定理 1 圖 G 是 ?k 面可著色的當(dāng)且僅當(dāng)它的對偶圖 ?G 是 ?k 點(diǎn)可著色的 . 定理 2 任何平面圖都是 ?5 可著色的 . 3 平面圖、對偶圖和色數(shù)的應(yīng)用 平面圖理論的應(yīng)用 例 1 (空調(diào)管道的設(shè)計 ) 某娛樂中心有 6 個景點(diǎn) , 位置分布如下圖 . 圖 10 經(jīng)考察知 , 1A 與 4A 、 2A 與 5A 、 3A 與 6A 間人流較少 , 其它景點(diǎn)之間人流量大 , 必須投資鋪設(shè)空調(diào)管道 , 但要求空調(diào)管道間不能交叉 . 如何設(shè)計 ? 如果把每個景點(diǎn)分別模型為一個點(diǎn) , 景點(diǎn)間連線 , 當(dāng)且僅當(dāng)兩景點(diǎn)間要鋪設(shè)空調(diào)管道 . 那么 , 上面問題直接對應(yīng)的圖為 : ８ 圖 11 于是 , 問題轉(zhuǎn)化為 , 能否把上圖畫在平面上 , 使得邊不會相互交叉 ? 通過嘗試 , 可以把上圖畫為 :
畢業(yè)設(shè)計相關(guān)推薦
鄂ICP備17016276號-1