《特殊平面圖與平面圖的對偶》由會員分享，可在線閱讀，更多相關《特殊平面圖與平面圖的對偶（33頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 1Email: 圖 論 及 其 應 用任課教師：楊春數(shù)學科學學院 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 2 本 次 課 主 要 內 容(一 )、 一 些 特 殊 平 面 圖(二 )、 平 面 圖 的 對 偶 圖特 殊 平 面 圖 與 平 面 圖 的 對 偶 圖 1、 極 大 平 面 圖 及 其 性 質 2、 極 大 外 平 面 圖 及 其 性 質 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.

2、5 2 1 0.5 0 0.5 1 n 3 1、 極 大 平 面 圖 及 其 性 質(一 )、 一 些 特 殊 平 面 圖 對 于 一 個 簡 單 平 面 圖 來 說 ， 在 不 鄰 接 頂 點 對 間 加 邊 ，當 邊 數(shù) 增 加 到 一 定 數(shù) 量 時 ， 就 會 變 成 非 平 面 圖 。 這 樣 ，就 啟 發(fā) 我 們 研 究 平 面 圖 的 極 圖 問 題 。 定 義 1 設 G 是 簡 單 可 平 面 圖 ， 如 果 G 是 K i (1 i 4),或者 在 G的 任 意 非 鄰 接 頂 點 間 添 加 一 條 邊 后 ， 得 到 的 圖 均 是非 可 平 面 圖 ， 則 稱 G是

3、極 大 可 平 面 圖 。 極 大 可 平 面 圖 的 平 面 嵌 入 稱 為 極 大 平 面 圖 。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 4 注 ： 只 有 在 單 圖 前 提 下 才 能 定 義 極 大 平 面 圖 。 引 理 設 G是 極 大 平 面 圖 ， 則 G必 然 連 通 ； 若 G的 階 數(shù) 大于 等 于 3， 則 G無 割 邊 。 極 大 平 面圖 非 極 大 平面 圖 極 大 平 面圖 (1) 先 證 明 G連 通 。 若 不 然 ， G至 少 兩 個 連 通 分 支 。 設 G1與 G2是 G的 任

4、意 兩個 連 通 分 支 。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 5 把 G1畫 在 G2的 外 部 面 上 ， 并 在 G1,G2上 分 別 取 一 點 u與 v.連 接 u與 v得 到 一 個 新 平 面 圖 G*。 但 這 與 G是 極 大 平 面 圖 相矛 盾 。 (2) 當 G的 階 數(shù) n 3時 ， 我 們 證 明 G中 沒 有 割 邊 。 若 不 然 ， 設 G中 有 割 邊 e = uv， 則 G-uv不 連 通 ， 恰 有 兩個 連 通 分 支 G1與 G2。 uve G 1G 2 G f 0.8 1 0

5、.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 6 設 u在 G 1中 ， 而 v在 G 2中 。 由 于 n3, 所 以 ， 至 少 有 一個 分 支 包 含 兩 個 以 上 的 頂 點 。 設 G 2至 少 含 有 兩 個 頂 點 。又 設 G 1中 含 有 點 u的 面 是 f , 將 G 2畫 在 f 內 。 由 于 G 是 單 圖 ， 所 以 ， 在 G 2的 外 部 面 上 存 在 不 等 于 點v的 點 t。 現(xiàn) 在 ， 在 G 中 連 接 點 u與 t得 新 平 面 圖 G *,它 比 G多 一 條 邊 。 這 與 G 的 極 大

6、性 相 矛 盾 。vu e G 1G 2G 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 7 下 面 證 明 極 大 平 面 圖 的 一 個 重 要 性 質 。 定 理 1 設 G 是 至 少 有 3個 頂 點 的 平 面 圖 ， 則 G 是 極 大 平面 圖 ， 當 且 僅 當 G 的 每 個 面 的 次 數(shù) 是 3且 為 單 圖 。 注 ： 該 定 理 可 以 簡 單 記 為 是 “ 極 大 平 面 圖 的 三 角 形 特征 ” ， 即 每 個 面 的 邊 界 是 三 角 形 。 證 明 ： “ 必 要 性 ” 由 引 理 知

7、， G 是 單 圖 、 G 無 割 邊 。 于 是 G 的 每 個 面 的次 數(shù) 至 少 是 3。 假 設 G 中 某 個 面 f 的 次 數(shù) 大 于 等 于 4。 記 f 的 邊 界 是v 1v2v3v4vk。 如 下 圖 所 示 : 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 8 如 果 v1與 v3不 鄰 接 ， 則 連 接 v1v3， 沒 有 破 壞 G 的 平 面 性 ，這 與 G 是 極 大 平 面 圖 矛 盾 。 所 以 v1v3必 須 鄰 接 ， 但 必 須 在 f 外 連 線 ； 同 理 v2與 v4也 必 須

8、在 f 外 連 線 。 但 邊 v1v3與 邊v2v4在 f 外 交 叉 ， 與 G 是 平 面 圖 矛 盾 ！ 所 以 ， G 的 每 個 面 次 數(shù) 一 定 是 3. 定 理 的 充 分 性 是 顯 然 的 。v1v2 v3 v4 v5vkf 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 9 推 論 ： 設 G 是 n個 點 ， m條 邊 和 個 面 的 極 大 平 面 圖 ，且 n 3.則 ： (1) m=3n-6; (2) =2n-4. 證 明 ： 因 為 G 是 極 大 平 面 圖 ， 所 以 ， 每 個 面 的 次 數(shù)

9、為 3.由 次 數(shù) 公 式 ： 2 deg( ) 3fm f 由 歐 拉 公 式 ： 2 n m 所 以 得 ： 2 23 m n m 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 10 所 以 得 ： 3 6m n 又 2m n 所 以 ： 2 4n 注 ： 頂 點 數(shù) 相 同 的 極 大 平 面 圖 并 不 唯 一 。 例 如 ： 正 20面 體 非 正 20面 體 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 11 還 在 研 究 中 的 問 題 是 ： 頂 點 數(shù)

10、 相 同 的 極 大 平 面 圖 的 個數(shù) 和 結 構 問 題 。 2、 極 大 外 平 面 圖 及 其 性 質 定 義 2 若 一 個 可 平 面 圖 G 存 在 一 種 平 面 嵌 入 ， 使 得 其 所有 頂 點 均 在 某 個 面 的 邊 界 上 ， 稱 該 圖 為 外 可 平 面 圖 。 外 可平 面 圖 的 一 種 外 平 面 嵌 入 ， 稱 為 外 平 面 圖 。 外 可 平 面 圖 外 平 面 圖 1f 外 平 面 圖 2 f 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 12 注 ： 對 外 可 平 面 圖 G 來

11、 說 ， 一 定 存 在 一 種 外 平 面 嵌 入 ，使 得 G 的 頂 點 均 在 外 部 面 的 邊 界 上 。 這 由 球 極 投 影 法 可 以說 明 。 下 面 研 究 極 大 外 平 面 圖 的 性 質 。 定 義 3 設 G 是 一 個 簡 單 外 可 平 面 圖 ， 若 在 G 中 任 意 不 鄰接 頂 點 間 添 上 一 條 邊 后 ， G 成 為 非 外 可 平 面 圖 ， 則 稱 G 是極 大 外 可 平 面 圖 。 極 大 外 可 平 面 圖 的 外 平 面 嵌 入 ， 稱 為 極大 外 平 面 圖 。 極 大 外 平 面 圖 0.8 1 0.6 0.4 0.2 0

12、x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 13 定 理 2 設 G 是 一 個 有 n (n3)個 點 ， 且 所 有 點 均 在 外 部 面上 的 極 大 外 平 面 圖 ， 則 G 有 n-2個 內 部 面 。 證 明 ： 對 G 的 階 數(shù) 作 數(shù) 學 歸 納 。 當 n=3時 ， G 是 三 角 形 ， 顯 然 只 有 一 個 內 部 面 ； 設 當 n=k時 ， 結 論 成 立 。 當 n=k+1時 ， 首 先 ， 注 意 到 G 必 有 一 個 2度 頂 點 u在 G 的外 部 面 上 。 (這 可 以 由 上 面 引 理 得 到 ) 考 慮 G 1=G

13、-v。 由 歸 納 假 設 ， G 1有 k-2個 內 部 面 。 這 樣 G有 k-1個 內 部 面 。 于 是 定 理 2得 證 。 引 理 設 G 是 一 個 連 通 簡 單 外 可 平 面 圖 ， 則 在 G 中 有 一個 度 數(shù) 至 多 是 2的 頂 點 。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 14 定 理 3 設 G 是 一 個 有 n (n3)個 點 ， 且 所 有 點 均 在 外 部 面上 的 外 平 面 圖 ， 則 G 是 極 大 外 平 面 圖 ， 當 且 僅 當 其 外 部 面的 邊 界 是 圈 ，

14、內 部 面 是 三 角 形 。 注 ： 這 是 極 大 外 平 面 圖 的 典 型 特 征 。 證 明 ： 先 證 明 必 要 性 。 (1) 證 明 G 的 邊 界 是 圈 。 容 易 知 道 ： G 的 外 部 面 邊 界 一 定 為 閉 跡 ， 否 則 ， G 不 能為 極 大 外 平 面 圖 。 設 W=v1v2vnv1是 G 的 外 部 面 邊 界 。 若W不 是 圈 ， 則 存 在 i與 j, 使 vi=vj=v.此 時 ， G可 以 示 意 如 下 ： W vi-1 v1vnv2vi+1vj-1 vj+1v 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5

15、2 1 0.5 0 0.5 1 n 15 vi-1與 vi+1不 能 鄰 接 。 否 則 W不 能 構 成 G 的 外 部 面 邊 界 。這 樣 ， 我 們 連 接 vi-1與 vi+1： vi-1 v1vnv2vi+1vj-1 vj+1v 得 到 一 個 新 外 平 面 圖 。 這 與 G 的 極 大 性 矛 盾 。 (2) 證 明 G 的 內 部 面 是 三 角 形 。 首 先 ， 注 意 到 ， G 的 內 部 面 必 須 是 圈 。 因 為 ， G 的 外 部面 的 邊 界 是 生 成 圈 ， 所 以 G 是 2連 通 的 ， 所 以 ， G 的 每 個 面的 邊 界 必 是 圈 。

16、0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 16 其 次 ， 設 C是 G 中 任 意 一 個 內 部 面 的 邊 界 。 如 果 C的 長 度大 于 等 于 4， 則 C中 一 定 存 在 不 鄰 接 頂 點 ， 連 接 這 兩 點 得 到一 個 新 平 面 圖 ， 這 與 G 的 極 大 性 矛 盾 。 又 由 于 G 是 單 圖 ，所 以 C的 長 度 只 能 為 3. 下 面 證 明 充 分 性 。 設 G 是 一 個 外 平 面 圖 ， 內 部 面 是 三 角 形 ， 外 部 面 是 圈 W. 如 果 G 不 是 極 大

17、 外 平 面 圖 ， 那 么 存 在 不 鄰 接 頂 點 u與 v,使得 G +uv是 外 平 面 圖 。 但 是 ， G +uv不 能 是 外 平 面 圖 。 因 為 ， 若 邊 uv經(jīng) 過 W的內 部 ， 則 它 要 與 G 的 其 它 邊 相 交 ； 若 uv經(jīng) 過 W的 外 部 ， 導致 所 有 點 不 能 在 G 的 同 一 個 面 上 。 所 以 ， G 是 極 大 外 平 面 圖 。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 17 定 理 4 每 個 至 少 有 7個 頂 點 的 外 可 平 面 圖 的 補 圖 不

18、 是 外可 平 面 圖 ， 且 7是 這 個 數(shù) 目 的 最 小 者 。 我 們 用 枚 舉 方 法 證 明 。 證 明 ： 對 于 n=7的 極 大 外 可 平 面 圖 來 說 ， 只 有 4個 。 如下 圖 所 示 。 直 接 驗 證 ： 它 們 的 補 圖 均 不 是 外 可 平 面 的 。 而 當 n=6時 ， 我 們 可 以 找 到 一 個 外 可 平 面 圖 G (見 下 圖 ),使 得 其 補 圖 是 外 可 平 面 圖 。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 18 G G(二 )、 平 面 圖 的 對 偶

19、圖 1、 對 偶 圖 的 定 義 定 義 4 給 定 平 面 圖 G ， G 的 對 偶 圖 G *如 下 構 造 ： (1) 在 G 的 每 個 面 fi內 取 一 個 點 vi*作 為 G *的 一 個 頂 點 ； (2) 對 G 的 一 條 邊 e, 若 e是 面 fi 與 fj 的 公 共 邊 ， 則 連 接 vi*與 vj*， 且 連 線 穿 過 邊 e;若 e是 面 fi 中 的 割 邊 ， 則 以 vi為 頂 點 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 19 作 環(huán) ， 且 讓 它 與 e相 交 。 例 如 ，

20、作 出 平 面 圖 G 的 對 偶 圖 G *G 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 20 2、 對 偶 圖 的 性 質 (1)、 G 與 G *的 對 應 關 系 1) G *的 頂 點 數(shù) 等 于 G 的 面 數(shù) ； 2) G *的 邊 數(shù) 等 于 G 的 邊 數(shù) ； 3) G *的 面 數(shù) 等 于 G 的 頂 點 數(shù) ； 4) d (v*)=deg( f ) 對 偶 圖面邊割 邊環(huán)邊 割 集回 路點邊環(huán)割 邊回 路邊 割 集 對 應平 面 圖 G 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5

21、 2 1 0.5 0 0.5 1 n 21 (2)、 定 理 5 定 理 5 平 面 圖 G 的 對 偶 圖 必 然 連 通 證 明 ： 在 G *中 任 意 取 兩 點 vi*與 vj*。 我 們 證 明 該 兩 點 連通 即 可 ！ 用 一 條 曲 線 l 把 vi*和 vj*連 接 起 來 ， 且 l 不 與 G *的 任 意頂 點 相 交 。 顯 然 ， 曲 線 l 從 vi*到 vj*經(jīng) 過 的 面 邊 序 列 ， 對 應 從 vi*到vj*的 點 邊 序 列 ， 該 點 邊 序 列 就 是 該 兩 點 在 G *中 的 通 路 。 注 : (1) 由 定 理 5知 ： (G *)*

22、不 一 定 等 于 G ; 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 22 證 明 ： “ 必 要 性 ” (2) G 是 平 面 圖 ， 則 當 且 僅 當 G 是 連 通 的 。(習 題 第 26題 ) ( *)*G G 由 于 G 是 平 面 圖 ， 由 定 理 5， G *是 連 通 的 。 而 由 G *是 平面 圖 ， 再 由 定 理 5， (G *)*是 連 通 的 。 所 以 ， 由 得 ： G 是 連 通 的 。( *)*G G “ 充 分 性 ” 由 對 偶 圖 的 定 義 知 ， 平 面 圖 G 與 其 對

23、 偶 圖 G *嵌 入 在 同 一 平面 上 ， 當 G 連 通 時 ， 容 易 知 道 ： G *的 無 界 面 f *中 僅 含 G 的 唯一 頂 點 v,而 除 v外 ， G 中 其 它 頂 點 u均 與 G *的 有 限 面 形 成 一 一 對應 ， 于 是 ， G 中 頂 點 和 G *頂 點 在 這 種 自 然 對 應 方 式 下 一 一 對應 ， 且 對 應 頂 點 間 鄰 接 關 系 保 持 不 變 ， 故 ： ( *)*G G 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 23 (3) 同 構 的 平 面 圖 可

24、以 有 不 同 構 的 對 偶 圖 。 例 如 ， 下 面 的 兩 個 圖 ： 1 2G GG 1 G 2 但 1 2* *G G 這 是 因 為 ： G 2中 有 次 數(shù) 是 1的 面 ， 而 G 1沒 有 次 數(shù) 是 1的面 。 所 以 ， 它 們 的 對 偶 圖 不 能 同 構 。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 24 第 一 次 上 交 作 業(yè) 第 3章 習 題 3 ： 1， 7， 9， 16. 第 4章 習 題 4 ： 3， 7， 10， 12. 第 5章 習 題 5 ： 1， 2， 6， 7， 13， 19

25、。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 25 作 業(yè) P143-146 習 題 5 ： 3， 4， 5， 6， 8， 25, 26， 27。 其 中 25， 26， 27結 合 課 件 學 習 。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 26 Thank You ! 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 27 例 2 證 明 ： * ( *) *c E G c B C (1) B是 平

26、面 圖 G 的 極 小 邊 割 集 ， 當 且 僅 當 是 G *的 圈 。 (2) 歐 拉 平 面 圖 的 對 偶 圖 是 偶 圖 。 示 意 圖 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 28 證 明 : (1) 對 B的 邊 數(shù) 作 數(shù) 學 歸 納 。 示 意 圖 當 B的 邊 數(shù) n=1時 ， B中 邊 是 割 邊 顯 然 ， 在 G *中 對 應 環(huán) 。 所 以 ， 結 論 成 立 。 設 對 B的 邊 數(shù) nk 時 ， 結 論 成 立 。 考 慮 n=k的 情 形 。 設 c1 B, 于 是 B-c1是 G -c1=

27、G 1的 一 個 極 小 邊 割 集 。 由 歸納 假 設 ： 1 1 1* ( *) *c E G c B c C 是 G 1*的 一 個 圈 。 且 圈 C1*上 的 頂 點 對 應 于 G 1中 的 面 f, f 的邊 界 上 有 極 小 邊 割 集 B-e1的 邊 。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 29 現(xiàn) 在 ， 把 e1加 入 到 G 1中 ， 恢 復 G 。示 意 圖 G 1 由 于 G 是 平 面 圖 ， 其 作 用 相 當 于 圈 C1*上 的 一 個 頂 點 對應 于 G 1中 的 一 個 平 面

28、 區(qū) 域 f, 被 e1劃 分 成 兩 個 頂 點 f1*與 f2*,并在 其 間 連 以 e1所 對 應 的 邊 e1*。 所 以 ， B對 應 在 G *中 的 C*仍 然 是 一 個 圈 。 由 歸 納 法 ，結 論 得 到 證 明 。 示 意 圖 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 30 充 分 性 ： G *中 的 一 個 圈 ， 對 應 于 G 中 的 邊 的 集 合 B顯 然 是 G 中 的 一個 邊 割 集 。 示 意 圖 若 該 割 集 不 是 極 小 邊 割 集 ， 則 它 是 G 中 極 小 邊 割

29、集 之和 。 而 由 必 要 性 知 道 ： 每 個 極 小 邊 割 集 對 應 G *的 一 個圈 ， 于 是 推 出 B在 G *中 對 應 的 邊 集 合 是 圈 之 并 。 但 這 與假 設 矛 盾 。 (2) 因 歐 拉 圖 的 任 意 邊 割 集 均 有 偶 數(shù) 條 邊 。 于 是 由(1),G *中 不 含 奇 圈 。 所 以 G *是 偶 圖 。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 31 例 3 設 T是 連 通 平 面 圖 G 的 生 成 樹 ， * * ( *) ( )E e E G e E T 證 明

30、 ： T*=G *E*是 G *中 的 生 成 樹 。 (習 題 第 27題 ) 示 意 圖 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 32 證 明 ： 情 形 1， 如 果 G 是 樹 。 在 這 種 情 況 下 ， E* = .則 T*是 平 凡 圖 ， 而 G*的 生 成 樹也 是 平 凡 圖 ， 所 以 ， 結 論 成 立 ； 情 形 2， 如 果 G 不 是 樹 。 因 G 的 每 個 面 必 然 含 有 邊 e不 屬 于 E(T),即 G *的 每 個 頂 點必 然 和 E*中 的 某 邊 關 聯(lián) ， 于 是 T*必

31、 然 是 G *的 生 成 子 圖 。 下 面 證 明 ： T*中 沒 有 圈 。 若 T*中 有 圈 。 則 由 例 2知 ： T的 余 樹 中 含 有 G 的 極 小 邊 割集 。 但 我 們 又 可 以 證 明 ： 如 果 T是 連 通 圖 G 的 生 成 樹 ， 那 么 ，T的 余 樹 不 含 G 的 極 小 邊 割 集 。 這 樣 ， T*不 能 含 G *的 圈 。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 33 又 因 在 G 中 ， 每 去 掉 T的 余 樹 中 的 一 條 邊 ， G 的 面 減 少 一個 ， 當 T的 余 樹 中 的 邊 全 去 掉 時 ， G 變 成 一 顆 樹 T. 于 是 ， 有 ：( *) ( ) ( ) 1 ( *) 1E T E T G V G 所 以 ， T*是 G *的 生 成 樹 。