Согласно книге «Топологическая теория графов» Гросса и Такера, учитывая клеточное вложение графа на поверхность (под «поверхностью» я подразумеваю здесь сферу с некоторыми ручками , а ниже S n относится к сфере с ровно n ручками), можно определить двойной мультиграф, рассматривая грани исходного графа, встраиваемые как вершины, и добавляя ребро между двумя вершинами для каждой стороны, которую имеют соответствующие грани в исходном графе.
Вот моя проблема . Учитывая график , мне нужно найти другой граф G ' таких , что существует поверхность S и клеточное вложение G на S таких , что G ' является двойственным этим вложением G . Я знаю, что существует много возможных графов G ′ ; Мне просто нужно найти для любого графа G .
У меня есть несколько вопросов . Моя текущая стратегия состоит в том, чтобы (1) определить род в G , (2) найти вложение G на S n и (3) найти двойственное для этого вложения. Все эти шаги имеют известные алгоритмы (хотя (1) NP-Hard). Интересно, есть ли способ найти G , который обходит вычисления рода, поскольку это является узким местом этого подхода, и это мой первый вопрос. Мой второй вопрос: если я знаю, что G регулярна, может ли это облегчить вычисление рода? И мой третий вопрос - запрос на любые ссылки, которые могут помочь мне решить эту проблему.
Ответы:
Ваш двойник должен быть минимального рода? Поскольку нахождение клеточного вложения для любого графа тривиально: просто выберите круговой порядок для ребер, падающих на каждую вершину, произвольно, а затем определите грани вложения как последовательности ребер, согласующиеся с выбранными порядками.
Мне нравится представление GEM (кодированная в графах карта) вложения из книги «Основы теории топологических графов» Беннингтона и Литтла. В этом представлении вложение представляется 3-реберным 3-регулярным графом с одним ребром для каждого флага вложения (падающая тройка вершины, ребра и грани) и одним ребром для каждых двух флагов, которые отличаются только один из элементов наборов вершин / ребер / граней, которые они представляют. Например, изображение ниже из Википедии может быть интерпретировано как GEM правильного додекаэдра, в котором красные циклы представляют его грани, желтые циклы представляют его ребра, а синие циклы представляют его вершины; края могут быть окрашены в соответствии с цветами их двух инцидентных граней.
При заданном круговом упорядочении ребер графа G его GEM можно найти, сделав цикл из 2d вершин для каждой вершины степени d в G, по два для каждого ребра, с парами вершин для каждого инцидентного ребра, встречающегося в цикл в выбранном круговом порядке, а затем для каждого ребра e из G, связывающего две пары ребер GEM для двух конечных точек e в прямоугольник. Если вы хотите ориентированное встраивание, выбор способа связывания этих четырех вершин в прямоугольник должен соответствовать круговым порядкам, в противном случае он может быть произвольным.
Тогда вершины, ребра и грани вложения G представлены циклами в GEM, которые чередуются между двумя из трех краевых цветов. Двойник G представлен GEM с тем же базовым 3-регулярным графом, но с двумя замененными краями. И граф, представленный GEM, может быть сформирован путем сжатия всех его циклов вершин и объединения пар параллельных ребер в одно ребро. Таким образом, построение дуала G (если вам все равно, какой дуал) может быть легко сделано за линейное время.
источник