離散數(shù)學(xué)平面

8.4 平 面 圖 平 面 圖 與 平 面 嵌 入 平 面 圖 的 面 、 有 限 面 、 無 限 面 面 的 次 數(shù) 極 大 平 面 圖 極 小 非 平 面 圖 歐 拉 公 式 平 面 圖 的 對 偶 圖 平 面 圖 和 平 面 嵌 入 定 義 如 果 能 將 圖 G除 頂 點(diǎn) 外 邊 不 相 交 地 畫 在 平 面 上 , 則 稱 G是 平 面 圖 . 這 個 畫 出 的 無 邊 相 交 的 圖 稱 作 G的 平 面 嵌 入 . 沒 有 平 面 嵌 入 的 圖 稱 作 非 平 面 圖 . 例 如 下 圖 中 (1)(4)是 平 面 圖 , (2)是 (1)的 平 面 嵌 入 ，(4)是 (3)的 平 面 嵌 入 . (5)是 非 平 面 圖 . 平 面 圖 和 平 面 嵌 入 (續(xù) ) 今 后 稱 一 個 圖 是 平 面 圖 , 可 以 是 指 定 義 中 的 平 面 圖 , 又 可 以是 指 平 面 嵌 入 , 視 當(dāng) 時 的 情 況 而 定 . 當(dāng) 討 論 的 問 題 與 圖 的 畫法 有 關(guān) 時 , 是 指 平 面 嵌 入 . K5和 K3,3是 非 平 面 圖 設(shè) G G, 若 G為 平 面 圖 , 則 G 也 是 平 面 圖 ; 若 G 為 非 平 面 圖 , 則 G也 是 非 平 面 圖 . K n(n5), K3,n(n3)都 是 非 平 面 圖 . 平 行 邊 與 環(huán) 不 影 響 圖 的 平 面 性 . K5K3,3 平 面 圖 的 面 與 次 數(shù)設(shè) G是 一 個 平 面 嵌 入G的 面 : 由 G的 邊 將 平 面 劃 分 成 的 每 一 個 區(qū) 域無 限 面 (外 部 面 ): 面 積 無 限 的 面 , 用 R0表 示有 限 面 (內(nèi) 部 面 ): 面 積 有 限 的 面 , 用 R1, R2, Rk表 示 面 Ri的 邊 界 : 包 圍 Ri的 所 有 邊 構(gòu) 成 的 回 路 組面 Ri的 次 數(shù) : Ri邊 界 的 長 度 ， 用 deg(Ri)表 示 說 明 : 構(gòu) 成 一 個 面 的 邊 界 的 回 路 組 可 能 是 初 級 回 路 , 簡 單 回路 , 也 可 能 是 復(fù) 雜 回 路 , 還 可 能 是 非 連 通 的 回 路 之 并 . 定 理 平 面 圖 各 面 的 次 數(shù) 之 和 等 于 邊 數(shù) 的 2倍 . 平 面 圖 的 面 與 次 數(shù) (續(xù) )例 1 右 圖 有 4個 面 , deg(R1)=1, deg(R2)=3, deg(R3)=2, deg(R0)=8. 請 寫 各 面 的 邊 界 . 例 2 左 邊 2個 圖 是 同 一 個 平 面圖 的 平 面 嵌 入 . R1在 (1)中 是外 部 面 , 在 (2)中 是 內(nèi) 部 面 ; R 2在 (1)中 是 內(nèi) 部 面 , 在 (2)中 是外 部 面 . 其 實 , 在 平 面 嵌 入 中可 把 任 何 面 作 為 外 部 面 . 極 大 平 面 圖 定 義 若 G是 簡 單 平 面 圖 , 并 且 在 任 意 兩 個 不 相 鄰 的 頂 點(diǎn) 之間 加 一 條 新 邊 所 得 圖 為 非 平 面 圖 , 則 稱 G為 極 大 平 面 圖 .性 質(zhì) 若 簡 單 平 面 圖 中 已 無 不 相 鄰 頂 點(diǎn) ， 則 是 極 大 平 面 圖 . 如 K1, K2, K3, K4都 是 極 大 平 面 圖 . 極 大 平 面 圖 必 連 通 . 階 數(shù) 大 于 等 于 3的 極 大 平 面 圖 中 不 可 能 有 割 點(diǎn) 和 橋 . 設(shè) G為 n(n3)階 極 大 平 面 圖 , 則 G每 個 面 的 次 數(shù) 均 為 3. 任 何 n(n4)階 極 大 平 面 圖 G均 有 (G)3. 實 例3個 圖 都 是 平 面 圖 , 但 只 有 右 邊 的 圖 為 極 大 平 面 圖 . 極 小 非 平 面 圖 定 義 若 G是 非 平 面 圖 , 并 且 任 意 刪 除 一 條 邊 所 得 圖都 是 平 面 圖 , 則 稱 G為 極 小 非 平 面 圖 .說 明 : K5, K3,3都 是 極 小 非 平 面 圖 極 小 非 平 面 圖 必 為 簡 單 圖下 面 4個 圖 都 是 極 小 非 平 面 圖 歐 拉 公 式 定 理 8.11 (歐 拉 公 式 ) 設(shè) G為 n階 m條 邊 r個 面 的 連 通 平 面 圖 ，則 nm+r=2. 證 對 邊 數(shù) m做 歸 納 證 明 . m=0, G為 平 凡 圖 , 結(jié) 論 為 真 .設(shè) m=k(k0)結(jié) 論 為 真 , m=k+1時 分 情 況 討 論 如 下 : (1) G中 無 圈 , 則 G必 有 一 個 度 數(shù) 為 1的 頂 點(diǎn) v, 刪 除 v及 它 關(guān)聯(lián) 的 邊 , 記 作 G . G 連 通 , 有 n-1個 頂 點(diǎn) , k條 邊 和 r個 面 . 由 歸納 假 設(shè) , (n-1)-k+r=2, 即 n-(k+1)+r=2, 得 證 m=k+1時 結(jié) 論 成 立 . (2) 否 則 ,刪 除 一 個 圈 上 的 一 條 邊 ,記 作 G . G 連 通 , 有 n個 頂點(diǎn) ,k條 邊 和 r-1個 面 . 由 歸 納 假 設(shè) , n-k+(r-1)=2, 即 n-(k+1)+r=2,得 證 m=k+1時 結(jié) 論 也 成 立 . 證 畢 . 歐 拉 公 式 (續(xù) )歐 拉 公 式 的 推 廣 設(shè) G是 有 p (p2) 個 連 通 分 支 的 平 面 圖 , 則 n m + r = p + 1證 設(shè) 第 i 個 連 通 分 支 有 ni個 頂 點(diǎn) , mi 條 邊 和 ri 個 面 . 對 各 連 通 分 支 用 歐 拉 公 式 , ni mi + ri = 2, i = 1, 2, , p求 和 并 注 意 r = r1+rp+ p1, 即 得 n m + r = p + 1 與 歐 拉 公 式 有 關(guān) 的 定 理 )2(2 nl lm K 5 K3,3 定 理 設(shè) G為 n階 連 通 平 面 圖 , 有 m條 邊 , 且 每 個 面 的 次 數(shù) 不小 于 l (l 3), 則 證 由 定 理 (各 面 次 數(shù) 之 和 等 于 邊 數(shù) 的 2倍 )及 歐 拉 公 式 得 2m lr = l (2+m-n)可 解 得 所 需 結(jié) 論 . 推 論 K5 和 K3,3不 是 平 面 圖 .證 用 反 證 法 , 假 設(shè) 它 們 是 平 面 圖 ,則 K5 : n=5, m=10, l=3 K 3,3 : n=6, m=9, l=4與 定 理 矛 盾 . 與 歐 拉 公 式 有 關(guān) 的 定 理 (續(xù) )1(2 pnl lm定 理 : 設(shè) G為 有 p (p2) 個 連 通 分 支 的 平 面 圖 , 且 每 個 面 的 次 數(shù) 不 小 于 l (l 3), 則定 理 設(shè) G為 簡 單 平 面 圖 ， 則 (G)5. 同 胚 與 收 縮 消 去 2度 頂 點(diǎn) v 如 上 圖 從 (1)到 (2)插 入 2度 頂 點(diǎn) v 如 上 圖 從 (2)到 (1)G1與 G2同 胚 : G1與 G2同 構(gòu) , 或經(jīng) 過 反 復(fù) 插 入 、 或 消 去 2度 頂點(diǎn) 后 同 構(gòu)收 縮 邊 e 如 下 圖 從 (1)到 (2) 庫 拉 圖 斯 基 定 理定 理 G是 平 面 圖 G中 不 含 與 K5同 胚 的 子 圖 , 也 不含 與 K3,3同 胚 的 子 圖 .定 理 G是 平 面 圖 G中 無 可 收 縮 為 K5的 子 圖 , 也 無可 收 縮 為 K3,3的 子 圖 . 非 平 面 圖 證 明例 證 明 下 述 2個 圖 均 為 非 平 面 圖 . 證 圖 中 紅 色 部 分 分 別 與 K 3,3和 K5 同 胚 平 面 圖 的 對 偶 圖 定 義 設(shè) 平 面 圖 G, 有 n個 頂 點(diǎn) , m條 邊 和 r個 面 , 構(gòu) 造 G的 對 偶 圖 G*=如 下 ：在 G的 每 一 個 面 Ri中 任 取 一 個 點(diǎn) vi*作 為 G*的 頂 點(diǎn) , V*= vi*| i=1,2,r .對 G每 一 條 邊 ek, 若 ek在 G的 面 Ri與 Rj的 公 共 邊 界 上 , 則 作 邊 ek*=(vi*,vj*), 且 與 ek相 交 ; 若 ek為 G中 的 橋 且 在面 R i的 邊 界 上 , 則 作 環(huán) ek*=(vi*,vi*). E*= ek*| k=1,2, ,m . 平 面 圖 的 對 偶 圖 （ 續(xù) ）例 黑 色 實 線 為 原 平 面 圖 , 紅 色 虛 線 為 其 對 偶 圖 平 面 圖 的 對 偶 圖 (續(xù) )性 質(zhì) ： G*是 平 面 圖 ， 而 且 是 平 面 嵌 入 . G*是 連 通 圖 若 邊 e為 G中 的 環(huán) ， 則 G*與 e對 應(yīng) 的 邊 e*為 橋 ; 若 e為 橋 ， 則 G*中 與 e對 應(yīng) 的 邊 e*為 環(huán) . 在 多 數(shù) 情 況 下 ， G*含 有 平 行 邊 . 同 構(gòu) 的 平 面 圖 的 對 偶 圖 不 一 定 同 構(gòu) . 上 面 兩 個 平 面 圖 是 同 構(gòu) 的 , 但 它 們 的 對 偶 圖 不 同 構(gòu) . 平 面 圖 與 對 偶 圖 的 階 數(shù) 、 邊 數(shù) 與 面 數(shù) 之 間 的 關(guān) 系 :設(shè) G*是 平 面 圖 G的 對 偶 圖 ， n*, m*, r*和 n, m, r分 別為 G*和 G的 頂 點(diǎn) 數(shù) 、 邊 數(shù) 和 面 數(shù) ， 則(1) n*= r(2) m*=m(3) r*=n-p+1, 其 中 p是 G的 連 通 分 支 數(shù)(4) 設(shè) G*的 頂 點(diǎn) vi*位 于 G的 面 Ri中 , 則 d(vi*)=deg(Ri)平 面 圖 的 對 偶 圖 (續(xù) )