2014 dxdy logo

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

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



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


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

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

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

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

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



Начать новую тему Ответить на тему
 
 Поиск Эйлерового цикла
Сообщение26.05.2014, 01:19 


26/05/14
5
Доброе время суток.
Помогите найти эйлеров цикл в неориентированном графе, заданном матрицей смежности:
$
\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, но к этой матрице даже не знаю как подступиться (для начала надо хотя бы определить есть ли эйлеров цикл)

 Профиль  
                  
 
 Posted automatically
Сообщение26.05.2014, 01:21 
Модератор


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

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

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

 Профиль  
                  
 
 Posted automatically
Сообщение26.05.2014, 01:36 
Модератор


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

 Профиль  
                  
 
 Re: Поиск Эйлерового цикла
Сообщение26.05.2014, 07:24 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Поиск Эйлерового цикла
Сообщение26.05.2014, 08:36 


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

 Профиль  
                  
 
 Re: Поиск Эйлерового цикла
Сообщение26.05.2014, 08:46 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Поиск Эйлерового цикла
Сообщение26.05.2014, 08:57 


26/05/14
5
Изображение
Эйлеров цикл: 1 -> 6 -> 7 -> 1 -> 4 -> 5 -> 6 -> 4 -> 3 -> 5 -> 2 -> 4 -> 3 -> 2 -> 1
Это правильно?

 Профиль  
                  
 
 Re: Поиск Эйлерового цикла
Сообщение26.05.2014, 15:31 
Заслуженный участник
Аватара пользователя


27/04/09
19162
Уфа
А где ребро 4—7?

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

 Профиль  
                  
 
 Re: Поиск Эйлерового цикла
Сообщение26.05.2014, 18:18 


26/05/14
5
Спасибо, разобрался!

 Профиль  
                  
 
 Re: Поиск Эйлерового цикла
Сообщение05.02.2015, 11:16 


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

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

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

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



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

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


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

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