|
Имеется граф с 10 вершинами и 26 ребрами. Необходимо вычислить род графа. Согласно критерию планарности Понтрягина-Куратовского я определил, что граф не является планарным. Следовательно, его род равен 1 или больше. С помощью какого алгоритма можно вычислить род графа? Какой математический пакет может вычислить эту величину? В пакете Wolfram Mathematica 10 я не смог найти данный функционал. И, наконец, с помощью какой программы можно визуализировать род графа (например, нарисовать граф на торе для графа рода 1)? задан 13 Ноя '14 21:14 
DarkGenius
показано 5 из 8
показать еще 3
|
|
Вот пример укладки на торе без одного ребра. Рассматриваем квадрат, в углу которого находится 4. На верхней стороне, слева направо, идут 1, 2, 6, 3. Их копии идут также на нижней стороне. На левой стороне, сверху вниз: 8, 9. Их копии есть справа. Все соединения по контуру -- это рёбра. Проводим соединения 8-1, 8-2 слева сверху, потом 4-6, 4-2 справа сверху. Справа внизу проводим линии 9-3 и 9-6. Внутри квадрат рисуем треугольник 5-7-10 с тремя сторонами, где 10 смотрит вверх, 5 находится левее, а 7 правее. Соединяем 7 с нижними 1, 2, 6 и с 8 на правой стороне. Соединяем 5 с 4 и 9 на левой стороне. Наконец, 10 соединим с 2 наверху и 9 слева. Здесь будут все соединения кроме 3-10. Из этого следует, что род графа не больше двух. Равен ли он 1 или 2, я не знаю. Пример строился чисто методом проб и ошибок. отвечен 14 Ноя '14 12:03 
falcao @falcao: благодарю за построение. Попробую еще поиграться с различными конфигурациями, вдруг удастся уложить все ребра. Интересно, как можно оптимизировать построение: например, какие вершины лучше размещать на сторонах квадрата, а какие - в центре?
(14 Ноя '14 13:06)
DarkGenius
@DarkGenius: я помещал 4 в угол, так как у неё самая большая валентность. На границе оказались те точки, для которых существуют соединения по рёбрам, но это расположение, скорее всего, не единственное. Можно поварьировать, чтобы внутри оказались 1, 3, 5. У них валентности самые маленькие. Если укладка на торе имеется, то у неё, скорее всего, должно быть 12 треугольных граней и 4 четырёхугольных. Это следует из формулы Эйлера для торических графов. Я также смотрел на полные подграфы из 4 вершин. Их имеется два: на 1248 и 3469. Вершина 4 общая.
(14 Ноя '14 13:25)
falcao
@falcao: что подразумевается под "формулой Эйлера для торических графов"?
(14 Ноя '14 14:32)
DarkGenius
v-e+f=0, где v=10 -- число вершин, e=26 -- число рёбер, f -- число граней торического многогранника, при условии возможности укладки на торе. При этом f=16.
(14 Ноя '14 18:36)
falcao
@falcao: да, полезная формула. В более общем виде в правой части равенства стоит 2-2g, где g-род поверхности, на которую укладываем (количество "ручек" по сути). Я бы воспользовался этой формулой, но алгоритмически сложно вычислить f.
(14 Ноя '14 20:56)
DarkGenius
@falcao: как точно построить укладку либо доказать, что укладка на торе невозможна?
(14 Ноя '14 21:13)
DarkGenius
@DarkGenius: здесь как раз f вычисляется точно, если мы исследуем тор. Больше ничего исследовать при помощи этой формулы не нужно, так как на сфере с двумя ручками всё укладывается. Можно к условию f=16 (это заведомо так!) добавить пару слов. Пусть среди граней имеется k не треугольных. Их сумма периметров >=4k. У треугольников она равна 3(16-k). Сумма периметров граней -- это 52: удвоенное число рёбер. Отсюда k<=4. Основной случай k=4, то есть 12 треугольных и четыре 4-угольных грани. Его и надо пытаться реализовать в первую очередь.
(14 Ноя '14 21:14)
falcao
@DarkGenius: мне не совсем понятен смысл Вашего последнего вопроса. теоретически можно перебрать все способы укладки. Их имеется конечное число с точностью до изотопии. Сколько тут вариантов, я не знаю. Скорее всего, много. Компьютеру это может быть под силу, а может и не быть -- всё зависит от того, хорошо ли организован перебор. Есть шанс построить пример вручную, тогда это снимет вопрос. А вот если граф на самом деле имеет род 2, то доказать это может быть не просто. Проблема вычисления рода полного графа (а он просто устроен) стояла в математике лет около 100.
(14 Ноя '14 21:22)
falcao
показано 5 из 8
показать еще 3
|
|
1) На плоскости можно изобразить граф с 24 рёбрами и 10 вершинами. Для этого надо поставить внутрь каких-нибудь четырёх граней плоского графа октаэдра по одной точке и соединить каждую с вершиной этой грани. 2) А дальше приставляем одну ручку к двум граням данного графа с непересекающимися границами и соединить пары соответствующих вершин так, чтоб рёбра не пересекались (это, очевидно, возможно). У этого графа будет даже 27 рёбер, а значит, у исходного род не больше 1. отвечен 13 Ноя '14 21:37 
trongsund @trongsund: там 10 вершин, а не рёбер. Кроме того, не всякий граф с 10 рёбрами и 24 вершинами планарен ($%K_5$% плюс несколько точек).
(13 Ноя '14 21:41)
falcao
А известно расположение рёбер и вершин в исходном графе? А то род графа может быть разным.
(13 Ноя '14 21:52)
trongsund
@trongsund, как это разным? Род графа однозначано определяется по его ребрам и вершинам.
(13 Ноя '14 22:07)
DarkGenius
Ну $%K_5$% с добавленным листом не планарен, а граф октаэдра с удалённым ребром планарен, хотя у них одинаково и вершин, и рёбер
(13 Ноя '14 22:17)
trongsund
@trongsund,естественно, так как ребра в указанных вами графах разные. В моей задаче речь идет не об абстрактном графе с заданным количеством вершин и ребер, а о вполне конкретном.
(14 Ноя '14 6:57)
DarkGenius
|
@DarkGenius: я не уверен, что есть эффективные алгоритмы для вычисления рода графа на каких-то больших данных. Скорее всего, Ваш случай можно разобрать вручную. Если есть картинка или описание, неплохо было бы их приложить. Поскольку граф не слишком большой, можно попробовать уложить его на торе вручную, если такая укладка в принципе возможна. Делать это можно на квадрате с отождествлёнными сторонами, проводя линии. Примерно так, как это делается для укладки на торе полного графа $%K_7$% и полного двудольного графа $%K_{4,4}$%.
@falcao, спасибо за ответ. Да, мне известно об укладке на квадрате. Попробовал один раз, но отчего-то не получилось. Вот список ребер моего графа: 1,2 1,4 1,7 1,8 2,4 2,6 2,7 2,8 2,10 3,4 3,6 3,9 3,10 4,5 4,6 4,8 4,9 5,7 5,9 5,10 6,7 6,9 7,8 7,10 8,9 9,10
@DarkGenius: задача очень интересная чисто в плане нахождения правильного ответа. Она точно должна решаться. Но тут надо какое-то время поизучать, как этот граф и его возможная укладка могут быть устроены. Сходу это пока не видно; я нахожусь в процессе изучения.
@falcao: Можете прислать рисунок? В какой программе Вы это делали? Какие эвристики используются для подобной укладки?
@falcao:Вы пишете, что заведомо f=16. Почему это так?
У меня про это было сказано в одном из комментариев ниже. По формуле Эйлера для тора v-e+f=0. Отсюда f=e-v=26-10=16.
@falcao: f=16 в предположении, что укладка на торе существует. Если она не существует, то тождество неверно.
В том то и дело, что это шанс. Можно очень долго пытаться построить пример и безрезультатно.
@DarkGenius: если укладка на торе есть, то f=16. А если нет, то само понятие f не имеет смысла, так как грани имеются не у самого графа, а у его укладки. Оговорка о том, что это всё верно в предположении наличии укладки, была у меня в комментарии.
Если какая-то задача объективно сложная, то бывает так, что её решают десятилетиями или даже столетиями. А если она не такая сложная, во что хотелось бы верить, то решение может быть найдено подобно головоломкам. Это соответствует характеру задачи.