2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Создать все неизоморфные $n$-вершинные макс.плоские графы
Сообщение18.12.2016, 14:10 


13/05/14
476
Здравствуйте, уважаемые форумчане.
Пожалуйста помогите решить следующую проблему:
Цитата:
мне надо найти (если есть готовые) или сгенерировать список всех неизоморфных $n$–вершинных плоских 2-деревьев (триангуляций выпуклого многоугольника) для разных значений $n=3,4,5,6,7,8,9,10,11,12,13,14,15,16,17$. Эти графы являются максимальными внешнеплоскими графами (МВП графами).
Каждый такой граф должен быть создан в виде списка ребер, или в виде списка смежностей, воспринимаемых СКМ Matematica (пользуюсь пятой версией).

Я уже сам сгенерировал с помощью Mathematica файлы со всеми неизоморфными МВП графами для $n=3,4,5,6,7,8,9$. Но надо еще создать хотя бы для $n=10,11,12$.
О больших $n$ я и не заикаюсь (хотя нужно и побольше) потому, что с ростом $n$ число таких графов стремительно возрастает.
Для $n=6$ таких графов $12$, для $n=7$ их уже $27$, для $n=8$ их $82$, для $n=9$ их $228$ и т.д. в соответствии с последовательностью A000207 OEIS.

Эти графы мне нужны для проведения расчетных экспериментов, результаты которых я планирую поместить в своей статье. Прошу помочь мне найти такие графы или алгоритм (программу) для их генерации. Мне важен результат, сам алгоритм меня не интересует (вернее интересует ТОЛЬКО как средство получения МВП графов).
Естественно, тем кто мне поможет, я буду очень благодарен и в статье обязательно укажу на его авторство (алгоритма, программы) или поблагодарю за предоставленные материалы (графы).

(Оффтоп)

Если кого интересует, готовых данных в интернете я не нашел, не нашел и нужных мне алгоритмов. Находил много алгоритмов генерации скобочных последовательностей и двоичных деревьев. Нашел алгоритм генерации скобочной последовательности по заданной. Сделал программу генерации всех таких последовательностей, программу генерации двоичного дерева и генерации МВП графа по скобочной последовательности… Проблема в том, что таких скобочных последовательностей на порядки больше (число Каталана), чем самих неизоморфных МВП графов, поэтому очень трудно выбрать неизоморфные графы...

У кого есть СКМ Mathematica старших версий, может там возможно генерировать такие МВП графы автоматически? Слышал также, что NAUTY также может создавать неизоморные графы разных классов. Поэтому прошу и тех, у кого есть доступ к NAUTY посмотреть есть ли там возможность генерации неизоморфных МВП графов.

P.S. Если разместил не в том разделе, то прошу уважаемых модераторов перенести в нужное место
___________
Поскольку тема не относится к программированию на универсальных ЯВУ, то переместил пока из «Программирования» в корень СS. Возможно, позже кто-то из модераторов перенесет в «Околонаучный софт». / GAA

 Профиль  
                  
 
 Re: Создать все неизоморфные $n$-вершинные макс.плоские графы
Сообщение18.12.2016, 15:16 


13/05/14
476
Ну вот забыл написать. А редактировать уже невозможно. :-(
В интернете нашел интересную статью китайского математика HU Guanzhang “Catalan Number and Enumeration of Maximal Outerplanar Graphs” опубликованную в журнале
Tsinghua science and technology 2000.Vol. 5, No. 1,pp. pp. l09--114.
В ней как раз (с многочисленными рисунками) определяется число неизоморфных триангуляций выпуклого многоугольника. Может быть кому-нибудь удастся по этой статье разработать алгоритм для генерации МВП графов. Статья написана очень плотно и на английском языке, в котором я, увы, совсем не разбираюсь. :oops:

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 2 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group