正文之前
在圖論中蹂空，平面圖是可以畫(huà)在平面上并且使得不同的邊可以互不交疊的圖膏燕。而如果一個(gè)圖無(wú)論怎樣都無(wú)法畫(huà)在平面上闸衫，并使得不同的邊互不交疊献丑，那么這樣的圖不是平面圖末捣，或者稱為非平面圖。?——Wikipedia
在這篇文章中创橄，我們介紹兩個(gè)方面內(nèi)容：
- 平面圖
- 涂色問(wèn)題（四色定理）
正文
平面圖
- 簡(jiǎn)介
- 判斷（歐拉公式）
- 串聯(lián)約減
- 同胚
- 庫(kù)拉托夫斯基(Kuratowski)定理
1. 簡(jiǎn)介
在一個(gè)平面畫(huà)出一個(gè)圖箩做，如果圖的每條邊都互不相交，則稱這個(gè)圖為平面圖
在完全圖的文章中妥畏，介紹了K4邦邦，這里我們以此為例
本來(lái)以為K4不會(huì)是平面圖，會(huì)有兩條邊相交醉蚁，但是我們做個(gè)變形燃辖，將一條邊畫(huà)出去，就將K4畫(huà)成了平面圖
2. 判斷
在K4內(nèi)网棍，圖被分為4個(gè)面(face of region)：A, B, C, D
K4內(nèi)共有：
- 4個(gè)面(f)
- 4個(gè)結(jié)點(diǎn)(v)
- 6條邊(e)
為了判斷一個(gè)圖是否為平面圖黔龟，我們使用
歐拉公式：f = e - v + 2 （面數(shù) = 邊數(shù) - 結(jié)點(diǎn)數(shù) + 2）
3. 串聯(lián)約減
在一個(gè)圖中，有一個(gè)度為2的結(jié)點(diǎn)和兩條邊(v, v1)和(v, v2)滥玷，而且v1 ≠ v2氏身，則稱(v, v1)和(v, v2)是串聯(lián)的
串聯(lián)約減就是將結(jié)點(diǎn)v從圖中刪去，用(v1,v2)代替(v, v1)和(v, v2)
上圖就采用串聯(lián)約減刪去結(jié)點(diǎn)e惑畴，邊(a, e)和(e, c)被替換為(a, c)
4. 同胚
如果圖G1可以通過(guò)串聯(lián)約減（一步或多步）變?yōu)榕cG2同構(gòu)的圖蛋欣，則稱G1和G2是同胚的，反之也是
5. 庫(kù)拉托夫斯基定理
一個(gè)圖G是平面圖當(dāng)且僅當(dāng)G中不包含與K5或者K3,3同胚的子圖
可用庫(kù)拉托夫斯基定理判斷圖G是不是平面圖如贷，舉個(gè)書(shū)本中的例子
移除圖中的邊(a, b),(e, f),(g, h)陷虎，經(jīng)過(guò)串聯(lián)約減之后，就將圖變?yōu)榱薑3,3杠袱，所以不是平面圖
涂色問(wèn)題
- 簡(jiǎn)介
- 四色定理
1. 簡(jiǎn)介
給出一個(gè)平面圖泻红，給圖的每個(gè)面涂上顏色，使得每?jī)蓚€(gè)相鄰的面的顏色不同霞掺，一共需要多少種顏色谊路？
這張圖用了四種顏色涂了五個(gè)面
2. 四色定理
四色定理是一個(gè)著名的數(shù)學(xué)定理：如果在平面上劃出一些鄰接的有限區(qū)域缠劝，那么可以用四種顏色來(lái)給這些區(qū)域染色秉馏，使得每?jī)蓚€(gè)鄰接區(qū)域染的顏色都不一樣??????????????????——Wikipedia
用一個(gè)復(fù)雜一點(diǎn)的圖試試
關(guān)于平面圖的介紹就到這里了，謝謝大家脱羡！
