2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Количество путей длины $n$ в графе
Сообщение17.11.2012, 13:42 
Заслуженный участник


29/04/12
268
Рассмотрим граф: вершины составляют прямоугольную сетку $3\times 3$, рёбра соединяют соседние вершины (по диагонали тоже).

Хочу найти количество путей длины $n$ (начинать и заканчивать можно любой вершиной, можно проходить через одну вершину сколько угодно раз).

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

 Профиль  
                  
 
 Re: Количество путей длины $n$ в графе
Сообщение17.11.2012, 14:29 
Заслуженный участник
Аватара пользователя


13/08/08
14429
Если задача в евклидовой метрике, то диагональные отрезки можно выкинуть — их длина иррациональна. Вопрос: что считать равными (эквивалентными) путями. Если путь это последовательность $n+1$ вершины, то надо найти все такие последовательности, у которых после 1 идёт 2 или 4, после 2 идёт 3, 5 или 1, в соответствии с нумерацией вершин и их соседством.

 Профиль  
                  
 
 Re: Количество путей длины $n$ в графе
Сообщение17.11.2012, 14:51 


28/11/11
13
C RnD
lena7 в сообщении #645680 писал(а):
....составляют прямоугольную сетку $3\times 3$

А она не "квадратная" разве?

 Профиль  
                  
 
 Re: Количество путей длины $n$ в графе
Сообщение17.11.2012, 15:04 
Заслуженный участник
Аватара пользователя


23/08/07
5420
Нов-ск
Если под длиной пути понимать количество ребер, то вроде так:

Составим матрицу $A$, в которой элоемент $a_{ij}$ равен 1, если вершины $i$ и $j$ соединены, и равен нулю, если не соединены. В качестве ответа (количества путей длины $n$) возьмем сумму элементов матрицы $A^n$.

 Профиль  
                  
 
 Re: Количество путей длины $n$ в графе
Сообщение17.11.2012, 15:17 


28/11/11
13
C RnD
gris в сообщении #645701 писал(а):
...то диагональные отрезки можно выкинуть — их длина иррациональна.
- математики шутят ?)

gris в сообщении #645701 писал(а):
Вопрос: что считать равными (эквивалентными) путями.

Если написано, что путь длины $n$ - значит он содержит $n$ дуг. Получается ,что "равными" путями будут пути,содержащие одинаковое число дуг. Интересно то,что переходя из одной вершины в другую туда-сюда $n$ раз мы тоже получим путь,который будет "равен" любому другому пути длины $n$.

gris в сообщении #645701 писал(а):
последовательности, у которых после 1 идёт 2 или 4, после 2 идёт 3, 5 или 1, в соответствии с нумерацией вершин и их соседством.
Ну,это "гнусно"... Такая привязка к нумерации это "гнусно"...

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

-- 17.11.2012, 15:20 --

TOTAL, опередили....

 Профиль  
                  
 
 Re: Количество путей длины $n$ в графе
Сообщение17.11.2012, 17:34 
Заслуженный участник
Аватара пользователя


13/08/08
14429
Чего гнусного? Пусть все девять вершин связаны каждая с каждой. Найдём количество путей длины 15. Я сразу скажу, что это 39582418599936. А вы две недели будете матрицы перемножать.

 Профиль  
                  
 
 Re: Количество путей длины $n$ в графе
Сообщение17.11.2012, 17:37 
Заслуженный участник


29/04/12
268
gris
Длина пути -- количество проходимых рёбер. Если по ребру проходят $m$ раз, то оно считается $m$ раз.

TOTAL в сообщении #645708 писал(а):
Составим матрицу $A$, в которой элемент $a_{ij}$ равен 1, если вершины $i$ и $j$ соединены, и равен нулю, если не соединены. В качестве ответа (количества путей длины $n$) возьмем сумму элементов матрицы $A^n$.

Вау, как просто. А как можно доказать, что этот метод работает?

 Профиль  
                  
 
 Re: Количество путей длины $n$ в графе
Сообщение17.11.2012, 17:51 
Заслуженный участник


09/08/09
3438
С.Петербург
Почитайте про матрицу смежности (вики).

 Профиль  
                  
 
 Re: Количество путей длины $n$ в графе
Сообщение17.11.2012, 18:08 
Заслуженный участник


29/04/12
268
Ещё вариация задачи. Что если нельзя проходит по вершине повторно?

 Профиль  
                  
 
 Re: Количество путей длины $n$ в графе
Сообщение17.11.2012, 18:46 
Заслуженный участник
Аватара пользователя


23/08/07
5420
Нов-ск
lena7 в сообщении #645746 писал(а):
Ещё вариация задачи. Что если нельзя проходит по вершине повторно?
В этом случае подход к задаче такой же.

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

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



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

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


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

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