2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Выявить последовательность из графа
Сообщение28.11.2015, 00:41 


28/11/15

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

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

 Профиль  
                  
 
 Posted automatically
Сообщение28.11.2015, 01:36 


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

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

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

 Профиль  
                  
 
 Posted automatically
Сообщение28.11.2015, 02:12 


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

 Профиль  
                  
 
 Re: Выявить последовательность из графа
Сообщение28.11.2015, 06:26 
Заслуженный участник


27/04/09
28128
De'Ad в сообщении #1077526 писал(а):
Пути, элементы которых совпадают, отличаясь лишь последовательностью, считаются тождественными и учитываются один раз.
Дуги или вершины?

 Профиль  
                  
 
 Re: Выявить последовательность из графа
Сообщение28.11.2015, 08:57 


28/11/15

4
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,....?

 Профиль  
                  
 
 Re: Выявить последовательность из графа
Сообщение28.11.2015, 09:40 
Заслуженный участник


08/04/08
8564
Граф на картинке - это граф Кэли $\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 писал(а):
Пути, элементы которых совпадают, отличаясь лишь последовательностью, считаются тождественными и учитываются один раз. Все учитываемые пути должны быть непрерывны и замкнуты.
Это какое-то для меня неясное определение. Слово "последовательность" имеет вполне определенный смысл. Можете выразиться иначе?

 Профиль  
                  
 
 Re: Выявить последовательность из графа
Сообщение28.11.2015, 09:47 
Заслуженный участник


27/04/09
28128
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 иначе. Формула страшно неудобная, но хотя бы динамическое программирование (собственно, она и есть его прямое отражение) даёт быстренько написать. :roll: С начальными условиями $c(S,F,0,\ldots,0) = [S = F]$ (единица и ноль как выше; это т. н. скобки Айверсона). Ну, здесь, как вы выше писали, можно выкинуть $S$, положив её равной $A$, но если бы граф был не такой симметричный… (и имел не все возможныё дуги, кстати: тогда можно убрать соответствующие вычитания $[PQ=F'F]$!).

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

 Профиль  
                  
 
 Re: Выявить последовательность из графа
Сообщение28.11.2015, 09:53 
Заслуженный участник


08/04/08
8564
arseniiv в сообщении #1077598 писал(а):
А если склеивать пути, но по содержанию в них только одинаковых количеств вершин, получатся треугольные числа и другие $n^{\overline{a}}/a!$. (Это я ночью написал сюда, но потом удалил, потому что будь постановка такой, это было бы заметно при решении. :-) )
Ну да.
Но я сейчас понял, что я не понимаю, какие пути эквивалентны. Вы понимаете? Если да, то можете написать более-менее формально?

 Профиль  
                  
 
 Re: Выявить последовательность из графа
Сообщение28.11.2015, 09:57 
Заслуженный участник


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

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

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

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

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

 Профиль  
                  
 
 Re: Выявить последовательность из графа
Сообщение28.11.2015, 10:02 
Заслуженный участник


08/04/08
8564
arseniiv в сообщении #1077601 писал(а):
Я так понял, что мы смотрим число вхождений каждой дуги в путь и считаем пути с одинаковыми наборами этих чисел вхождений эквивалентными. Потому в моём посте все эти 9 дополнительных параметров.
Ууу, жуть. Тогда все усложняется.

 Профиль  
                  
 
 Re: Выявить последовательность из графа
Сообщение28.11.2015, 10:27 


28/11/15

4
Sonic86 в сообщении #1077603 писал(а):
arseniiv в сообщении #1077601 писал(а):
Я так понял, что мы смотрим число вхождений каждой дуги в путь и считаем пути с одинаковыми наборами этих чисел вхождений эквивалентными. Потому в моём посте все эти 9 дополнительных параметров.
Ууу, жуть. Тогда все усложняется.


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

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

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

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

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

 Профиль  
                  
 
 Re: Выявить последовательность из графа
Сообщение28.11.2015, 11:07 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Выявить последовательность из графа
Сообщение28.11.2015, 12:47 


20/03/14
12041
 !  De'Ad заблокирован как злостный клон.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 13 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: YandexBot [bot]


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group