Выявить последовательность из графа

[De'Ad]

Здравствуйте!
Предлагаю попробовать решить следующую нестандартную, не учебную задачу:

Рассмотрим следующий направленый граф:

Единицей длины будем называть расстояние, пройденное между двумя соседними вершинами графа или однократное прохождение петли. Из произвольной из вершин, например $A$, можно построить замкнутые пути, любой натуральной длины, приводящие в эту же вершину. Например, замкнутый путь длины $1$ из вершины $A$ будет соответствовать петле при этой вершине и его можно построить единственным способом, лишь пройдя по этой петле. Путь длины $2$ из этой же вершины можно построить уже 3- мя способами, пройдя дважды по петле или пройдя $A \rightarrow B \rightarrow A$ или $A \rightarrow C \rightarrow A$, далее картина усложняется, для путей длины $3$ существует уже $7$ вариантов, для путей длины $4$ - $18$ вариантов, для длины $5$ и более- неизвестно вариантов, необходимо продолжить данный ряд: $1, 3, 7, 18,........, $а также попытаться выявить аналитическую зависимость количества замкнутых путей от их длины. Пути, элементы которых совпадают, отличаясь лишь последовательностью, считаются тождественными и учитываются один раз. Все учитываемые пути должны быть непрерывны и замкнуты.

[Lia]

Тема перемещена из форума «Дискуссионные темы (М)» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы);
- также просьба поместить изображение в тегах img, а не по внешней ссылке, в пределах 800 px ширины, и не 3 МБ, а разумнее.

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

[Lia]

Тема перемещена из форума «Карантин» в форум «Математика (общие вопросы)»

[arseniiv]

De'Ad в сообщении #1077526 писал(а):

Пути, элементы которых совпадают, отличаясь лишь последовательностью, считаются тождественными и учитываются один раз.

Дуги или вершины?

[De'Ad]

arseniiv в сообщении #1077569 писал(а):

De'Ad в сообщении #1077526 писал(а):

Пути, элементы которых совпадают, отличаясь лишь последовательностью, считаются тождественными и учитываются один раз.

Дуги или вершины?

Тождественными считаются такие замкнутые пути в которых количественно совпадают и дуги, и вершины, причём в общее количество друг и вершин учитываются и повторные прохождения по дуге или через вершину.
Пример: в данном графе из одной вершины у нас есть всего 9 замкнутых путей длины 3:

A \to A \to A \to A

A \to A \to B \to A

A \to A \to C \to A

A \to B \to A \to A

A \to B \to B \to A

A \to B \to C \to A

A \to C \to A \to A

A \to C \to B \to A

A \to C \to C \to A

Однако путь $ A \to A \to B \to A$ тождественен пути $A \to B \to A \to A$, также и путь $ A \to A \to C \to A$ тождественен пути $A \to C \to A \to A$. Итого, для замкнутых путей длины 3 получилось 7 возможных вариантов.

-- 28.11.2015, 10:04 --

Кстати, насчёт четвёртого члена ряда= 18, я сомневаюсь, я вычислял его методом перебора, в уме, и, вполне мог ошибиться, достоверно известны лишь первые три: 1, 3, 7,....?

[Sonic86]

Граф на картинке - это граф Кэли $\mathbb{Z}_3$: вершина $A$ - это $0$, вершина $B$ - это $1$, вершина $C$ - это $2$.
Дуги-петли отмечаются меткой $0$, дуги, идущие по часовой стрелке - меткой $1$, дуги, идущие против часовой стрелки - меткой $2$.

Если отбросить это ограничение:

De'Ad в сообщении #1077586 писал(а):

Однако путь $ A \to A \to B \to A$ тождественен пути $A \to B \to A \to A$, также и путь $ A \to A \to C \to A$ тождественен пути $A \to C \to A \to A$. Итого, для замкнутых путей длины 3 получилось 7 возможных вариантов.

то
Задача равносильна следующей: для данного $n$ найти всевозможные варианты $n$ элементов $a_1,...,a_n \in\mathbb{Z}_3$ таких, что $\sum\limits_{k=1}^n a_k \equiv 0 \pmod 3$.
Всего $3^n$ путей. Изменение одного элемента на 1 дает изменение суммы на 1, значит всего $3^{n-1}$ комбинаций $a_1,...,a_n$ таких, что их сумма равна заданному числу $S$ (в т.ч. и нулю).
Если же ограничение вернуть, то получим, что надо еще рассматривать энки $(a_1,...,a_n)$ как эквивалентные, если они равны после выбрасывания из них всех нулей.

De'Ad в сообщении #1077586 писал(а):

$A \to A \to B \to A$
$A \to B \to B \to A$

А эти пути эквивалентны?
Уточните, когда пути эквивалентны.

De'Ad в сообщении #1077526 писал(а):

Пути, элементы которых совпадают, отличаясь лишь последовательностью, считаются тождественными и учитываются один раз. Все учитываемые пути должны быть непрерывны и замкнуты.

Это какое-то для меня неясное определение. Слово "последовательность" имеет вполне определенный смысл. Можете выразиться иначе?

[arseniiv]

De'Ad
Спасибо за уточнение!

Приходит только безыскусная мысль написать что-то такое:

$$c(S,F,[AA],[AB],[AC],[BA],[BB],[BC],[CA],[CB],[CC]) = \sum_{F'} c(S,F',\ldots,[PQ]-[PQ=F'F],\ldots),$$

где $c(S,F,\ldots)$ — число путей из $S$ в $F$ с количествами дуг $P\to Q$, обозначенными $[PQ]$, и $[PQ=F'F] = 1$, если дуги $PQ = F'F$, и 0 иначе. Формула страшно неудобная, но хотя бы динамическое программирование (собственно, она и есть его прямое отражение) даёт быстренько написать. С начальными условиями $c(S,F,0,\ldots,0) = [S = F]$ (единица и ноль как выше; это т. н. скобки Айверсона). Ну, здесь, как вы выше писали, можно выкинуть $S$, положив её равной $A$, но если бы граф был не такой симметричный… (и имел не все возможныё дуги, кстати: тогда можно убрать соответствующие вычитания $[PQ=F'F]$!).

Вот можно ли это как-то упростить… А, я пост Sonic86 не дочитал. Понятно, что в случае произвольного, а не такого исключительного графа, вопрос об упрощении звучит намного сомнительнее.

[Sonic86]

arseniiv в сообщении #1077598 писал(а):

А если склеивать пути, но по содержанию в них только одинаковых количеств вершин, получатся треугольные числа и другие $n^{\overline{a}}/a!$. (Это я ночью написал сюда, но потом удалил, потому что будь постановка такой, это было бы заметно при решении. )

Ну да.
Но я сейчас понял, что я не понимаю, какие пути эквивалентны. Вы понимаете? Если да, то можете написать более-менее формально?

[arseniiv]

Я так понял, что мы смотрим число вхождений каждой дуги в путь и считаем пути с одинаковыми наборами этих чисел вхождений эквивалентными. Потому в моём посте все эти 9 дополнительных параметров.

-- Сб ноя 28, 2015 12:01:56 --

(Теория категорий.)

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

Точнее, понятное дело, функтор есть из последней в первую, но вот как его можно описать чисто категорно?

[Sonic86]

arseniiv в сообщении #1077601 писал(а):

Я так понял, что мы смотрим число вхождений каждой дуги в путь и считаем пути с одинаковыми наборами этих чисел вхождений эквивалентными. Потому в моём посте все эти 9 дополнительных параметров.

Ууу, жуть. Тогда все усложняется.

[De'Ad]

Sonic86 в сообщении #1077603 писал(а):

arseniiv в сообщении #1077601 писал(а):

Я так понял, что мы смотрим число вхождений каждой дуги в путь и считаем пути с одинаковыми наборами этих чисел вхождений эквивалентными. Потому в моём посте все эти 9 дополнительных параметров.

Ууу, жуть. Тогда все усложняется.

Благодарю за ответы.

Да, уважаемый arseniiv абсолютно прав насчёт определения эквивалентности путей. Однако, как мне кажется, реализовать это программно не так уж и просто. К томуже, уже при сравнительно небольших длинах путей, компьютер "умрет" и последовательность выявить не удастся. Да и сам алгоритм если и возможен, то не столь прост как может показаться на первый взгляд.

Данная последовательность в чем-то сходна с распределением простых чисел в натуральном ряду. Только недоступные для "восприятия" члены появляются гораздо раньше. Хотя, очевидно, что она бесконечна.

Хотелось бы для начала выявить хотя бы пару десятков членов.

Также я предполагаю, что аналитического выражения для членов искомой последовательности не существует.

[Brukvalub]

Господа, с прискорбием сообщаю вам, что вы развлекаете забаненного иващенко (это достоверная информация!)

[Lia]

De'Ad заблокирован как злостный клон.