＋设为首页 ＋添加到收藏夹
已知一个图，求它的最大可平面子图并画出一个同构平面图。
图用邻接表存储。
gz！
最笨的方法就是先求一个最小同胚图
然后依次去掉一些边，
再用库拉托夫斯基定理判定。
不过最近看到一篇文章，说是判定图的平面性可以用深度优先搜索，不知道是怎么实现的。
用库拉托夫斯基定理判断很难，不如用D.M.P算法：
定义:设H是G的一个子图。在边集E(G)-E(H)(即在G中而不在H中的边)中定义一个关系“~”：
1 若el，e2∈E(G)-E(H)，e1和e2由一条不在E(H)中的边组成的链μ相连接，且e1是μ的第一条边，e2是p的最后一条边
2。μ的内部顶点不是H的顶点，则e1~e2．
容易验证，关系“~”是一个等价关系．因此可以把边集E(G)-E(H)按这个等价关系分类．由关系“~”的一个等价类超导出来的G-E(H)的子图，称为G中H的片(Piece)，片与H的公共点称为片的附着点(Vertices of attachment)．
D．M．P算法．没G是一个2—连通图，按下列步骤可将一个可平面图嵌入平面，若算法不能进行到底，则G是不可平面图．
1．设G1是G中的一条回路(若G无回路，则必为平
面图)，求Gl的一个平面嵌入G1，．
2．若B(C)-E(G1)为空则停止；若E(G)-E(G1)不为空，求出G中Gl的所有的片B．对每个片B，在G1中求出所有片B的全部附着点的面，这些面的集合记作F(B，G1)．
2.1. 若存在某一片B，使F(B，G1)为空(即G1中没有任何一个面含有B的全部附着点)，于是片B是不可画的，因而G是不可平面团，算法停止．
2.2. 若有片B使|F(B，G1)|＝1，则取片B和面f∈F(B，G1)．
3.若对每一片B均有|F(B，G1)|＞2，则取片B和任一面f∈F(B，G1)．
并且我觉得也可以修改这个算法来求可平面子图：在2.1中，找到F(B，G1)中包含B的附着点最多的面，把附着点不在这个面上的所有边删除。不过不知道这样的结果是不是“最大”。
