c++ - 如何检查图是否为平面图？

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

关于平面性...

众所周知的 e <= 3v - 6 criteria by Euller这里提到的意思是，如果一个图形是平面的，那么这个条件必须成立。但是，并非满足该条件的所有图形都必须是平面的。这就是为什么您实际上需要 planarity test algorithm .

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

第一个被认为是有效的平面性测试算法——在这种情况下为 O(n)——归功于 Hopcroft 和 Tarjan。这一点在殷竹的帖子里已经提到过了。你可以找到原论文here .

这一次，算法的问题在于，很多人觉得它太难理解，甚至难以实现。因此，有些论文的目的只是澄清原始论文的要点。例如，Kocay paper .

Hopcraft-Tarjan 论文是经典的，如果你想尝试实现它，我最好的引用是 this other paper ，其中介绍了该理论以及 C++ 实现。这是由在 LEDA library 中实现算法的人编写的。 .

在 Hopcroft-Tarjan 论文(1974 年)发表多年后，其他 O(n) 算法发表。我对它们了解不多，但有些使用了 PC/PQ 树。然而，有一个，我读了，觉得很有趣。这要归功于 Boyer 和 Myrvold，它是从 2004 年开始的。你可以找到它 here .当然，除了算法本身之外，这篇论文的一个好处是它为平面性测试算法提供了严谨的历史引用。

最近，我发现了一个 another paper从 2008 年开始，Tarjan 是其中的作者之一。还没查。

好吧，如果您只是阅读这篇文章感到厌烦，我假设您不想实现自己的算法。 :) 在这种情况下，我可以推荐一些 C++ 库。

• Boost .
• GDToolkit .
• LEDA .
• OGDF .
• GTAD - 这是我自己的图形库(不幸的是，我最近无法使用它)。有一个 Hopcroft-Tarjan 算法的实现，这是我根据我提到的那篇论文编写的。由于论文已经提供了真实的代码，事情就简单多了。