如何检查图表是否是平面图？

Question

我正在学习平面图和c ++着色.但我不知道安装算法来做这项工作.有人请帮帮我？

在这里,我有一些信息给你!这是我的代码!它仍然有一个功能没有完成.如果有人知道什么是"平面图",请修复下面的Planar_Graph函数!:D非常感谢!: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") ;
         }

    }

}

输入文件示例:

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

Answer 1

关于平面性......

Euller在这里提到的众所周知的e <= 3v - 6 标准说,如果图是平面的,那么这个条件必须成立.然而,并非所有条件都适用的图形必然是平面的.这就是你真正需要平面度测试算法的原因.

值得注意的是,平面度测试算法并不容易实现.有一个非常古老的基于子图查找和删除.我现在不记得原作者了,但他们算法的问题在于它具有O(n³)复杂度.

被认为是高效的第一个平面度测试算法 - 案例中的O(n) - 归因于Hopcroft和Tarjan.这在尹朱的帖子中已经提到了.你可以在这里找到原始论文.

这一次,算法的问题在于许多人发现它太难理解甚至实现.因此,有些论文旨在澄清原始论文的要点.例如,Kocay论文.

Hopcraft-Tarjan论文是经典的,如果你想尝试实现它,我最好的参考是另一篇论文,它将理论与C++实现结合起来.这是由在LEDA库中实现算法的人编写的.

多年后,在Hopcroft-Tarjan论文(1974年)之后,其他O(n)算法被发表.我对它们了解不多,但有些人使用的是PC/PQ树.然而,有一个我读过并发现非常有趣.它归功于Boyer和Myrvold,它来自2004年.你可以在这里找到它.当然,除了算法本身之外,本文的一个好处是它提供了关于平面度测试算法的严格历史参考.

最近,我发现了2008年的另一篇论文,其中Tarjan是其中一位作者.尚未检查过.

好吧,如果你只是通过阅读这篇文章感到厌倦,我认为你不想实现自己的算法.:)在这种情况下,我可以推荐一些C++库.

• 提升.
• GDToolkit.
• LEDA.
• OGDF.
• GTAD - 这是我自己的图形库(遗憾的是,我最近无法对其进行处理).有一个Hopcroft-Tarjan算法的实现,我根据我提到的那篇论文写的.由于该论文已经提供了真实的代码,因此事情要容易得多.

Answer 2

测试平面或非平面的无向图是很好地解决的,并且存在有效的算法.它实际上是R. Tarjan 1986年图灵奖的一部分.

您可以先查看此注释.http://bkocay.cs.umanitoba.ca/G&G/articles/Planarity.pdf

您可能还想查看Tarjan和Hopcraft的原始论文:http://portal.acm.org/citation.cfm？id = 321852

我不知道算法是否有重大进展.但是T&H的算法已经很快了.

顺便说一句,实现算法是非常困难的,维基页面中的定理并没有给你一个有效的实现线索(虽然简单).