離散數(shù)學(xué)第十七章平面-wenkub.com
2025-01-13 20:38 本頁面
【正文】 為了深入討論這個問題，需要引入平面圖的概念。1 第十七章 平面圖 本章的主要內(nèi)容 ? 平面圖的基本概念 ? 歐拉公式 ? 平面圖的判斷 ? 平面圖的對偶圖 2 引言 許多實際問題可以抽象為這樣的模式：在一些表示客體的結(jié)點之間 “ 布線 ” 、 “ 建通道 ” ，以建立它們之間的某些聯(lián)系，要求這些 “ 線 ” 、 “ 通道 ” 在一個平面上而又不相互交疊。 3 在圖中， (2)是 (1) 的平面嵌入， (4)是 (3)的平面嵌入 . 平面圖 的基本概念 定義 (1) G可嵌入曲面 S—— 若能將 G除頂點外無邊相交地畫在 S上 (2) G是 可平面圖 或 平面圖 —— G可嵌入平面 ? (3) 平面嵌入 —— 畫出的無邊相交的平面圖 (4) 非平面圖 —— 無平面嵌入的無向圖 (1) (2) (3) (4) 4 幾點說明及一些簡單結(jié)論 一般所談平面圖不一定是指平面嵌入，上圖中 4個圖都是平 面圖，但討論某些性質(zhì)時，一定是指平面嵌入 . 結(jié)論： (1) K5, K3,3都不是平面圖（待證） (2) 設(shè) G??G，若 G為平面圖，則 G?也是平面圖（定理 ） (3) 設(shè) G??G，若 G?為非平面圖，則 G也是非平面圖（定理），由此可知， Kn(n?6)， K3,n(n?4) 都是非平面圖 . (4) 平行邊與環(huán)不影響平面性 . 5 平面圖 (平面嵌入 )的面與次數(shù) 定義 (1) G的 面 —— 由 G的平面嵌入的邊將平面化分成的區(qū)域 (2) 無限面 或 外部面 —— （可用 R0表示） —— 面積無限的面 (3) 有限面 或 內(nèi)部面 （可用 R1, R2, …, Rk等表示） —— 面積 有限的面 (4) 面 Ri 的邊界 —— 包圍 Ri的回路組 (5) 面 Ri 的次數(shù) —— Ri邊界的長度，用 deg(Ri)表示 6 定理 平面圖各面次數(shù)之和等于邊數(shù)的兩倍 . 幾點說明 ? 若平面圖 G有 k個面，可籠統(tǒng)地用 R1, R2, …, Rk表示，不需要指出外部面 . ? 定義 (4) 中回路組是指：邊界可能是初級回路 (圈 )，可能是簡單回路，也可能是復(fù)雜回路 . 特別地，還可能是非連通的回路之并 . 平面圖有 4個面，deg(R1)=1, deg(R2)=3, deg(R3)=2, deg(R0)=8. 請寫各面的邊界 . 7 極大平面圖 定義 若在簡單平面圖 G中的任意兩個不相鄰的頂點之間 加一條新邊所得圖為非平面圖，則稱 G為 極大平面圖 . 注意：若簡單平面圖 G中已無不相鄰頂點， G顯然是極大平 面圖，如 K1(平凡圖 ), K2, K3, K4都是極大平面圖 . 極大平面圖的主要性質(zhì) 定理 極大平面圖是連通的 .
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號-1