Cayley tree (алгоритм)

[LynxGAV]

maxal писал(а):

Как я понял, задача сводится к построению 4-регулярного графа на 53 вершинах с максимальным обхватом (girth).

Цитирую:
Thomas Grüner found that there exist no 4-regular Graphs with girth 7 on less than 58 vertices.

Поэтому обхват равный 7 для данного графа недостижим.

Добавлено спустя 3 минуты 2 секунды:

На том же сайте есть программа для построения регулярных графов с заданным обхватом.

Меня такие маленькие графы и не интересуют. Если, например, для 1062881 можно, то отлично.

Добавлено спустя 1 минуту 39 секунд:

maxal писал(а):

На том же сайте есть программа для построения регулярных графов с заданным обхватом.

Спасибо, посмотрю.

[maxal]

LynxGAV писал(а):

Меня такие маленькие графы и не интересуют. Если, например, для 1062881 можно, то отлично.

1062881 - это 12 уровней, надо полагать? Кстати, когда вы говорите, что число уровней в графе может быть любым, то степень вершин по-прежнему предполагается равной 4?

[LynxGAV]

maxal писал(а):

1062881 - это 12 уровней, надо полагать?

Да.

maxal писал(а):

Кстати, когда вы говорите, что число уровней в графе может быть любым, то степень вершин по-прежнему предполагается равной 4?

То, что degree всех вершин 4 (или мы говорим coordination number ), должно безукоризненно выполняться.

Собственно, если вы так чудно разбираетесь в этих вещах, то могу поделиться некоторыми размышлениями. Мне выбор "замкнутой" Bethe lattice тоже не очень удобен по одной простой причине, что число вершин с каждым уровнем растет не по дням, а по часам. То есть выбор практически или за миллион вершин, или за три (или больше..), что ограничивает возможности исследования систем разного размера. С другой стороны мои теор. результаты верны именно для "cycle-free graph" без конкретного ограничения на число вершин (т.е. для Bethe lattice, которая по определению не имеет ни одного цикла и соответственно бесконечна; или просто для некого абстрактного графа с girth=infinity). Поэтому первая идея была взять именно такую структуру, ее легко симулировать до определенного уровня, а потом замкнуть ребра, получая наибольший обхват (физ. система соответственно меньше всего будет чувствовать эти циклы), что мне казалось будет не сложно осуществить практически. С другой стороны, я сейчас подумала, что не так важно будет это граф по типу Bethe lattice c z=4 или 4-regular graph (4RG даже удобнее). Важно, чтобы girth был наибольшим, а общее число циклов наименьшим (если я правильно себе представляю приближение компьютерной системы к теоретической).

Если надо исследовать графы с 10^7 вершинами, мне только вручную с помощью их программы параметры проверять (к тому же общее число циклов тоже очень хотелось бы знать)? Интересно, для такого большого числа вершин матрица тоже выводится?? Не может ли оказаться, что для 10^6 girth будет х, а для 10^6+1 меньше х?

[maxal]

Посмотрите как определяется $(v,g)$-клетка. Из нижней оценки на число вершин в таком графе следует, что в вашем случае (для $v=4$) максимальный обхват может составлять что-то около $2\log_3 n$, где $n$ - число вершин в 4-регулярном графе.

[LynxGAV]

Логично . Для той же 12-уровневой Bethe lattice максимальный обхват будет порядка 25, т.е. цикл, проходящий через центр.

Что значит "The following table summarizes known cage graphs." Самым последним идет (4,12) >=1 Royle. А дальше что?

Существует много r-регулярных графов с заданным числом вершин. Но их топологические характеристики (число и длина циклов) одинаковые? Тож же вопрос для r-regular graphs with girth at least g.

[maxal]

LynxGAV писал(а):

Что значит "The following table summarizes known cage graphs." Самым последним идет (4,12) >=1 Royle. А дальше что?

А дальше точная конструкция (4,g)-клеток (и число вершин в них) неизвестна. Но вам, как я понял, в точности эти клетки и не нужны (в противном случае вы упираетесь в открытую проблему), а нужно лишь более-менее хорошее приближение к ним.

LynxGAV писал(а):

Существует много r-регулярных графов с заданным числом вершин. Но их топологические характеристики (число и длина циклов) одинаковые?

Вообще говоря, нет. Но для экстремальных случаев (например, когда число вершин максимально или минимально возможное) характеристики вполне могут принимать фиксированные значения.

[LynxGAV]

maxal писал(а):

LynxGAV писал(а):

Что значит "The following table summarizes known cage graphs." Самым последним идет (4,12) >=1 Royle. А дальше что?

А дальше точная конструкция (4,g)-клеток (и число вершин в них) неизвестна. Но вам, как я понял, в точности эти клетки и не нужны (в противном случае вы упираетесь в открытую проблему), а нужно лишь более-менее хорошее приближение к ним.

Число вершин максимальное или минимальное -- не важно, так же как и число возможных графов. Достаточно одного единственного.

Да, но нужно достаточно хорошее приближение. Плохие (или не плохие, но наиболее простые приближения) я уже встречала в статьях.

Какой тогда смысл пользоваться программой GENREG, если она этого заведомо сделать не сможет. Сейчас проверю, до скольки вершин потянет.

[maxal]

LynxGAV писал(а):

Какой тогда смысл пользоваться программой GENREG, если она этого заведомо сделать не сможет. Сейчас проверю, до скольки вершин потянет.

Для исходной задачи на 53 вершинах может и потянет. Для большего числа уровней - вряд ли.

[LynxGAV]

Часто генерируется Bethe lattice, после чего вершины последнего уровня замыкаются друг на друга случайным образом, что неминуемо влечет образование большого числа циклов всех длин. К тому же такой алгорим даже менее точный, чем RRG4 (random 4-regular graph). Если число вершин 10^6, то в последнем вероятность образования циклов длины 3 и 4 меньше, чем в "замкнутой" Bethe lattice, потому что в ней число вершин на последнем уровне порядка числа "внутри". RRG4 уже проверяла: в среднем образуется около 15 циклов длины 3 и 4 (посчитать циклы большей длины не представляется возможным), после чего я делаю rewiring до тех пор, пока они не исчезнут. И даже такой модифицированный граф портит всю малину из-за бОльших корреляций, которые я ни подсчитать, ни убрать не могу. Потому надо что-то более точное.

Добавлено спустя 11 минут 7 секунд:

maxal писал(а):

Для исходной задачи на 53 вершинах может и потянет. Для большего числа уровней - вряд ли.

Совершенно верно. Программа GENREG расчитана на "maximal 99 knoten". Но та же ссылка на wolfram'е yтверждает, что существует граф с числом вершин = числу вершин в 12-уровн. Bethe lattice, degree 4 и girth 25. То есть алгоритм все-таки есть. Для lower bound, g odd, число вершин и есть сумма $\sum\limits_{k=1}^p 4 \ 3^{(k-1)}+1$.

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

[Борис Лейкин]

LynxGAV писал(а):

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

А чё за реальная задача? Секрет?

[maxal]

LynxGAV писал(а):

Но та же ссылка на wolfram'е yтверждает, что существует граф с числом вершин = числу вершин в 12-уровн. Bethe lattice, degree 4 и girth 25.

Где именно такое утверждается?

[LynxGAV]

Да, я невнимательно смотрела, это только нижняя грань.

Добавлено спустя 32 минуты 50 секунд:

Борис Лейкин писал(а):

А чё за реальная задача?

Реальная не в значении "крутая". Алгоритм нужен как приложение для изучения динамики другой модели.

[Борис Лейкин]

А узлы графа это значит больные, а чего у них именно по четыре соседа, семья?

нг:

[нг]

Борис Лейкин, Вам хочется порезвиться? Вы хорошо знаете, это более уместно в ЛС.

Какой ответ Вы ожидаете? Это не дискуссионная тема в математике. Вы же не ожидаете всерьёз, что Вам здесь будут излагать теорию и современное состояние исследований. Если Вас заинтересовало введение в вопрос — Вы знаете, что сто́ит открыть новую тему, а не мешать в существующей. Так почему Вы так себя ведёте?

[maxal]

Посмотрите на эту статейку и особенно на Fig. 2 там. Можно у них позаимствовать идею построения 4-регулярного графа Кэли для подгруппы $S_n$, порожденной двумя перестановками $a, b$ $n$-го порядка. Для начала можно попробовать взять случайные перестановки и посмотреть какой получается обхват...