Количество видов цепочек

[Xaositect]

Не стоит ли связность графа потребовать?

Мне кажется, через разбиения можно получить какой-то результат.
Количество ребер, инцидентных вершине, называется ее степенью.
Для простого графа $\sum \deg v = 2N$ (сумма степеней всех вершин).
То есть набор степеней - это разбиение $2N$ на слагаемые.
Осталось только выяснить, какие разбиения соответствуют графам, а какие нет.

[maxal]

Xaositect в сообщении #280131 писал(а):

Осталось только выяснить, какие разбиения соответствуют графам, а какие нет.

http://mathworld.wolfram.com/DegreeSequence.html
http://www.theory.csc.uvic.ca/~cos/inf/ ... ences.html

[0101]

Спасибо!

[0101]

Тема не иссякла Количество замкнутых цепочек.
Заданное количество ребер N. Нужно определить количество графов, каждый из которых включает все ребра и прочертив который мы возращаемся в исходную точку. Граф относим к виду, определяемому по списку количеств соединенных ребер для каждой вершины. Одну пару вершин может соединять только одно ребро.

[Xaositect]

Эйлеровы графы?

[0101]

Это они. Отлично
Только под построением Эйлерова цикла принято понимать обработку некого произвольного графа. А как получить Эйлеровы циклы по заданному количеству ребер?
Попробую это.
С помощью матрицы смежности вершин можно найти маршруты, содержащие заданное количество ребер (дуг).
Теорема. Для определения количества маршрутов, состоящих из k ребер (дуг) необходимо возвести в k-ю степень матрицу смежности вершин. Тогда элемент даст количество маршрутов длины k из вершины vi в вершину vj.

[Xaositect]

Граф эйлеров тогда и только тогда, когда он связен и все вершины имеют четную степень.

[0101]

Эйлеров путь (эйлерова цепь) в графе — это путь, проходящий по всем рёбрам графа и притом только по одному разу.
$\xymatrix{A\ar@{-}[r]\ar@{-}[d]&B\ar@{-}[d]\\C\ar@{-}[r]&D}$Такой граф уже не Эйлеров?
Мне нужно, чтобы маршрут проходил по всем ребрам графа и возвращался точку начала. Для 6 ребер получается 2 варианта - 222222 и 42222(бабочка).

[maxal]

0101
http://en.wikipedia.org/wiki/Eulerian_p ... n_circuits

[Xaositect]

0101 в сообщении #281234 писал(а):

Такой граф уже не Эйлеров?

Почему же нет, эйлеров.
И степени всех вершин у него 2.

[0101]

Тогда асимптотическая формула числа эйлеровых графов для N ребер существует? Не та ,правда, что нужна

[0101]

Инфомация вполне исчерпывает вопрос. Спасибо!

[0101]

Это уже по поводу количества видов Эйлеровых графов для заданного количества ребер. В правом нижнем углу матрицы - сумма степеней вершин, нижняя строка и правый столбец- степени соотв. вершин.
Получал научным тыком. Гляньте, пожалуйста, не пропустил ли чего?
6 ребер
$\left(\begin{array}{ccccccc} 0&1&0&0&0&1&2\\ 1&0&1&0&0&0&2\\ 0&1&0&1&0&0&2\\ 0&0&1&0&1&0&2\\ 0&0&0&1&0&1&2\\ 1&0&0&0&1&0&2\\ 2&2&2&2&2&2&12 \end{array}\right)$$\left(\begin{array}{cccccc} 0&1&1&1&1&4\\ 1&0&1&0&0&2\\ 1&1&0&0&0&2\\ 1&0&0&0&1&2\\ 1&0&0&1&0&2\\ 4&2&2&2&2&12 \end{array}\right)$
7 ребер
$\left(\begin{array}{cccccc} 0&1&1&1&1&4\\ 1&0&1&1&1&4\\ 1&1&0&0&0&2\\ 1&1&0&0&0&2\\ 1&1&0&0&0&2\\ 4&4&2&2&2&14\\ \end{array}\right)$$\left(\begin{array}{ccccccc} 0&1&1&1&1&0&4\\ 1&0&0&0&0&1&2\\ 1&0&0&1&0&0&2\\ 1&0&1&0&0&0&2\\ 1&0&0&0&0&1&2\\ 0&1&0&0&1&0&2\\ 4&2&2&2&2&2&14\\ \end{array}\right)$$\left(\begin{array}{cccccccc} 0&1&0&0&0&0&1&2\\ 1&0&1&0&0&0&0&2\\ 0&1&0&1&0&0&0&2\\ 0&0&1&0&1&0&0&2\\ 0&0&0&1&0&1&0&2\\ 0&0&0&0&1&0&1&2\\ 1&0&0&0&0&1&0&2\\ 2&2&2&2&2&2&2&14\\ \end{array}\right)$
8 ребер
$\left(\begin{array}{cccccccc} 0&0&1&1&1&1&4\\ 0&0&1&1&1&1&4\\ 1&1&0&0&0&0&2\\ 1&1&0&0&0&0&2\\ 1&1&0&0&0&0&2\\ 1&1&0&0&0&0&2\\ 4&4&2&2&2&2&16 \end{array}\right)$$\left(\begin{array}{cccccccc} 0&1&1&1&1&0&0&4\\ 1&0&0&0&0&0&1&2\\ 1&0&0&1&0&0&0&2\\ 1&0&1&0&0&0&0&2\\ 1&0&0&0&0&1&0&2\\ 0&0&0&0&1&0&1&2\\ 0&1&0&0&0&1&0&2\\ 4&2&2&2&2&2&2&16 \end{array}\right)$$\left(\begin{array}{ccccccccc} 0&1&0&0&0&0& &1&2\\ 1&0&1&0&0&0&0&&2\\ 0&1&0&1&0&0&0&&2\\ 0&0&1&0&1&0&0&&2\\ 0&0&0&1&0&1&0&&2\\ 0&0&0&0&1&0&1&&2\\ 0&0&0&0&0&1&0&1&2\\ 1&&&&&&1&&2\\ 2&2&2&2&2&2&2&2&16 \end{array}\right)$
9 ребер
$\left(\begin{array}{ccccccc} 0&1&1&1&1&0&4\\ 1&0&1&0&1&1&4\\ 1&1&0&1&0&1&4\\ 1&0&1&0&0&0&2\\ 1&1&0&0&0&0&2\\ 0&1&1&0&0&0&2\\ 4&4&4&2&2&2&18 \end{array}\right)$$\left(\begin{array}{cccccccc} 0&0&0&1&1&1&1&4\\ 0&0&1&1&1&1&0&4\\ 0&1&0&0&0&0&1&2\\ 1&1&0&0&0&0&0&2\\ 1&1&0&0&0&0&0&2\\ 1&1&0&0&0&0&0&2\\ 1&0&1&0&0&0&0&2\\ 4&4&2&2&2&2&2&18 \end{array}\right)$$\left(\begin{array}{ccccccccc} 0&1&1&1&1&0&0&0&4\\ 1&0&0&0&0&0&0&1&2\\ 1&0&0&1&0&0&0&0&2\\ 1&0&1&0&0&0&0&0&2\\ 1&0&0&0&0&1&0&0&2\\ 0&0&0&0&1&0&1&0&2\\ 0&0&0&0&0&1&0&1&2\\ 0&1&0&0&0&0&1&0&2\\ 4&2&2&2&2&2&2&2&18 \end{array}\right)$$\left(\begin{array}{cccccccc} 0&1&1&1&1&1&1&6\\ 1&0&1&0&0&0&0&2\\ 1&1&0&0&0&0&0&2\\ 1&0&0&0&1&0&0&2\\ 1&0&0&1&0&0&0&2\\ 1&0&0&0&0&0&1&2\\ 1&0&0&0&0&1&0&2\\ 6&2&2&2&2&2&2&18 \end{array}\right)\left(\begin{array}{cccccccccc} 0&1&0&0&0&0& & &1&2\\ 1&0&1&0&0&0&0&&&2\\ 0&1&0&1&0&0&0&&&2\\ 0&0&1&0&1&0&0&&&2\\ 0&0&0&1&0&1&0&&&2\\ 0&0&0&0&1&0&1&&&2\\ 0&0&0&0&0&1&0&1&&2\\ 0&&&&&&1&&1&2\\ 1&&&&&&&1&&2\\ 2&2&2&2&2&2&2&2&2&18 \end{array}\right)$
10 ребер
$\left(\begin{array}{cccccc} 0&1&1&1&1&4\\ 1&0&1&1&1&4\\ 1&1&0&1&1&4\\ 1&1&1&0&1&4\\ 1&1&1&1&0&4\\ 4&4&4&4&4&20 \end{array}\right)$$\left(\begin{array}{ccccccc} 0&1&1&1&1&0&4\\ 1&0&1&1&0&1&4\\ 1&1&0&1&0&1&4\\ 1&1&1&0&1&0&4\\ 1&0&0&1&0&0&2\\ 0&1&1&0&0&0&2\\ 4&4&4&4&2&2&20 \end{array}\right)$$\left(\begin{array}{cccccccc} 0&1&1&1&1&0&&4\\ 1&0&1&0&1&0&1&4\\ 1&1&0&1&0&1&&4\\ 1&0&1&0&0&0&&2\\ 1&1&0&0&0&0&&2\\ 0&0&1&0&0&0&1&2\\ &1&&&&1&&2\\ 4&4&4&2&2&2&2&20 \end{array}\right)$$\left(\begin{array}{ccccccccc} 0&0&0&1&1&1&1&&4\\ 0&0&1&1&1&1&0&&4\\ 0&1&0&0&0&0&0&1&2\\ 1&1&0&0&0&0&0&&2\\ 1&1&0&0&0&0&0&&2\\ 1&1&0&0&0&0&0&&2\\ 1&0&0&0&0&0&0&1&2\\ &&1&&&&1&&2\\ 4&4&2&2&2&2&2&2&20 \end{array}\right)$$\left(\begin{array}{cccccccccc} 0&1&1&1&1&0&0&0&&4\\ 1&0&0&0&0&0&0&0&1&2\\ 1&0&0&1&0&0&0&0&&2\\ 1&0&1&0&0&0&0&0&&2\\ 1&0&0&0&0&1&0&0&&2\\ 0&0&0&0&1&0&1&0&&2\\ 0&0&0&0&0&1&0&1&&2\\ 0&0&0&0&0&0&1&0&1&2\\ &1&&&&&&1&&2\\ 4&2&2&2&2&2&2&2&2&20 \end{array}\right)$$\left(\begin{array}{cccccccc} 0&1&1&1&1&1&1&6\\ 1&0&1&1&1&&&4\\ 1&1&0&0&0&0&&2\\ 1&1&0&0&0&0&&2\\ 1&1&0&0&0&0&&2\\ 1&0&0&0&0&0&1&2\\ 1&&&&&1&&2\\ 6&4&2&2&2&2&2&20 \end{array}\right)$$\left(\begin{array}{ccccccccc} 0&1&1&1&1&1&0&1&6\\ 1&0&1&0&0&0&0&&2\\ 1&1&0&0&0&0&0&&2\\ 1&0&0&0&1&0&0&&2\\ 1&0&0&1&0&0&0&&2\\ 1&0&0&0&0&0&1&&2\\ 0&0&0&0&0&1&0&1&2\\ 1&&&&&&1&&2\\ 6&2&2&2&2&2&2&2&20 \end{array}\right)$$\left(\begin{array}{ccccccccccc} 0&1&0&0&0&0&&&&1&2\\ 1&0&1&0&0&0&0&&&&2\\ 0&1&0&1&0&0&0&&&&2\\ 0&0&1&0&1&0&0&&&&2\\ 0&0&0&1&0&1&0&&&&2\\ 0&0&0&0&1&0&1&&&&2\\ 0&0&0&0&0&1&0&1&&&2\\ 0&&&&&&1&&1&&2\\ 0&&&&&&&1&&1&2\\ 1&&&&&&&&1&&2\\ 2&2&2&2&2&2&2&2&2&2&20 \end{array}\right)$

11 ребер
$\left(\begin{array}{ccccccc} 0&1&1&1&0&1&4\\ 1&0&1&1&1&&4\\ 1&1&0&1&1&&4\\ 1&1&1&0&1&&4\\ 0&1&1&1&0&1&4\\ 1&&&&1&&2\\ 4&4&4&4&4&2&22 \end{array}\right)$$\left(\begin{array}{cccccccc} 0&1&1&1&1&0&&4\\ 1&0&1&1&0&0&1&4\\ 1&1&0&1&0&1&&4\\ 1&1&1&0&1&0&&4\\ 1&0&0&1&0&0&&2\\ 0&0&1&0&0&0&1&2\\ &1&&&&1&&2\\ 4&4&4&4&2&2&2&22 \end{array}\right)$$\left(\begin{array}{ccccccccc} 0&1&1&1&1&0&&&4\\ 1&0&1&0&1&0&1&&4\\ 1&1&0&1&0&1&&&4\\ 1&0&1&0&0&0&&&2\\ 1&1&0&0&0&0&&&2\\ 0&0&1&0&0&0&0&1&2\\ &1&&&&0&&1&2\\ &&&&&1&1&&2\\ 4&4&4&2&2&2&2&2&22 \end{array}\right)$$\left(\begin{array}{cccccccccc} 0&0&0&1&1&1&1&&&4\\ 0&0&1&1&1&1&0&&&4\\ 0&1&0&0&0&0&0&1&&2\\ 1&1&0&0&0&0&0&&&2\\ 1&1&0&0&0&0&0&&&2\\ 1&1&0&0&0&0&0&&&2\\ 1&0&0&0&0&0&0&0&1&2\\ &&1&&&&0&&1&2\\ &&&&&&1&1&&2\\ 4&4&2&2&2&2&2&2&2&22 \end{array}\right)$$\left(\begin{array}{ccccccccccc} 0&1&1&1&1&0&0&0&&&4\\ 1&0&0&0&0&0&0&0&1&&2\\ 1&0&0&1&0&0&0&0&&&2\\ 1&0&1&0&0&0&0&0&&&2\\ 1&0&0&0&0&1&0&0&&&2\\ 0&0&0&0&1&0&1&0&&&2\\ 0&0&0&0&0&1&0&1&&&2\\ 0&0&0&0&0&0&1&0&0&1&2\\ &1&&&&&&0&&1&2\\ &&&&&&&1&1&&2\\ 4&2&2&2&2&2&2&2&2&2&22 \end{array}\right)$$\left(\begin{array}{cccccccc} 0&1&1&1&1&1&1&6\\ 1&0&1&1&1&1&1&6\\ 1&1&0&0&0&&&2\\ 1&1&0&0&0&&&2\\ 1&1&0&0&0&&&2\\ 1&1&&&&&&2\\ 1&1&&&&&&2\\ 6&6&2&2&2&2&2&22 \end{array}\right)$$\left(\begin{array}{cccccccc} 0&1&1&1&1&1&1&6\\ 1&0&1&1&1&0&0&4\\ 1&1&0&0&0&1&1&4\\ 1&1&0&0&0&&&2\\ 1&1&0&0&0&&&2\\ 1&0&1&&&&&2\\ 1&0&1&&&&&2\\ 6&4&4&2&2&2&2&22 \end{array}\right)$$\left(\begin{array}{ccccccccc} 0&0&1&1&1&1&1&1&6\\ 0&0&1&1&1&1&&&4\\ 1&1&0&0&0&0&&&2\\ 1&1&0&0&0&0&&&2\\ 1&1&0&0&0&0&&&2\\ 1&1&0&0&0&0&&&2\\ 1&&&&&&&1&2\\ 1&&&&&&1&&2\\ 6&4&2&2&2&2&2&2&22 \end{array}\right)$$\left(\begin{array}{cccccccccc} 0&1&1&1&1&1&0&1&&6\\ 1&0&1&0&0&0&0&&&2\\ 1&1&0&0&0&0&0&&&2\\ 1&0&0&0&1&0&0&&&2\\ 1&0&0&1&0&0&0&&&2\\ 1&0&0&0&0&0&1&&&2\\ 0&0&0&0&0&1&0&0&1&2\\ 1&&&&&&0&&1&2\\ &&&&&&1&1&&2\\ 6&2&2&2&2&2&2&2&2&22 \end{array}\right)$$\left(\begin{array}{cccccccccccc} 0&1&0&0&0&0&&&&0&1&2\\ 1&0&1&0&0&0&0&&&&&2\\ 0&1&0&1&0&0&0&&&&&2\\ 0&0&1&0&1&0&0&&&&&2\\ 0&0&0&1&0&1&0&&&&&2\\ 0&0&0&0&1&0&1&&&&&2\\ 0&0&0&0&0&1&0&1&&&&2\\ 0&&&&&&1&&1&&&2\\ 0&&&&&&&1&&1&&2\\ 0&&&&&&&&1&&1&2\\ 1&&&&&&&&&1&&2\\ 2&2&2&2&2&2&2&2&2&2&2&22 \end{array}\right)$

12 ребер все хочет в одно сообщение влепиться и превысить 2000 символов

[0101]

12 ребер
$\left(\begin{array}{ccccccc} 0&1&1&1&0&1&4\\ 1&0&1&1&1&0&4\\ 1&1&0&0&1&1&4\\ 1&1&0&0&1&1&4\\ 0&1&1&1&0&1&4\\ 1&0&1&1&1&0&4\\ 4&4&4&4&4&4&24 \end{array}\right)$$\left(\begin{array}{cccccccc} 0&1&1&1&0&0&1&4\\ 1&0&1&1&1&&&4\\ 1&1&0&1&1&&&4\\ 1&1&1&0&1&&&4\\ 0&1&1&1&0&1&&4\\ 0&&&&1&&1&2\\ 1&&&&&1&&2\\ 4&4&4&4&4&2&2&24 \end{array}\right)$$\left(\begin{array}{ccccccccc} 0&1&1&1&1&0&&&4\\ 1&0&1&1&0&0&0&1&4\\ 1&1&0&1&0&1&&&4\\ 1&1&1&0&1&0&&&4\\ 1&0&0&1&0&0&&&2\\ 0&0&1&0&0&0&1&&2\\ &0&&&&1&&1&2\\ &1&&&&&1&&2\\ 4&4&4&4&2&2&2&2&24 \end{array}\right)$$\left(\begin{array}{cccccccccc} 0&1&1&1&1&0&&&&4\\ 1&0&1&0&1&0&1&&&4\\ 1&1&0&1&0&1&&&&4\\ 1&0&1&0&0&0&&&&2\\ 1&1&0&0&0&0&&&&2\\ 0&0&1&0&0&0&0&0&1&2\\ &1&&&&0&&1&&2\\ &&&&&0&1&&1&2\\ &&&&&1&&1&&2\\ 4&4&4&2&2&2&2&2&2&24 \end{array}\right)$$\left(\begin{array}{ccccccccccc} 0&0&0&1&1&1&1&&&&4\\ 0&0&1&1&1&1&0&&&&4\\ 0&1&0&0&0&0&0&1&&&2\\ 1&1&0&0&0&0&0&&&&2\\ 1&1&0&0&0&0&0&&&&2\\ 1&1&0&0&0&0&0&&&&2\\ 1&0&0&0&0&0&0&0&1&&2\\ &&1&&&&0&&0&1&2\\ &&&&&&1&0&&1&2\\ &&&&&&&1&1&0&2\\ 4&4&2&2&2&2&2&2&2&2&24 \end{array}\right)$$\left(\begin{array}{cccccccccccc} 0&1&1&1&1&0&0&0&&&&4\\ 1&0&0&0&0&0&0&0&1&&&2\\ 1&0&0&1&0&0&0&0&&&&2\\ 1&0&1&0&0&0&0&0&&&&2\\ 1&0&0&0&0&1&0&0&&&&2\\ 0&0&0&0&1&0&1&0&&&&2\\ 0&0&0&0&0&1&0&1&&&&2\\ 0&0&0&0&0&0&1&0&0&1&&2\\ &1&&&&&&0&&0&1&2\\ &&&&&&&1&0&&1&2\\ &&&&&&&&1&1&&2\\ 4&2&2&2&2&2&2&2&2&2&2&24 \end{array}\right)$$\left(\begin{array}{ccccccccc} 0&1&1&1&1&1&0&1&6\\ 1&0&1&1&1&1&1&&6\\ 1&1&0&0&0&&&&2\\ 1&1&0&0&0&&&&2\\ 1&1&0&0&0&&&&2\\ 1&1&&&&&&&2\\ 0&1&&&&&&1&2\\ 1&&&&&&1&&2\\ 6&6&2&2&2&2&2&2&24 \end{array}\right)$$\left(\begin{array}{ccccccccc} 0&1&1&1&1&1&0&1&6\\ 1&0&1&1&1&0&0&&4\\ 1&1&0&0&0&1&1&&4\\ 1&1&0&0&0&&&&2\\ 1&1&0&0&0&&&&2\\ 1&0&1&&&&&&2\\ 1&0&1&&&&&1&3\\ 0&&&&&&1&&1\\ 6&4&4&2&2&2&2&2&24 \end{array}\right)$$\left(\begin{array}{cccccccccc} 0&0&0&1&1&1&1&1&1&6\\ 0&0&1&1&1&1&0&&&4\\ 0&1&0&0&0&0&1&&&2\\ 1&1&0&0&0&0&0&&&2\\ 1&1&0&0&0&0&0&&&2\\ 1&1&0&0&0&0&0&&&2\\ 1&0&1&0&0&0&0&&&2\\ 1&&&&&&&&1&2\\ 1&&&&&&&1&&2\\ 6&4&2&2&2&2&2&2&2&24 \end{array}\right)$$\left(\begin{array}{ccccccccccc} 0&1&1&1&1&1&0&1&&&6\\ 1&0&1&0&0&0&0&&&&2\\ 1&1&0&0&0&0&0&&&&2\\ 1&0&0&0&1&0&0&&&&2\\ 1&0&0&1&0&0&0&&&&2\\ 1&0&0&0&0&0&1&&&&2\\ 0&0&0&0&0&1&0&0&0&1&2\\ 1&&&&&&0&&1&&2\\ &&&&&&0&1&&1&2\\ &&&&&&1&&1&&2\\ 6&2&2&2&2&2&2&2&2&2&24 \end{array}\right)$$\left(\begin{array}{ccccccccccccc} 0&1&0&0&0&0&0&0&0&0&0&1&2\\ 1&0&1&0&0&0&0&&&&&&2\\ 0&1&0&1&0&0&0&&&&&&2\\ 0&0&1&0&1&0&0&&&&&&2\\ 0&0&0&1&0&1&0&&&&&&2\\ 0&0&0&0&1&0&1&&&&&&2\\ 0&0&0&0&0&1&0&1&&&&&2\\ 0&&&&&&1&&1&&&&2\\ 0&&&&&&&1&&1&&&2\\ 0&&&&&&&&1&&1&&2\\ 0&&&&&&&&&1&&1&2\\ 1&&&&&&&&&&1&&2\\ 2&2&2&2&2&2&2&2&2&2&2&2&24 \end{array}\right)$$\left(\begin{array}{cccccccccc} 0&1&1&1&1&1&1&1&1&8\\ 1&0&1&0&0&0&0&0&0&2\\ 1&1&0&0&0&0&0&0&0&2\\ 1&0&0&0&1&0&0&0&0&2\\ 1&0&0&1&0&0&0&0&0&2\\ 1&0&0&0&0&0&1&0&0&2\\ 1&0&0&0&0&1&0&0&0&2\\ 1&0&0&0&0&0&0&0&1&2\\ 1&0&0&0&0&0&0&1&0&2\\ 8&2&2&2&2&2&2&2&2&24 \end{array}\right)$

[AD]

Ой, ё-моё
Всем обладателям 50-дюймовых экранов прошу пожалеть владельцев нетбуков и на будущее разбивать строчки хотя бы вот так.