如何检查图形是否为平面图? [英] How to check if a Graph is a Planar Graph or not?
问题描述
我正在学习 C++ 中的平面图和着色.但我不知道安装算法来完成这项工作.有人请帮我吗?
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?
这里有一些信息给你！这是我的代码！而且它还有一个功能没有完成.如果有人知道什么是Planar Graph"，请修复下面的Planar_Graph 函数！:D 非常感谢！:x
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("
Error
");
return 1;
}
else
{
printf("File mane: %s
",filename);
printf("Content :
");
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("
");
}
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("
Result:
");
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
",i + 'A',j + 'A',my_array[i][j]) ;
my_array[i][j] = -1;
my_array[j][i] = -1;
}
printf("
") ;
}
}
}
输入文件示例:
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 的标准 在这里提到，如果图是平面图，那么该条件必须成立.但是，并非所有满足该条件的图都必须是平面图.这就是为什么您实际上需要一个平面性测试算法.
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.
需要注意的是，平面度测试算法并不容易实现.有一个非常古老的基于子图的查找和删除.我现在不记得原作者了，但他们算法的问题是它的复杂度为 O(n³).
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.
第一个被认为有效的平面度测试算法 - 在这种情况下为 O(n) - 归功于 Hopcroft 和 Tarjan.这一点在殷珠的帖子里已经提到了.您可以在此处找到原始论文.
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.
这一次，算法的问题是很多人觉得太难理解，甚至难以实现.所以有些论文只是为了澄清原始论文的要点.例如，Kocay 论文.
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.
Hopcraft-Tarjan 论文很经典，如果你想尝试实现它，我最好的参考是 这篇另一篇论文，其中介绍了该理论以及 C++ 实现.这是由在 LEDA 库 中实现算法的人编写的.
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.
在 Hopcroft-Tarjan 论文(1974 年)发表多年后，其他 O(n) 算法发表.我对它们了解不多，但有些使用了 PC/PQ 树.然而，有一个我读过并发现非常有趣.这是 Boyer 和 Myrvold 的作品，是 2004 年的.你可以找到它 这里.当然，除了算法本身，本文的一个好处是它为平面度测试算法提供了严谨的历史参考.
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.
好吧，如果你只是读了这篇文章就累了，我假设你不想实现自己的算法.:) 在这种情况下，我可以推荐一些 C++ 库.
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.
- 提升.
- GDToolkit.
- LEDA.
- OGDF.
- GTAD - 这是我自己的图形库(不幸的是，我无法工作最近在做).有一个 Hopcroft-Tarjan 算法的实现，这是我根据我提到的那篇论文编写的.由于论文已经提供了真实的代码，所以事情要容易得多.
- 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屋！
