如何检查如果一个图是平面图或不？ [英] How to check if a Graph is a Planar Graph or not?
问题描述
我了解的平面图，并在C ++着色。但我不知道装的算法来做好这项工作。有人帮帮我吗？
在这里，我有一些信息给你！这是我的code！而且它还有一个功能没有完成。如果有人知道什么是平面图，请修复下面的Planar_Graph功能！ ：D非常感谢！ ：X
＃定义MAX 100
INT克拉[MAX]
INT TK = 0;
INT my_array [MAX] [MAX]; // 图形
FILE * F;
INT N，M; // M：边，N：顶点
INT指数[MAX]
INT许可[MAX]
INT颜色[MAX] //彩色阵列
INT colors_max;
字符文件名[MAX]
INT输入（字符文件名[MAX]）
{
INT I，J;
F = FOPEN（文件名，R）;
如果（F == NULL）
{
的printf（\ n错误的\ n）;
返回1;
}
其他
{
的printf（文件鬃毛：％S \ N，文件名）;
的printf（内容：\ N）;
的fscanf（F，％D，和放大器; N）;
的fscanf（F，％D，和放大器; M）;
对于（I = 0; I＆n种;我+ +）
{
为（J = 0; J＆n种; J ++）
{
的fscanf（F，％D，和放大器; my_array [I] [J]）;
的printf（％D，my_array [I] [J]）;
}
的printf（\ N）;
}
返回0;
}
}
无效默认（）
{
的for（int i = 0; I＆LT; colors_max;我++）
颜色[我] =我;
}
无效的init（）
{
文件名[0] = NULL;
N = 0;
}
INT Planar_Graph（INT my_array [MAX] [MAX]，INT N，INT M）//这是我的问题
{
/ *的for（int i = 0;我n种;我++）
如果（正＆GT; = 2安培;＆安培;（int）的第（n + 1）*（N-2）/（N-1）＆GT; = m）个
返回1;
}
其他
{
返回0;
} * /
}
INT MAX（）
{
INT最大;
诠释计数= 0;
的for（int i = 0;我n种;我++）
{
计数= 0;
为（诠释J = 0; J＆n种; J ++）
如果（my_array [I] [j]的大于0）
算上++;
如果（MAX＆LT;计数）
最大=计数;
}
返回MAX + 1;
}
无效检查（INT X，int y）对//检查各地
{
INT I;
默认（）;
对于（I = 0; I＆n种;我+ +）
{
如果（my_array [X] [I]！= -1）//如果边缘[X，柯[I]是彩色吨
颜色[my_array [X] [I] = -1; //然后选择颜色[T] = 0
}
对于（I = 0; I＆n种;我+ +）
{
如果（my_array [y]的[I]！= -1）
颜色[my_array [y]的[I] = -1;
}
}
无效着色（）
{
INT吨;
的for（int i = 0;我n种;我++）
为（诠释J = 0; J＆n种; J ++）
如果（my_array [I] [j]的大于0）
{
检查（I，J）;
对于（T = 0; T＆LT; colors_max;吨++）
如果（颜色[T] == T）
{
my_array [I] [J] = T;
my_array [J] [我] = T;
打破;
}
}
}
无效的主要（）
{
如果（输入（input.txt的）！= 1）
{
默认（）;
colors_max = MAX（）;
染色（）;
的printf（\ N结果：\ñ\ N）;
Planar_Graph（my_array，N，M）;
的for（int i = 0;我n种;我++）
{
为（诠释J = 0; J＆n种; J ++）
如果（my_array [I] [j]的大于0）
{
的printf（％C，％C]着色％D \ N，我+'A'，J +'A'，my_array [I] [J]）;
my_array [I] [J] = -1;
my_array [j]的[I] = -1;
}
的printf（\ N）;
}
}
}
输入文件的例子：
10 18
0 1 0 1 1 1 0 0 0 0
1 0 1 0 0 0 0 0 0 0
0 1 0 0 1 0 0 0 0 0
1 0 0 0 1 0 1 1 0 0
1 0 1 1 0 1 1 0 1 0
1 0 0 0 1 0 1 0 1 0
0 0 0 1 1 1 0 1 0 0
0 0 0 1 0 0 1 0 1 1
0 0 0 0 1 1 0 1 0 1
0 0 0 0 0 0 0 1 1 0
对于平面...
众所周知e控制= 3V - 6 标准由Euller 的这里提到说，如果一个图是平面的，则该条件必须持有。然而，不会所有在该条件成立的图形必然是平面的。这就是为什么你真的需要一个平面测试算法。
有一个要注意的是，平面测试算法并不容易实现。有一个非常古老的其中一个是基于子图发现和清除。我不记得了原作者的权利，但他们的算法的问题是，它具有O（n³）的复杂性。
第一平面测试算法被认为是有效的 - 为O（n）的情况下 - 是由于Hopcroft和的Tarjan。这已经在后由殷珠略。你可以在这里找到原皮。
这一次，该算法的问题是，很多人觉得太难以理解，甚至实施。所以有与原纸的只是澄清点的意图论文。例如， Kocay纸。
在Hopcraft-的Tarjan纸是经典，如果你想尝试实现它，最好的参考我已经是这等纸，其中presents理论连同C ++实现。这是写的谁实现的算法在 LEDA库的人。
数年之后，Hopcroft-的Tarjan纸（这是在1974年）后，其它O（n）的算法进行了公布。我不很了解他们，但有些用PC / PQ树。还有一个，不过，这是我读，发现非常有趣。这是由于博耶和Myrvold，它是从2004年你可以找到它这里。当然，除了算法本身，对本文好事是，它提供了关于平面测试算法严格的历史参考。
最近，我发现了一个<一个href="http://www.sciencedirect.com/science?%5Fob=ArticleURL&%5Fudi=B75GV-4T5BWKX-12&%5Fuser=10&%5Frdoc=1&%5Ffmt=&%5Forig=search&%5Fsort=d&%5Fdocanchor=&view=c&%5FsearchStrId=1123969666&%5FrerunOrigin=google&%5Facct=C000050221&%5Fversion=1&%5FurlVersion=0&%5Fuserid=10&md5=c6cbd6708bce2d15e8918c6cf6a1d537">another从2008年纸中的Tarjan是作者之一。还没有检查它。
好吧，如果你只是通过阅读这篇文章累了，我想你不希望实现自己的算法。 :)在这种情况下，我可以推荐一些C ++库。
- 升压。
- GDToolkit 。
- LEDA 。
- OGDF 。
- GTAD - 这是我自己的图形库（其中，不幸的是，我一直没能在其上工作，最近）。还有的Hopcroft-的Tarjan算法，这是我写的基础上的论文中，我提到的实现。由于该文件已经提供了真正的code，事情变得更加简单。
I'm learning about the Planar Graph and coloring in c++. But i don't know install the algorithm to do this work. Someone please help me?
Here i have some information for you! This is my code! And it still has a function does not finish. If someone know what is a "Planar Graph", please fix the Planar_Graph function below! :D thanks so much! :x
# define MAX 100
int kt[MAX];
int tk=0;
int my_array[MAX][MAX]; // Graph
FILE *f;
int n,m; //m: Edge, n: Vertex
int index[MAX];
int ke[MAX];
int Color[MAX] ; //Color Array
int colors_max;
char filename[MAX];
int input(char filename[MAX])
{
int i,j;
f = fopen(filename,"r");
if (f== NULL)
{
printf("\n Error \n");
return 1;
}
else
{
printf("File mane: %s \n",filename);
printf("Content :\n");
fscanf(f,"%d",&n);
fscanf(f,"%d",&m);
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
fscanf(f,"%d",&my_array[i][j]);
printf("%d ",my_array[i][j]);
}
printf("\n");
}
return 0;
}
}
void Default()
{
for(int i=0;i<colors_max;i++)
Color[i]= i;
}
void Init()
{
filename[0]=NULL;
n = 0;
}
int Planar_Graph(int my_array[MAX][MAX],int n, int m) // This is my problem
{
/* for(int i=0;i<n;i++)
if(n>=2 && (int)(n+1)*(n-2)/(n-1)>=m)
return 1;
}
else
{
return 0;
} */
}
int max()
{
int max;
int count=0;
for(int i=0;i<n;i++)
{
count = 0;
for(int j=0;j<n;j++)
if (my_array[i][j] > 0)
count++ ;
if (max < count)
max = count;
}
return max+1;
}
void Check(int x,int y) // Check around
{
int i;
Default();
for(i=0;i<n;i++)
{
if (my_array[x][i] != -1) // if edge [x,ke[i]] is color t
Color[my_array[x][i]] = -1; // then Color[t] = 0
}
for(i=0;i<n;i++)
{
if (my_array[y][i] != -1)
Color[my_array[y][i]] = -1;
}
}
void Coloring()
{
int t;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if (my_array[i][j] > 0)
{
Check(i,j) ;
for(t=0;t < colors_max;t++)
if (Color[t] == t)
{
my_array[i][j] = t;
my_array[j][i] = t;
break;
}
}
}
void main()
{
if(input("input.txt")!=1)
{
Default();
colors_max = max() ;
Coloring();
printf("\n Result:\n\n");
Planar_Graph(my_array,n,m);
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
if (my_array[i][j]>0)
{
printf(" %c,%c] coloring %d \n",i + 'A',j + 'A',my_array[i][j]) ;
my_array[i][j] = -1;
my_array[j][i] = -1;
}
printf("\n") ;
}
}
}
The input file example:
10 18
0 1 0 1 1 1 0 0 0 0
1 0 1 0 0 0 0 0 0 0
0 1 0 0 1 0 0 0 0 0
1 0 0 0 1 0 1 1 0 0
1 0 1 1 0 1 1 0 1 0
1 0 0 0 1 0 1 0 1 0
0 0 0 1 1 1 0 1 0 0
0 0 0 1 0 0 1 0 1 1
0 0 0 0 1 1 0 1 0 1
0 0 0 0 0 0 0 1 1 0
Regarding planarity...
The well known e <= 3v - 6 criteria by Euller mentioned here says that if a graph is planar, then that condition must hold. However, not all graphs in which that condition holds are necessarily planar. That is why you actually need a planarity test algorithm.
A thing to notice is that planarity testing algorithms are not easy to implement. There's a very old one which is based on subgraphs finding and removal. I can't remember the original authors right now, but the problem with their algorithm is that it has O(n³) complexity.
The first planarity test algorithm considered to be efficient - O(n) in the case - is due to Hopcroft and Tarjan. This was already mentioned here in the post by Yin Zhu. You can find the original paper here.
This time, the problem with the algorithm was that many people found it too hard to understand and even to implement. So there are papers with the intention of just clarifying points of the original paper. For instance, the Kocay paper.
The Hopcraft-Tarjan paper is classic and if you want to try to implement it, the best reference I have is this other paper, which presents the theory together with a C++ implementation. That was written by the people who implemented the algorithm in the LEDA library.
Years later after the Hopcroft-Tarjan paper (which was in 1974), others O(n) algorithms were published. I don't know much about them, but some used PC/PQ trees. There is one, however, which I read and found very interesting. It's due to Boyer and Myrvold and it's from 2004. You can find it here. Besides the algorithm itself, of course, a good thing about this paper is that it provides a rigorous historical reference about planarity test algorithms.
Very recently, I discovered a another paper from 2008 in which Tarjan is one of the authors. Haven't checked it yet.
Well, if you got tired just by reading this post, I assume you don't want to implement your own algorithm. :) In this case, I can recommend some C++ libraries.
- Boost.
- GDToolkit.
- LEDA.
- OGDF.
- GTAD - This is my own graph library (which, unfortunately, I haven't been able to work on it lately). There's an implementation of the Hopcroft-Tarjan algorithm, which I wrote based on that paper I mentioned. Since the paper already provides real code, things are a lot easier.
这篇关于如何检查如果一个图是平面图或不？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
