15

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

4 回答 4

42

关于平面...

Euller在这里提到的众所周知的 e <= 3v - 6标准说，如果图形是平面的，则该条件必须成立。但是，并非所有符合该条件的图都必须是平面的。这就是为什么您实际上需要一个平面性测试算法。

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

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

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

Hopcraft-Tarjan 论文是经典的，如果你想尝试实现它，我最好的参考是this other paper，它介绍了理论和 C++ 实现。那是由在LEDA 库中实现该算法的人编写的。

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

最近，我发现了另一篇2008 年的论文，其中 Tarjan 是作者之一。还没有检查它。

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

  • 升压。
  • GD工具包。
  • 发光二极管。
  • OGDF。
  • GTAD - 这是我自己的图形库（不幸的是，我最近无法使用它）。有一个 Hopcroft-Tarjan 算法的实现，这是我根据我提到的那篇论文编写的。由于论文已经提供了真实的代码，事情就容易多了。
于 2009-12-06T12:27:29.887 回答
6

测试无向图平面与否已得到很好的解决，并且存在有效的算法。它实际上是 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的算法已经非常快了。

顺便说一句，实现该算法非常困难，维基页面中的定理并没有给你一个有效的实现线索（虽然很容易）。

于 2009-12-06T08:17:51.090 回答
1

您的问题似乎涵盖两个主题：-图形是平面的吗？（你的标题） - （如果是的话？）我怎样才能给它上色（你没有说有多少种颜色）。

对于第一部分，维基百科有一个有用的部分： http ://en.wikipedia.org/wiki/Planar_graph

您应该完整阅读它，但它对平面性提出了两个简单的要求：

对于具有 v 个顶点和 e 个边的简单连接平面图，以下简单平面性标准成立：

定理 1.如果 v ≥ 3 则 e ≤ 3v - 6；
定理 2.如果 v > 3 且不存在长度为 3 的环，则 e ≤ 2v - 4。

您将需要创建一个能够保存顶点和边的数据结构，然后您将需要能够确定长度为 3（三角形）的循环。

于 2009-12-06T08:17:11.280 回答
0

您可以尝试使用 Graphanalyzer（http://grafoanalizator.unick-soft.ru/program/indexen.php）。或将问题发送给程序的 Autor。

于 2010-02-15T21:49:07.803 回答