Пусть . Мне нужно сгенерировать простые графы G обхвата g , чтобы множество всех g- циклов образовывало двойное ребро, покрывающее G (то есть каждое ребро делится ровно двумя g- циклами), и такое, чтобы пересечение любых двух g- циклы - это либо вершина, ребро, либо пустое. Сгенерированные графы должны быть сколь угодно большими.
Метод генерации должен иметь некоторую случайность, но не в тривиальном смысле. Я хочу иметь возможность получать довольно сложные графики. Например, представьте прямоугольную сетку размером на плоскости. Если мы идентифицируем противоположные стороны ограничивающего прямоугольника, мы получим график, который удовлетворяет всем вышеуказанным требованиям для g = 4 . Я бы назвал этот график простым.
Есть ли такой метод?
Любые ссылки на подобные проблемы также приветствуются.
источник
Ответы:
Моя недоделанная идея была слишком амбициозной. Я включил это ниже для справки, но условие расстояния, которое я указал, фактически не достаточно, чтобы гарантировать большой обхват.
Существуют произвольно большие высокосимметричные карты поверхности с большим обхватом, но опубликованные доказательства существования в значительной степени основаны на теории групп, а не на топологии или геометрии как таковой.
Роман Недела и Мартин Шковьера. Регулярные карты на поверхностях с большой плоской шириной. European J. Combinatorics 22 (2): 243-262, 2001.
Юзеф Ширан. Представления групп треугольников и конструкции регулярных отображений. Proc. London Math. Soc. 82 (3): 513-532, 2001.
Если у вас есть одна такая карта поверхности, можно создать карты большего размера с такими же обхватом и степенью, создавая покрывающие пространства.
источник