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

[LynxGAV]

В структуре, указанной на рисунке (вариант Bethe lattice), у любого узла "внутри" имеется ровно четыре соседних узла (coordination number z=4). [Например, узел 1 связан ребрами с узлами 0, 5, 6, 7.] Как соединить узлы друг с другом, находящиеся на границе (в данном примере с 17 по 52) так, чтобы 1. у каждого было ровно 4 соседа (то есть для каждого узла последнего уровня надо создать три дополнительных ребра). 2. чтобы появляющиеся петли (loops) были максимальной длины. [Пример 1: если провести ребро от 17 к 18, образуется петля размера "3" 17-5-18. Пример 2: ребро от 17 к 26 создает пелю размера "7" 17-5-1-0-2-8-26. Но если следующее ребро от 18 к 27, то добавляются еще две петли 17-26-8-27-18-5 и 18-5-1-0-2-8-27.] 3. число уровней в графе считать известным, но не обязательно так, как на рисунке. [В системе на рисунке имеется только три уровня. Первый состоит из узлов 1, 2, 3, 4, второй 5, 6, 7, 8, 9, 10, ..., 16 и третий 17, 18, 19, 20, 21, ..., 52.]

[maxal]

LynxGAV писал(а):

2. чтобы появляющиеся петли (loops) были максимальной длины. [Пример 1: если провести ребро от 17 к 18, образуется петля размера "3" 17-5-18. Пример 2: ребро от 17 к 26 создает пелю размера "7" 17-5-1-0-2-8-26. Но если следующее ребро от 18 к 27, то добавляются еще две петли 17-26-8-27-18-5 и 18-5-1-0-2-8-27.]

Это условие непонятно. Пусть скажем мы соединили данное множество "крайних" вершин двумя различными способами и оба способа содержат циклы разных длин. Как сравнить какой из способов лучше? По сумме длин циклов, по минимаксу или еще как?

Судя по рисунку, абсолютной максимальности длин можно было бы достичь, если запретить соединять вершины, принадлежащие одной и той же из 4-х групп: 17-25, 26-34, 35-43, 44-52. И этого легко добиться - достаточно построить полные графы $K_4$ на следующих четверках вершин: (17, 26, 35, 44), (18, 27, 36, 45), ..., (25, 34, 43, 52), то есть беря каждый раз по одной вершине из каждой группы. Такое замыкание графа удовлетворяет всем требуемым условиям.

[photon]

maxal писал(а):

Судя по рисунку, абсолютной максимальности длин можно было бы достичь, если запретить соединять вершины, принадлежащие одной и той же из 4-х групп: 17-25, 26-34, 35-43, 44-52. И этого легко добиться - достаточно построить полные графы $K_4$ на следующих четверках вершин: (17, 26, 35, 44), (18, 27, 36, 45), ..., (25, 34, 43, 52), то есть беря каждый раз по одной вершине из каждой группы. Такое замыкание графа удовлетворяет всем требуемым условиям.

Не совсем - если мы провели, скажем связь 17-26, то следующая прокладка 18-27 образует более короткую связь (необходимо учитывать уже имеющуюся 17-26)

[maxal]

Да, такая конструкция не катит. Но тем не менее это не отрицает возможности существования такого замыкания, где все циклы будут иметь длину 7 (т.е. максимально возможную для данного графа). Существует ли оно?

[photon]

maxal писал(а):

Существует ли оно?

Вот в этом и есть вопрос номер 1, а вопрос номер 2 состоит в обобщении решения для графа с произвольным числом уровней

[LynxGAV]

maxal писал(а):

LynxGAV писал(а):

2. чтобы появляющиеся петли (loops) были максимальной длины. [Пример 1: если провести ребро от 17 к 18, образуется петля размера "3" 17-5-18. Пример 2: ребро от 17 к 26 создает пелю размера "7" 17-5-1-0-2-8-26. Но если следующее ребро от 18 к 27, то добавляются еще две петли 17-26-8-27-18-5 и 18-5-1-0-2-8-27.]

Это условие непонятно. Пусть скажем мы соединили данное множество "крайних" вершин двумя различными способами и оба способа содержат циклы разных длин. Как сравнить какой из способов лучше? По сумме длин циклов, по минимаксу или еще как?

Впринципе меня интересуют все алгоритмы, поэтому интересны любые предложения, если Вы можете дать оценку длин циклов для графа с конкретным числом уровней (например, для 12-уровнего графа, чтобы я могла сделать прикидку). Также отметаются случаи "тривиальных" циклов (длины 3, 4, 5) -- таковых быть не должно ни при каких условиях.

Но склоняюсь к тому, в котором циклы разных длин, но одного порядка.

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

[photon]

Таа-а-ак, каждый надо связать с тремя другими, значит, по-моему, логично связывать следующим образом. Трудно объяснить на словах - проследите первые связи в том порядке, как я их укажу и, надеюсь, вы поймете логику - последовательность сцепления:

17-26, 17-35, 17-44
18-29, 18-38, 18-47
19-32, 19-41, 19-50

20-27, 20-36, 20-45
21-30, 21-39, 21-48
22-33, 22-42, 22-51

23-28, 23-37, 23-46
24-31, 24-40, 24-49
25-34, 25-43, 25-52

Это я написал связи от ветки, которая пошла от 1. А дальше, тем же порядком для 2,3, 4. Похоже на правду или я "слажал"?

[LynxGAV]

Если погнаться за максимальной длиной уровней в самом начале, соединяя (17 с 26, 35, 44, etc.)

17 - 26, 35, 44
18 - 29, 38, 47
19 - 32, 41, 50
20 - 27, 36, 45
21 - 30, 39, 48
22 - 33, 42, 51
23 - 28, 37, 46
24 - 31, 40, 49
25 - 34, 43, 52

то эти ребра будут образовывать циклы только длины 7 и 8. Но остаётся провести по два ребра между вершинами 26, 27, ..., 51, 52 и, похоже, это можно сделать только с образованием циклов длины 5.

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

photon писал(а):

Это я написал связи от ветки, которая пошла от 1. А дальше, тем же порядком для 2,3, 4. Похоже на правду или я "слажал"?

И написал быстрее меня, но независимо. Дальше я прикинула, что для других веток не получается (будет 26-35, 44, но сразу будет петля 26-35-17).

[photon]

Да, действительно, бодрое начало, но дальше по аналогии не получается также красиво

[LynxGAV]

maxal писал(а):

Да, такая конструкция не катит. Но тем не менее это не отрицает возможности существования такого замыкания, где все циклы будут иметь длину 7 (т.е. максимально возможную для данного графа). Существует ли оно?

Такой алгоритм был бы идеальным.

[photon]

LynxGAV писал(а):

(будет 26-35, 44, но сразу будет петля 26-35-17).

Нет, я подумал дальше 26-38,50; 27-41,48, но вот уже на 29 будет короче.

[LynxGAV]

photon писал(а):

Да, действительно, бодрое начало, но дальше по аналогии не получается также красиво

.

Учитывая те связи, которые уже есть, можно замыкать 26 на 52. Или на другие вершины, с образование циклов длины 5. Вопрос: можно ли их все замкнуть, чтобы были петли только длины 5? И самое интересное, как это 5 изменится для графа с большим числом уровней.

[LynxGAV]

photon писал(а):

Нет, я подумал дальше 26-38,50; 27-41,48, но вот уже на 29 будет короче.

Для 29, понятно, не получится. Он уже не из тройки 26, 27, 28. Да и 26-38,50; 27-41,48 не является логичным продолжением изначального цикла.

[photon]

maxal писал(а):

где все циклы будут иметь длину 7 (т.е. максимально возможную для данного графа). Существует ли оно?

Что-то подсказывает, что нет - та последовательность, что задали я и LynxGAV, либо подобные, как мне кажется, единственно-возможный подход для образования всех связей одинаково максимальных для одной ветки (мы взяли ту, что пошла от единицы), но при попытке связать остальные возникает трабла. А может ли быть хотя бы 6 максимумом для того количества уровней, что мы взяли за образец?

[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 секунды:

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