Как проверить, является ли график планарным графиком или нет?

Я изучаю Planar Graph и раскраску в С++. Но я не знаю, как установить алгоритм для выполнения этой работы. Кто-нибудь, пожалуйста, помогите мне?

Здесь у меня есть информация для вас! Это мой код! И он все еще имеет функцию, не заканчивающуюся. Если кто-то знает, что такое "планарный график", пожалуйста, исправьте функцию Planar_Graph ниже!: D Большое спасибо!: Х

# 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

Ответы

Ответ 1

Относительно планарности...

Известный критерий e = lt = = 3v - 6 Euller, упомянутый здесь, говорит, что если граф плоский, то это условие должно выполняться, Однако не все графики, в которых выполняется это условие, обязательно являются плоскими. Вот почему вам действительно нужен алгоритм проверки планальности.

Следует заметить, что алгоритмы тестирования планарности нелегко реализовать. Там очень старый, основанный на поиске и удалении подграфов. Я не могу вспомнить оригинальных авторов прямо сейчас, но проблема с их алгоритмом заключается в том, что он имеет сложность O (n³).

Первый алгоритм проверки планарности, который считается эффективным - O (n) в случае - обусловлен Хопкрофтом и Таржаном. Это уже упоминалось здесь в сообщении Инь Чжу. Здесь вы можете найти оригинальную бумагу .

На этот раз проблема с алгоритмом заключалась в том, что многим людям было сложно понять и даже реализовать. Таким образом, есть документы, целью которых является просто уточнение пунктов оригинала. Например, Kocay paper.

Документ Hopcraft-Tarjan является классическим, и если вы хотите попытаться его реализовать, то лучше всего иметь ссылку эту другую статью, которая представляет теорию вместе с реализацией С++. Это было написано людьми, которые реализовали алгоритм в . Помимо самого алгоритма, конечно, хорошо, что в этой статье он содержит строгую историческую ссылку на алгоритмы тестирования планальности.

Совсем недавно я обнаружил другую статью от 2008 года, в которой Тарьян является одним из авторов. Еще не проверили.

Хорошо, если вы устали, просто прочитав этот пост, я предполагаю, что вы не хотите реализовывать свой собственный алгоритм.:) В этом случае я могу порекомендовать некоторые библиотеки С++.

  • Boost.
  • GDToolkit.
  • LEDA.
  • OGDF.
  • GTAD - Это моя собственная библиотека графов (которая, к сожалению, мне не удалось в последнее время работать). Там была реализация алгоритма Хопкрофта-Тарьяна, который я написал на основе этой статьи, о которой я говорил. Поскольку в документе уже есть реальный код, все намного проще.

Ответ 2

Тестирование ненаправленного планарного плана или нет хорошо решено и существуют эффективные алгоритмы. Это на самом деле часть работы Р. Тарьяна 1986 года Тьюринга.

Вы можете сначала проверить это примечание. http://bkocay.cs.umanitoba.ca/G&G/articles/Planarity.pdf

Вы также можете проверить оригинальную бумагу Tarjan и Hopcraft: http://portal.acm.org/citation.cfm?id=321852

Я не знаю, были ли значительные успехи в алгоритмах. Но алгоритм T & H уже очень быстр.

btw, реализация алгоритма очень сложная, и теорема на wiki-странице не дает вам эффективного ключа реализации (хотя и легко).

Ответ 3

Ваш вопрос, по-видимому, охватывает две темы: - График планарный? (Ваш заголовок) - (если так?), как я могу его покрасить (вы не говорите, сколько цветов).

Для первой части В Википедии есть полезный раздел: http://en.wikipedia.org/wiki/Planar_graph

Вы должны прочитать его полностью, но он дает два простых требования для планарности:

Для простого, связного планарного графа с v вершинами и e ребрами, следующие простые критерии планарности держать:

Теорема 1. Если v ≥ 3, то e ≤ 3v - 6,
Теорема 2. Если v > 3 и нет циклов длины 3, то e ≤ 2v - 4.

Вам нужно будет создать структуру данных, способную удерживать вершины и ребра, а затем вам нужно будет определить циклы длины 3 (треугольники).