-
平面網絡
鎖定
- 中文名
- 平面網絡
- 外文名
- planar network
- 所屬學科
- 數學(圖論)
- 屬 性
- 網絡的一種類型
- 相關概念
- 網絡,拓撲等價,同胚映射等
平面網絡基本介紹
根據網絡的定義,網絡既可以是平面上的圖形,也可以是空間的圖形。例如:四面體的稜及頂點所構成的網絡就是一個空間網絡,立方體的稜及頂點所構成的網絡也是一個空間網絡,如圖1。
在許多情況下,空間的網絡可以“置放”於平面上,或者説可以由彈性變形(同胚映射)使它成為一個平面網絡。例如圖1中的四面體和正方體的稜及頂點所構成的網絡就與圖8中的平面網絡是同胚的。
定義1一個空間網絡若能拓撲等價於某個平面網絡,則稱它為可平面的,否則稱為不可平面網絡(或非平面網絡)。
例如圖3所示的空間網絡是可平面的,其中圖3(a)是空間網絡,圖3(b)是相應的平面網絡。
特別指出:一個網絡是否可平面,這是一個拓撲性質。網絡的可平面性有廣泛的實用意義,如電力工程、無線電或電視機的標準線路的設計,都是用金屬箔片在紙板或塑膠底板上印出線路。為了適用,線路應用平面表示法,否則兩條邊交點將產生系統內的短路。並非所有的空間網絡都是可平面的,在介紹兩個著名的非平面網絡例子之前,我們先介紹約當定理
[2]
。
平面網絡相關性質
定義1 任一條同胚於圓周的曲線稱為簡單閉曲線。
這條定理就是説如果沿着這一條簡單閉曲線把平面剪開,結果平面被分成了兩塊,一塊是有界的內部,一塊為外部。直觀地看,這個定理是正確的,長久以來都認為是無須證明的事實。約當是第一個陳述這條定理的人,並指出需要證明。這條定理的證明有很多條件,且都不是很簡短的。約當定理是一條拓撲定理,即不牽涉到長度、角度和麪積等度量性質的定理,我們在此不證明它。
在平面上定理1的推廣形式為如下定理:
定理2 平面上有連接兩個已知點P和Q的K條折線,且每兩條折線都沒有其他的公共點,則平面被分為K個部分。
對於一般平面網絡而言,網絡的弧也將平面劃分成若干個部分。設A是某一平面網絡,一般來説,這個網絡可以以不同的方式分佈在平面上。例如圖3所示,這是同一個網絡的三種不同分佈方式,不同分佈的網絡之間是同胚的。
從圖上可以看出:雖然該網絡以不同的方式分佈在平面上,但不同分佈的網絡把平面分成的部分數是相同的,都是將平面分成了4個部分。平面網絡將平面劃分的部分數目是不依賴於這網絡在平面上的不同分佈的,即該數目在同胚映射下保持不變,是網絡的拓撲不變量。為此,引入網絡的面的概念。
定義2 平面網絡將平面劃分的每一個部分稱為網絡的面。
根據以上討論可知,網絡的面數是網絡的拓撲不變量。
下面我們用約當定理來説明兩個典型的網絡是非平面網絡。
例1 圖4給出一個水、電、氣供給網絡圖,其中,
分別代表水、電、氣供給點,
為三個使用水、電、氣的用户,記該網絡為
。
我們不妨試着將這個網絡變形(彈性運動)為平面網絡。該網絡共有9條弧,首先取出如下路徑
這是一條閉路徑,是由6條弧圍成的一條簡單閉曲線。根據約當定理,該閉路徑將平面劃分成兩個部分,即內部和外部,如圖5所示。剩下的3條弧,可以把一條弧
放入閉曲線的內部,另一條弧
放在其外部,而第三條弧
既不能放在內部,也不能放在外部,即無論如何不能放於平面上了,否則就與其他弧相交了。這説明網絡
不能通過同胚映射(彈性變換)成為平面網絡,
為不可平面網絡。
網絡
也稱為
完全二分網絡圖,記作
。一般的,如果網絡的頂點分為兩組
例1表明:完全二分網絡
是一個不可平面網絡。當
時,完全二分網絡
包含了不可平面網絡
(子網絡),則網絡
也一定是不可平面網絡。更一般的,如果一網絡包含了不可平面網絡
作為其子網絡,則該網絡一定是不可平面網絡
[2]
。
例2 設有5個頂點的網絡,其中每個頂點都與其他4個頂點有一條弧連接,如圖6所示,稱該網絡為5點完全網絡,記此網絡為
。用例1類似的方法,我們不妨試着將這個網絡變形(彈性運動)為平面網絡。該網絡共有10條弧,首先取路徑:1-2-3-4-5-1,這是一條閉路徑,是由5條弧圍成的一條簡單閉曲線。根據約當定理,該閉路徑將平面劃分成兩個部分,即內部和外部,如圖7所示。剩下的5條弧,可以把兩條弧(1,3)和(1,4)放入閉曲線的內部,另兩條弧(2,4)和(2,5)放在其外部,而最後一條弧(3,5)既不能放在內部,也不能放在外部,即無論如何不能放於平面上了,否則就與其他弧相交了。這説明網絡
不能通過同胚映射(彈性變換)成為平面網絡,
為不可平面網絡。
一般的,如果網絡有n個頂點,任意兩個不同頂點之間有一條弧連接,則該網絡稱為n點完全網絡,記作
。如圖8所示的部分完全網絡圖,顯然它們都是可平面網絡。
例2表明:完全網絡:
是一個不可平面網絡。當
時,完全網絡
包含了不可平面網絡
(子網絡),則網絡
也一定是不可平面網絡。更一般的,如果一網絡包含了不可平面網絡
作為其子網絡,則該網絡一定是不可平面網絡。
以上兩個例子給我們展示了兩個不可平面網絡。這兩個不可平面網絡
和
在放置平面過程中,表現出一個共同的特點:僅有一條弧不能放置在平面上。不可平面網絡
和
可以認為是“最小”的不可平面網絡,同時也是不可平面網絡的典型代表。顯然,包含
或Ks(子網絡)的網絡是不可平面的;反過來,不可平面的網絡是否一定包含
或
呢?波蘭數學家庫拉托夫斯基(C.Kuratowski)曾用這兩個網絡來描述平面網絡的特徵,並且對以上問題給出了肯定的回答。