Генерация графиков обхвата

10

Пусть . Мне нужно сгенерировать простые графы G обхвата g , чтобы множество всех g- циклов образовывало двойное ребро, покрывающее G (то есть каждое ребро делится ровно двумя g- циклами), и такое, чтобы пересечение любых двух g- циклы - это либо вершина, ребро, либо пустое. Сгенерированные графы должны быть сколь угодно большими.g3GggGgg

Метод генерации должен иметь некоторую случайность, но не в тривиальном смысле. Я хочу иметь возможность получать довольно сложные графики. Например, представьте прямоугольную сетку размером на плоскости. Если мы идентифицируем противоположные стороны ограничивающего прямоугольника, мы получим график, который удовлетворяет всем вышеуказанным требованиям для g = 4 . Я бы назвал этот график простым.n×mg=4

Есть ли такой метод?

Любые ссылки на подобные проблемы также приветствуются.

becko
источник
3
Итак, вы хотите, чтобы циклы были гранями некоего многогранного вложения графа на какую-то поверхность? (Вложение графа является «многогранным», если каждая грань вложения является диском, а любые две грани имеют общую вершину, общую g
границу
@ Jɛ ff E Да. Если все циклы гарантированно являются гранями, а все грани гарантированно являются g- циклами, то это эквивалентное описание. gg
becko
@ Jɛ ff E Знаете ли вы, где я могу найти различные 4-регулярные графы и их полиэдральные вложения? Они не должны быть огромными графиками, но я хотел бы видеть другие графики, которые удовлетворяют запрошенным мной свойствам, кроме того, который я упомянул. Я также знаю, что решение многогранной встраиваемости является NP-полным благодаря этому ответу . Несмотря на это, я также хотел бы знать алгоритм, который находит многогранное вложение, если оно есть. Вы знаете какой-либо ресурс / документ / ..., который объясняет такой алгоритм?
Бекко
есть ли связь между 4 регулярными графами и многогранными вложениями? у кого-нибудь есть описание этого? Год назад вы искали статьи о случайном создании регулярных графов, их довольно много, поэтому, если вы сможете перефразировать этот вопрос в терминах регулярных графов, это может привести к появлению новых возможностей.
vzn
@vzn Предположим, у меня есть многогранное вложение, подобное предложенному Джеффом. Все лица циклы. Двойственный граф, полученный из этого вложения, является g- регулярным. Возможно, это можно перевернуть: начните с g- регулярного графа и найдите его двойственный как-то. Это то, что я имел в виду. ggg
Беко

Ответы:

4

Моя недоделанная идея была слишком амбициозной. Я включил это ниже для справки, но условие расстояния, которое я указал, фактически не достаточно, чтобы гарантировать большой обхват.

Существуют произвольно большие высокосимметричные карты поверхности с большим обхватом, но опубликованные доказательства существования в значительной степени основаны на теории групп, а не на топологии или геометрии как таковой.

gdr1/g+1/d<1/2gdrrg

Если у вас есть одна такая карта поверхности, можно создать карты большего размера с такими же обхватом и степенью, создавая покрывающие пространства.


G

  • Gg

  • GGggG

  • GGg

g

GgGGGGg

Gddg1/d+1/g<1/2

Jeffε
источник
Кроме того, графики, которые вы получаете из этой конструкции, являются экспандерами.
Джефф
g
Что такое граф экспандера ?
Бекко
1
@becko, вы должны Google, прежде чем спрашивать :) en.wikipedia.org/wiki/Expander_graph
Каве
@Kaveh Хорошо. Извините, что пропустил это :)
becko