Как проверить, является ли график плоским или нет?
Я изучаю планарный график и раскраску в 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
4 ответа
Что касается планарности...
Упомянутые здесь Euller хорошо известные критерии e <= 3v - 6 говорят о том, что если граф плоский, то это условие должно выполняться. Однако не все графы, в которых выполняется это условие, обязательно являются плоскими. Вот почему вам действительно нужен алгоритм теста на плоскостность.
Следует отметить, что алгоритмы тестирования на плоскостность нелегко реализовать. Есть очень старая, основанная на поиске и удалении подграфов. Я не могу вспомнить оригинальных авторов прямо сейчас, но проблема с их алгоритмом состоит в том, что он имеет O(n³) сложность.
Первый алгоритм проверки на плоскостность, который считается эффективным (в данном случае O(n)), принадлежит Хопкрофту и Тарьяну. Об этом уже упоминалось здесь в посте Инь Чжу. Вы можете найти оригинальную статью здесь.
На этот раз проблема с алгоритмом заключалась в том, что многим людям было трудно его понять и даже реализовать. Таким образом, есть бумаги с намерением просто прояснить пункты оригинальной статьи. Например, бумага Kocay.
Статья Хопкрафта-Тарьяна является классической, и если вы хотите попытаться реализовать ее, лучшая ссылка, которую я имею, - это другая статья, которая представляет теорию вместе с реализацией C++. Это было написано людьми, которые реализовали алгоритм в библиотеке LEDA.
Спустя годы после статьи Хопкрофта-Тарьяна (которая была в 1974 году) были опубликованы другие алгоритмы O(n). Я не знаю много о них, но некоторые использовали деревья PC/PQ. Однако есть один, который я прочитал и нашел очень интересным. Это из-за Бойера и Мирволда, и это с 2004 года. Вы можете найти это здесь. Помимо самого алгоритма, конечно, хорошая вещь в этой статье состоит в том, что он предоставляет строгую историческую справку об алгоритмах теста на плоскость.
Совсем недавно я обнаружил еще одну статью 2008 года, в которой Тарьян является одним из авторов. Еще не проверял.
Что ж, если вы устали, просто прочитав этот пост, я предполагаю, что вы не хотите реализовывать свой собственный алгоритм.:) В этом случае я могу порекомендовать некоторые библиотеки C++.
- Повышение
- GDToolkit.
- ЛЕДА.
- OGDF.
- GTAD - это моя собственная библиотека графов (которая, к сожалению, я не смог над ней поработать в последнее время). Есть реализация алгоритма Хопкрофта-Тарьяна, которую я написал на основе упомянутой мной статьи. Поскольку статья уже предоставляет реальный код, все намного проще.
Тестирование неориентированного графа на плоскости или нет хорошо решено, и существуют эффективные алгоритмы. Это на самом деле часть работы Р. Тарьяна в 1986 году.
Вы можете сначала проверить эту заметку. http://bkocay.cs.umanitoba.ca/G&G/articles/Planarity.pdf
Вы также можете проверить оригинальную работу Тарьяна и Хопкрафта: http://portal.acm.org/citation.cfm?id=321852
Я не знаю, были ли существенные улучшения в алгоритмах. Но алгоритм T&H уже очень быстрый.
Кстати, реализовать алгоритм очень сложно, и теорема на вики-странице не дает эффективного ключа к реализации (хотя и проста).
Похоже, ваш вопрос охватывает две темы: - является ли график плоским? (ваше название) - (если так?) как я могу его покрасить (вы не говорите, сколько цветов).
Для первой части Википедии есть полезный раздел: http://en.wikipedia.org/wiki/Planar_graph
Вы должны прочитать это полностью, но это дает два простых требования к планарности:
Для простого связного плоского графа с v вершинами и e ребрами выполняются следующие простые критерии плоскостности:
Теорема 1. Если v ≥ 3, то e ≤ 3v - 6;
Теорема 2. Если v > 3 и циклов длины 3 нет, то e ≤ 2v - 4.
Вам нужно будет создать структуру данных, способную удерживать вершины и ребра, а затем вам нужно будет определить циклы длины 3 (треугольники).
Вы можете попробовать использовать Graphanalyzer ( http://grafoanalizator.unick-soft.ru/program/indexen.php). Или отправьте вопрос автору программы.