Количество путей длины $n$ в графе

[lena7]

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

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

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

[gris]

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

[demontagnac]

lena7 в сообщении #645680 писал(а):

....составляют прямоугольную сетку $3\times 3$

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

[TOTAL]

Если под длиной пути понимать количество ребер, то вроде так:

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

[demontagnac]

gris в сообщении #645701 писал(а):

...то диагональные отрезки можно выкинуть — их длина иррациональна.

- математики шутят ?)

gris в сообщении #645701 писал(а):

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

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

gris в сообщении #645701 писал(а):

последовательности, у которых после 1 идёт 2 или 4, после 2 идёт 3, 5 или 1, в соответствии с нумерацией вершин и их соседством.

Ну,это "гнусно"... Такая привязка к нумерации это "гнусно"...

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

-- 17.11.2012, 15:20 --

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

[gris]

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

[lena7]

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

TOTAL в сообщении #645708 писал(а):

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

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

[Maslov]

Почитайте про матрицу смежности (вики).

[lena7]

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

[TOTAL]

lena7 в сообщении #645746 писал(а):

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

В этом случае подход к задаче такой же.