1)Как построить плоскую карту с прямолинейными границами по заданной произвольно
матрице смежности двойственного графа? Т.е надо
а)сформулировать критерии планарности и алгоритм проверки планарности графа
б)в случае планарности реализовать его укладку с прямолинейными ребрами в заданном прямоугольнике.
на выходе алгоритма должны быть координаты каждой вершины.
Однозначно ли такое решение?
----------------------------------------------------------------------
Мне известны только необходимые условия планарности типа
1)если граф содержит двудольный подграф K3,3 или полный подграф K5, то он не планарен (теорема Куратовского)
2)r>3(n-2), r- число ребер, n-число вершин.
4)достаточное усл.планарности: r<=n+2
Применение которых не дает полного ответа на вопрос планарности.
А также неизвестен алгоритм укладки
2)Частные случаи прямоугольных и треугольных граней1)в лабиринтах с прямоугольным контуром матрица смежности A(k,k) имеет ненулевую
только 1-ю и n-наддиагонали (и поддиагонали). 0 на 1 диагонали соответствуют вертикальным стенкам, а 0 на m-диагонали – горизонтальным стенкам. При этом n – делитель k (k=m*n)
2)лабиринты с ступенчато-прямоугольным контуром могут быть получены из аналогичного с прямоугольным контуром путем изоляции нескольких клеток. (Изолированной вершине соответствует 0-строка и 0-столбец матрицы смежности).В частности, изоляцией некоторой внутренней группы клеток может быть получена замкнутая внутренняя стенка. См
На рис.1 –лабиринт с прямоугольным контуром без перегородок . На рис 2 лабиринт не прямоугольного контура вместе с их двойственными графами. Там же их матрицы смежности
Поэтому все многообразие таких лабиринтов описывается матрицами смежности с 2 ненулевыми наддиагоналями
