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

  • Z时代
  • 2024-01-10
  • 分类：问答

我正在学习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

回答：

关于平面度…

这里提到的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算法的实现，我是根据我提到的那篇论文编写的。由于本文已经提供了真实的代码，因此事情变得容易得多。

以上是 如何检查图是否为平面图？ 的全部内容， 来源链接： utcz.com/qa/424052.html

回到顶部