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

Question

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

Здесь у меня есть информация для вас! Это мой код! И до сих пор функция не заканчивается. Если кто-то знает, что такое «Планарный график», пожалуйста, исправьте функцию 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

Answer 1

По поводу планарности ...

Хорошо известные критерии e <= 3v - 6 <a href="http://en.wikipedia.org/wiki/Planar_graph" rel="noreferrer">, указанные Эуллером , упомянутые здесь, говорят о том, что если график плоский, то это условие должно выполняться. Однако не все графики, в которых выполняется это условие, обязательно являются плоскими. Вот почему вам на самом деле нужен алгоритм проверки на плоскостность .

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

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

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

Статья Хопкрафта-Тарьяна является классической, и если вы хотите попытаться реализовать ее, лучшая ссылка, которую я имею, это эта другая статья , которая представляет теорию вместе с реализацией C ++. Это было написано людьми, которые реализовали алгоритм в библиотеке LEDA .

Спустя годы после статьи Хопкрофта-Тарьяна (которая была в 1974 году) были опубликованы другие алгоритмы O (n). Я не знаю много о них, но некоторые использовали деревья PC / PQ. Однако есть один, который я прочитал и нашел очень интересным. Это из-за Бойера и Мирволда, и это с 2004 года. Вы можете найти это здесь . Помимо самого алгоритма, конечно, хорошо в этой статье то, что он содержит строгую историческую справку об алгоритмах теста на плоскость.

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

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

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

Answer 2

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

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

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

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

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

Answer 3

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

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

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

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

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

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

Answer 4

Вы можете попробовать использовать Graphanalyzer (http://grafoanalizator.unick -soft.ru / program / indexen.php ). Или отправьте вопрос автору программы.