使用反证法
 
设 彼得森图是平面图，那么按照欧拉公式 R=E-V+2 （R为面，E为边，V为结点）这里E=15,V=10
但是彼得森图每个面至少有5条边，由推论可得 3m<=5*(n-2) 即 15<=5/3*8矛盾，于是彼得森图不是平面图

我为什么现在要学平面图 
 因为顺切HNOI2010遇到了平面图判定…
 
————————————–线割分是我>w<————————————————–
 
首先是一些定义:
 
什么是平面图? 
 对于一个图G=< V,E >,如果能把G画在一个平面上,且画出的图的任意两条边除了V中的节点没有其他交点,则图G为平面图. 
 平面图的面: 
 对于一个平面图,由如果存在一些边围成的区域,且这个区域内不包含这个图的点和边,那么我们称这个区域为该平面图的一个面. 
 比如这里面的红色区域: 
  
 对于包围这个区域的那些边构成的圈,我们称之为这个面的边界.边界的长度,称为这个面的度. 
 我们定义一个面的集合F,于是对于平面图我们可以将其表示为G=< V,E,F > 
 平面图的性质(具体内容及证明见国家集训队2003论文刘才良《平面图在信息学中的应用》):
 
 
 
1.若图G=< V,E,F >为连通平面图,$\sum_{f\in 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属于两个面$f_1,f_2$,那么我们在G*中对点$f_1*,f_2*$连一条边; 
 如果e只属于一个面f,那么在G*中对点$f*,f*$连一条自环边. 
 此时有定理:
 
 
 
1.G的面数等于G*的点数,G与G*的边数相等. 
 2.对于一个s-t平面图,其对偶图中的一个环对应原图中的一个割.
 
 
此时就可以看出我们引入平面图与对偶图有什么作用了. 
 我们都知道求最大流的算法与最短路算法在效率上有不小的差距. 
 当我们看到一个题数据范围极大但是像是最大流,却又担心单纯的写最大流会TLE的时候 
 如果原图满足是平面图,我们不妨先转化为求最小割,然后再建出其对偶图然后求解. 
 对对偶图跑一遍Heap-Dijkstra,利用它求出的距离来做距离标号,构造最大流. 
 具体题目我好像只知道BeiJing2006 狼与兔子QAQ 
 之后单独写题解

 
平面图
 
平面图的概念与性质
 
定义
 
能把图G花在平面上，使得边与边之间没有交叉，称G可以嵌入平面，或称G是可平面图。G的平面嵌入表示的图称为平面图
 
一个平面图G把平面分成若干连通片，这些连通片称为G的一个面或区域，G的面组成的集合用Φ表示
 
  
其中面积有限的区域称为平面图G的内部面，否则，称为外部面
 
 
Jordan曲线
 
  
 
一条连续的，自身不交的，起点和终点重合（封闭的）曲线，平面图中圈中的各条边构成一条Jordan曲线
 
    
这个线是真实存在的，不是你自己想象的···
 
 
Jordan曲线定理：平面上任意简单闭合的曲线J把平面其余部分划分内部和外部
 
 
 
面的次数deg(f)
 
  
面的边界的边数，割边算2次
 
 
性质
 
 
欧拉公式
 
  
 
欧拉公式：G(m,n)是连通平面图，φ是G的面数，则n-m+φ=2
 
    
证明：数学归纳法即可，比较简单，假设n-1成立，然后n那里减去一条非割边，则面数-1，且边数-1，点数不变
 
 
推论1：设G是具有φ个面k个连通分支的平面图，则n-m+φ=k+1
 
 
推论2：设G是具有n个点m条边φ个面的连通平面图，如果对G的每个面f，有：deg(f)≥l≥3，则m≤(n-2)l/(l-2)
 
    
这里有2m=∑deg(f)，也就难怪之前割边要算两次了，因为一条非割边肯定是要作为两个面的边界的
然后证明主要由2m=∑deg(f)和欧拉公式来求
 
 
推论3：设G是具有n(n≥3)个点m条边φ割面的简单平面图，则m≤3n-6
 
推论4：设G说是具有n(n≥3)个点m条边φ割面的简单平面二部图，则：m≤2n-4
 
推论5：设G是具有n个点m条边的连通平面图，若G的每个圈均由长度是l的圈围成，则m(l-2)=l(n-2)
 
    
由次数公式，欧拉公式易得
 
 
推论6：设G是具有n个点m条边的简单平面图，则δ≤5
 
    
若不然，由握手定理会得m>3n-6不可平面
 
 
这里的性质都是 不可平面的判定条件（必要条件，而不充分）
 
    
这里的推论之后可以好好的证明一哈
 
 
 
定理：一个连通图是2连通的，当且仅当它的每个面的边界是圈
 
 
特殊平面图
 
极大平面图
 
 
对于一个简单平面图，在不邻接顶点对间加边，当边数增加到一定数量时，就会变成非平面图
 
  
平面图的极图
只有在简单图的前提下极大平面图才有意义
 
 
K1-K4都是极大平面图
 
  
K5非平面图
 
 
设G是极大平面，则G必然连通，若G阶数的大于等于3，则G无割边
 
 
性质
 
  
 
定理1：设G是n阶简单平面图，则下面命题等价
 
    
G是极大平面图
G每个面的次数是3
G有3n-6条边
 
 
推论：设G是n个点，m条边和φ个面的极大平面图，且n≥3，则φ=2n-4
 
 
 
极大外平面图
 
 
定义
 
  
若一个可平面图G存在一种平面嵌入，使其所有顶点均在某个面的边界上，称该图为外可平面图
 
 
2-连通的外平面图的外面边界是哈密尔顿圈
 
设G是一个连通简单外可平面图，则再G中有一个度数至多是2的顶点
定理2：设G是一个有n(n≥3)个点，且所有点均在外部面上的极大外平面图，则G有n-2个内部面
定理3：设G是一个有n个点，且所有点均在外部面上的外平面图，则G是极大外平面图，当且仅当其外部面的边界是圈，内部面是三角形
 
平面图的对偶图
 
对偶图的定义
 
每个面取做一个点，然后两个面相邻，就连边，相邻几条边，就画几个重边，若是自己有割边，则自己画自环
 
对偶图(G')的性质
 
G’的顶点数等于G的面数
G‘的边数等于G的边数
G’的面数等于G的顶点数
d(v')=deg(f)
对偶图的对偶图就是原图（当且仅当G是连通的）
 
定理5：平面图G的对偶图必然连通
 
因为面之间一定相互邻接，所以对偶图一定连通
 
同构的平面图可以有不同构的对偶图
 
平面图的判定
 
相关概念
 
 
剖分
 
  
一条边上插入一个2度顶点，使一条边分成两条边
 
 
内收缩(简化)
 
  
去掉一个图的2度顶点，使关联它们的两条边合并成一条边
 
 
同胚的
 
  
两图同构，或通过反复剖分和内收缩能变成同构
 
 
初等收缩子图
 
  
对G进行一系列删点，删边或边收缩运算得到的基础简单图
 
 
定理1：图G是可平面的，当且仅当它不含K5和K3,3同胚的子图
 
感觉没啥用
 
定理2：（1）图G是可平面的，当且仅当它的基础简单图是可平面的（2）图G是可平面图当且仅当G的每个块是可平面图
 
定理3：简单图G是可平面图当且仅当它不包含K5或K3,3的初等收缩子图
 
平面性的不变量
 
懒得看，感觉不考···
 
平面图算法
 
定义
 
 
H为G的真子图，E(G)-E(H)被划分成一些类
 
  
G-V(H)的每个分支F以及F连向H的边
e的端点在V(H)上，但e不在E(H)中，其作为一个孤立类
 
 
由H的这些类在G中的边导出子图称为G的H-片段，片段与H的公共顶点称为附着顶点
 
 
冲突
 
  
 
令C是图G的一个圈，G的两个C-片段A和B是冲突的
 
    
1）A和B在C上有三个公共的附着点
2）在C上存在四个顺序排列的顶点v1,v2,v3,v4，其中v1，v3是A的附着点，v2，v4是B的附着点
 
 
C的冲突图
 
    
顶点为G的C-片段，若C的两个片段冲突，则再冲突图中相邻
 
 
 
定理4：图G是可平面的当且仅当对G的每个圈C，C的冲突图是二部图
 
 
F(B,G)={f|f是G的面，且B的附着点均在f的边界上}
 
  
B是片段
F(B,G)是集合
注意是均哦
这里的面是针对C的面，而不是针对G的面
 
 
平面图算法（DMP）
 
 
算法流程
 
  
 
先找一个圈H，然后获取所有的圈片段，之后求F(B,G)，选择一个|F|最小的，在该片段中取一条连接圈中两个附着点的路Pi，把它画进H中，如此重复
 
    
直观点，就是找圈，然后看圈里的那些边(端点附着在圈上)，看它们是属于哪个面的(附着点均在哪个面的边界上，一个边可能可以属于多个面)，然后选择可能性最小的边，把它画上去，当然，一旦画上去，就会多一个面，这也无妨，继续走下去，直到画完，最终就是一个平面图，但也可能遇到有边，哪个面都不属于，直观上反应，它怎么画都会和别的边交叉，此时停止，说明不可平面
具体的看那个例题，基本可以解决所有的问题

在网上看到的一个十分简洁直观的证明，就忍不住想记录下来。
 

 在介绍这个证明之前，让我们先来回顾一下什么是Euler公式。Euler公式是说，在一个由若干顶点和它们之间的一些不相交的边所组成的图中，等式V+F=E+2总成立，其中V表示顶点个数，E表示总的边数，F表示这个图分割出来的区域个数（包括一个“外部区域”，例如一个圆把平面分割为两个区域）。如图1，这个图共有6个顶点、10条边和6个区域，可以看到6+6=10+2是成立的。为了证明这个结论，考虑这个图的任意一个生成树（图1中加粗了的边）。再考虑这个图的“对偶图”：新图的每个顶点代表原图的一个区域，原图的两个区域相邻则在新图上的两个对应顶点之间连一条边（图2中的虚线部分）。接下来，我们找出原图中那些不属于生成树的边界线，把它们在新图中所对应的边加粗（图2中的加粗虚线）。容易看出，加粗的虚线是连通的，因为原图的粗线条是一棵生成树，它没有隔离出任何一块区域；同时呢，加粗虚线是没有环的，否则它将把某个原图的顶点包起来，从而原图中的加粗线条就不可能是生成树了。只需要注意到一棵树的顶点数等于边数加一，我们的结论就直接出来了：原图的顶点数就是Euler公式中的V，它等于原图生成树的边数加一；新图的顶点数就是Euler公式中的F，它等于新生成树的边数加一；而两棵生成树的边数总和正好就是原图中的E。于是呢，我们就得到了V+F=E+2。