我為什么現在要學平面圖
因為順切HNOI2010遇到了平面圖判定…

————————————–線割分是我>w<————————————————–

首先是一些定義:

什么是平面圖?
對于一個圖G=< V,E >,如果能把G畫在一個平面上,且畫出的圖的任意兩條邊除了V中的節點沒有其他交點,則圖G為平面圖.
平面圖的面:
對于一個平面圖,由如果存在一些邊圍成的區域,且這個區域內不包含這個圖的點和邊,那么我們稱這個區域為該平面圖的一個面.
比如這里面的紅色區域:

對于包圍這個區域的那些邊構成的圈,我們稱之為這個面的邊界.邊界的長度,稱為這個面的度.
我們定義一個面的集合F,于是對于平面圖我們可以將其表示為G=< V,E,F >
平面圖的性質(具體內容及證明見國家集訓隊2003論文劉才良《平面圖在信息學中的應用》):

1.若圖G=< V,E,F >為連通平面圖, ∑f∈F?d(f)??=2|E|
2.若圖G=< V,E,F >為連通平面圖, |V|?|E|+|F|=2

當然,對于不連通的平面圖,我們可以把它分解成幾個聯通塊,然后對每個聯通塊這兩個性質都成立(這是很顯然的),所以就可以得到對不連通的平面圖的一些性質.這里我不再贅述.
從上面兩個性質又可以得到如下推論:

對于給定的連通簡單平面圖G=< V,E,F >,若|V|>=3,則|E|<=3|V|-6,|F|<=2|V|-4

原文的第二個推論我覺得好像有問題我不貼了,反正第二個好像也沒用
第一個推論的作用就是告訴我們E的數量級是O(|V|)的…

平面圖的判定(才不會說我就是因為這個才學平面圖的):
做法轉自這里

哈密頓回路會連成一個環，這個圖必定被分成兩部分，如果兩條邊相交無論同時在內還是在外都會相交，只有一條在環內一條在外才行——二分圖！首先判斷出那些邊不再回路上然后把有矛盾的邊連邊利用染色法判斷能否構成二分圖，二分圖的成立決定了平面圖的成立。

接下來是重點:平面圖與對偶圖
定義:對于一個平面圖,如果它有源點匯點,我們稱之為s-t平面圖.
每個平面圖都能建出相應的對偶圖.
對于一個平面圖G,其對偶圖為G*.G*中的一個點,對應原圖G中的一個面.
對于G中的每條邊e,如果e屬于兩個面 f1,f2 ,那么我們在G*中對點 f1?,f2? 連一條邊;
如果e只屬于一個面f,那么在G*中對點 f?,f? 連一條自環邊.
此時有定理:

1.G的面數等于G*的點數,G與G*的邊數相等.
2.對于一個s-t平面圖,其對偶圖中的一個環對應原圖中的一個割.

此時就可以看出我們引入平面圖與對偶圖有什么作用了.
我們都知道求最大流的算法與最短路算法在效率上有不小的差距.
當我們看到一個題數據范圍極大但是像是最大流,卻又擔心單純的寫最大流會TLE的時候
如果原圖滿足是平面圖,我們不妨先轉化為求最小割,然后再建出其對偶圖然后求解.
對對偶圖跑一遍Heap-Dijkstra,利用它求出的距離來做距離標號,構造最大流.
具體題目我好像只知道BeiJing2006 狼與兔子QAQ
之后單獨寫題解

總結

以上是生活随笔為你收集整理的【平面图理论】平面图学习笔记的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。