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