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
8556
Граф на картинке - это граф Кэли $\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
8556
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
8556
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 ] 

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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