Поиск Эйлерового цикла

[Teosty]

Доброе время суток.
Помогите найти эйлеров цикл в неориентированном графе, заданном матрицей смежности:
$ \left( \begin{array}{ccccccc} 1 & 1 & 0 & 1 & 0 & 1 & 1\\ 1 & 1 & 1 & 1 & 1 & 0 & 0\\ 0 & 1 & 1 & 1 & 1 & 0 & 1\\ 1 & 1 & 1 & 1 & 1 & 1 & 1\\ 0 & 1 & 1 & 1 & 1 & 1 & 0\\ 1 & 0 & 0 & 1 & 1 & 1 & 1\\ 1 & 0 & 1 & 1 & 0 & 1 & 1 \end{array} \right)$
Получалось находить эйлеров цикл в матрицах размера 4х4 и 5х5, но к этой матрице даже не знаю как подступиться (для начала надо хотя бы определить есть ли эйлеров цикл)

[Lia]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
Тема перемещена в Карантин по следующим причинам:

Наберите правильно матрицу и приведите попытки решения, указав затруднения.

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

[Lia]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»
Причина переноса: не указана.

[Sonic86]

Что такое "Эйлеров цикл" знаете?
Алгоритм построения эйлерова цикла ручкой на бумаге знаете?

[Teosty]

Эйлеров цикл - путь, проходящий через все грани графа и только один раз.
Находил по алгоритму "змея":
Для нахождения Эйлерова цикла можно использовать алгоритм "змеи" из книги Шеня.
Змея – это ненулевая последовательность из вершин графа, в которой две соседние вершины соединены ребром графа. Первая вершина последовательности – хвост змеи, а последняя – голова. При добавлении вершины в последовательность змея растет с головы, также возможно отрезать кончик хвоста, удалив первую вершину. Вначале змея состоит из единственной вершины. Далее действуем по следующему алгоритму:
while(змея включает не все ребра) {
if(из головы выходит неиспользованное в змее ребро)
удлинить змею этим ребром
else {
// хвост змеи находится в той же вершине, что и голова
отрезать конец хвоста и добавить его к голове
т.е. змея откусывает свой хвост
}
}

[provincialka]

Вы в детстве не обводили картинку "не отрывая карандаша от бумаги"? Граф всего лишь с 7 вершинами, его нетрудно изобразить на листочке.

[Teosty]

Эйлеров цикл: 1 -> 6 -> 7 -> 1 -> 4 -> 5 -> 6 -> 4 -> 3 -> 5 -> 2 -> 4 -> 3 -> 2 -> 1
Это правильно?

[arseniiv]

А где ребро 4—7?

Вы просто нарисуйте рёбра одним цветом, а потом обводите другим — тогда увидите, что осталось.

[Teosty]

Спасибо, разобрался!

[sqribner48]

... для других пользователей
1. Описание задачи не полное. Написано:"Помогите найти эйлеров цикл в неориентированном графе, заданном матрицей смежности". А по приложенному далее рисунку видно, что граф простой неориентированный без петель и кратных ребер.
Так и следовало бы написать.
2. Матрица смежности составлена не правильно - в диагонали вместо нулей стоят единицы. Кажется на это было указано модератором, но ТС почему-то не среагировал.

... для начинающих (других) пользователей
а) Матрица смежности простого неориентированного графа без петель и кратных ребер в диагонали имеет нули.
б) Граф $G$ имеет эйлеров цикл, когда каждая вершина графа $G$ имеет четную степень (в любой хорошей книге по теории графов, например, в книге Ф. Харари)