不可画入：不都在某一个面的周界上，则是不可画入的。
定理：若H的平面嵌入图是G可容纳的，则对H的每一桥B有，F(B,H~)非空。(也是G是平面图的一个必要条件，可用于非平面判定)
3 平面性算法 算法：
------------------------------------- 有5步组成
1 在G中选一回路G1，并求出G1的一个平面嵌入G1~，置 i = 1
2 若E(G)- E(Gi) = 空，则停止。于是Gi~是G的一个平面嵌入，G是平面图。 否则，确定G中Gi中的所有的桥，并对每一座桥B求出它的可画入的面的集合F(B,Gi~)
3 若有一座桥B，使得F(B,Gi~)=空，则停止。根据定理判定为非平面图。 若有一座桥B，使得|F(B,Gi~)|=1，则取{f}=F(B,Gi~)； 否则，从F(B,Gi~)中任选一个面作为f。
4 在桥B中选一条连接Gi上两个附着顶点的通路Pi，Pi?B，置Gi+1=Gi∪Pi，由Pi在Gi~的面f内的一个画法得到Gi+1的一个平面嵌入Gi+1。
5 换i为i+1，转2 -------------------------------------
三、实验的软硬件环境
PC机一台，装有VC++6.0或其它C语言集成开发环境。
四、实验准备
图可以用多种方式来表示，其中邻接矩阵是一种较简单的方式。复习离散数学教材12.5节中关于邻接矩阵的描述。明确一下内容：
1．如何使用邻接矩阵表示图。
2．利用图的邻接矩阵求结点的出度和入度的方法。 3.利用最短路径算法与平面图的算法
五、实验步骤
1．编写一段代码，接收键盘的输入，并以输入的整数对作为边来建立图形的邻接矩阵graph_matrix。
2．根据第一步得到的邻接矩阵计算每个结点的度数()。 一个结点i的出度等于邻接矩阵第i行之和。
deg_out[i] = graph_matrix[i][0]+ graph_matrix[i][1]+ …+graph_matrix[i][n] 一个结点i的入度等于邻接矩阵第i列之和。
deg_in[i] = graph_matrix[0] [i]+ graph_matrix[1] [i]+ …+graph_matrix[n][i] 3.利用DJKSTR最短路径算法与平面图的判定算法,进行实现.
18