Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 6 ] 
Автор Сообщение
 Заголовок сообщения: Эйлеров цикл и контуры.
СообщениеДобавлено: 30 окт 2017, 16:25 
Не в сети
Одарённый
Зарегистрирован:
02 дек 2015, 11:16
Сообщений: 179
Cпасибо сказано: 93
Спасибо получено:
3 раз в 3 сообщениях
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Доброго времени суток!
Возникли следующие вопросы:
1. В орграфе, можно ли считать петлю за контур любой длины ? Допустим является ли контуром длиной 3 петля с вершиной в точке 1 ? Как по-мне, да, является.
2. Необходимо найти Эйлеров цикл в неориентированном графе с петлями.
Использую алгоритм Флёри, но не знаю что делать с петлями. Их просто не учитывать при построении цикла?
3. Аналогичный двум предыдущим, только для гамильтонова графа. Как воспользоваться теоремой Дирака, если граф содержит петли? (ибо она ведь для простых графов)
4. Посоветуйте, пожалуйста, литературы по хорошей литературы по теории графов.
За ранее благодарен.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Эйлеров цикл и контуры.
СообщениеДобавлено: 30 окт 2017, 17:41 
Не в сети
Последняя инстанция
Зарегистрирован:
06 июн 2013, 16:17
Сообщений: 2590
Cпасибо сказано: 104
Спасибо получено:
746 раз в 701 сообщениях
Очков репутации: 158

Добавить очки репутацииУменьшить очки репутации
Teratore писал(а):
1. В орграфе, можно ли считать петлю за контур любой длины ? Допустим является ли контуром длиной 3 петля с вершиной в точке 1 ? Как по-мне, да, является.
Зависит от определения в учебнике, которым вы пользуетесь. Например, в книге Новиков Ф.А. Дискретная математика для программистов. Питер, 2009, с. 248 говорится: "Для псевдографов обычно особо оговаривают, считаются ли петли циклами". (Контур — это цикл в ориентированном графе.) Но если петлю считать циклом, то она будет циклом длины 1, т.к. цикл по определению — это замкнутая цепь, а цепь — это маршрут (самое общее понятие), где все ребра различны.

Teratore писал(а):
2. Необходимо найти Эйлеров цикл в неориентированном графе с петлями. Использую алгоритм Флёри, но не знаю что делать с петлями. Их просто не учитывать при построении цикла?
Просто каждый раз, когда вы заходите в вершину, проходите по петле, если она есть. Наличие или отсутствие петель не влияет на эйлеровость.

Teratore писал(а):
3. Аналогичный двум предыдущим, только для гамильтонова графа. Как воспользоваться теоремой Дирака, если граф содержит петли? (ибо она ведь для простых графов)
В гамильтоновом цикле не требуется использовать петли, так как нужно пройти по всем вершинам. То есть петли можно игнорировать.

Teratore писал(а):
4. Посоветуйте, пожалуйста, литературы по хорошей литературы по теории графов.
Не уверен, что это лучшие книги, но вот.

[0] Хаггарти Р. Дискретная математика для программистов. М.: Техносфера, 2012.

[1] Новиков Ф.А. Дискретная математика для программистов. СПб: Питер, 2011.

[2] Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990.

[3] Харари Ф. Теория графов. М.: Мир, 1973.

[4] Нефедов В.Н., Осипова В.А. Курс дискретной математики: Учеб. пособие. М.: Изд-во МАИ, 1992.

[5] Берж К. Теория графов и ее применения. М.: Изд. иностр. лит., 1962.

[6] Уилсон Р. Введение в теорию графов. М.: Мир, 1977.

Книга [0] самая простая и краткая. Книга [1] довольно полная и неплохая, но отдельные темы лучше смотреть в другом месте.

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю 3D Homer "Спасибо" сказали:
Teratore
 Заголовок сообщения: Re: Эйлеров цикл и контуры.
СообщениеДобавлено: 30 окт 2017, 18:28 
Не в сети
Одарённый
Зарегистрирован:
02 дек 2015, 11:16
Сообщений: 179
Cпасибо сказано: 93
Спасибо получено:
3 раз в 3 сообщениях
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
3D Homer писал(а):
а цепь — это маршрут (самое общее понятие), где все ребра различны

Хм.. У меня вот в пособии ВУЗа написано так:
"Рассмотрим теперь ориентированные графы. Пусть G ( X, E, Φ ) – орграф. Конечная последовательность дуг e1 , e2 , ... , en графа G называется путем длиной n, или ориентированным маршрутом длины n, если существует такая последовательность вершин x0 , x1 , ... , xn , что Φ ( ei ) = ( xi-1 , xi ), где i = 1, 2, ... . Путь μ записывается в виде μ = { e1 , e2 , ... , en } или в виде μ = { x0 , x1 , ... , xn }. В этом случае говорят, что путь состоит из дуг e1 , e2 , ... , en , выходит из вершины x0 и заходит в вершину xn . Путь μ называется простым, если все его дуги различны, и элементарным, если все его вершины различны"

Теперь я вообще ничего не понимаю. Если руководствоваться данным определением - то путь ~ маршрут. Т.е если мне нужно найти кол-во путей длины 4 я матрицу смежности вершин возвожу в 4-ю степень и суммирую элементы.

Тогда получается, что цепь может содержать одинаковые ребра => петля это контур n-й длины.

3D Homer писал(а):
Просто каждый раз, когда вы заходите в вершину, проходите по петле, если она есть. Наличие или отсутствие петель не влияет на эйлеровость.

Если у меня исходная вершина содержит петлю, мне вначале обойти петлю, а затем остальные вершины? Или в конце петлю обойти? Хотя, разницы никакой, наверное. Просто мне нужно цикл записать в виде вершин. Т.е если вершина 1 содержит цикл то получится так: 1->1->2 выглядит как-то странно, ну да ладно, меня больше первый вопрос интересует.

3D Homer писал(а):
В гамильтоновом цикле не требуется использовать петли, так как нужно пройти по всем вершинам. То есть петли можно игнорировать.

Здесь понял, спасибо.
3D Homer писал(а):
Не уверен, что это лучшие книги, но вот.

Мне нужны были операции на графах в матричном виде, в итоге я так и не нашел. Посмотрю в книгах, которые Вы предложили, может найду.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Эйлеров цикл и контуры.
СообщениеДобавлено: 30 окт 2017, 18:40 
Не в сети
Последняя инстанция
Зарегистрирован:
06 июн 2013, 16:17
Сообщений: 2590
Cпасибо сказано: 104
Спасибо получено:
746 раз в 701 сообщениях
Очков репутации: 158

Добавить очки репутацииУменьшить очки репутации
У Новикова путешествие без ограничений — маршрут, маршрут без повторяющихся ребер — цепь, цепь без повторяющихся вершин — простая цепь. Цикл — замкнутая цепь, простой цикл — простая замкнутая цепь. В орграфах цепь называется путем, цикл — контуром. У вас путь = маршрут, простой путь — без повторяющихся ребер (у Новикова это путь), элементарный путь — без повторяющихся вершин (у Новикова это простой путь). Поэтому я и говорю, что нужно смотреть в конкретную книгу, т.к. определения, к сожалению, различаются.

Teratore писал(а):
Тогда получается, что цепь может содержать одинаковые ребра => петля это контур n-й длины.
Вы ничего не сказали про определение контура в вашей книге.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Эйлеров цикл и контуры.
СообщениеДобавлено: 30 окт 2017, 19:00 
Не в сети
Одарённый
Зарегистрирован:
02 дек 2015, 11:16
Сообщений: 179
Cпасибо сказано: 93
Спасибо получено:
3 раз в 3 сообщениях
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
3D Homer писал(а):
Вы ничего не сказали про определение контура в вашей книге.

Его там просто нету.
3D Homer писал(а):
Просто каждый раз, когда вы заходите в вершину, проходите по петле, если она есть.

А здесь аналогичная ситуация? Зависит от учебника? То что петли не влияют на Эйлеровость это понятно, но вот нужно ли при построении цикла их обходить - я пока не знаю.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Эйлеров цикл и контуры.
СообщениеДобавлено: 30 окт 2017, 22:21 
Не в сети
Последняя инстанция
Зарегистрирован:
06 июн 2013, 16:17
Сообщений: 2590
Cпасибо сказано: 104
Спасибо получено:
746 раз в 701 сообщениях
Очков репутации: 158

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю 3D Homer "Спасибо" сказали:
Teratore
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ Сообщений: 6 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Эйлеров цикл

в форуме Дискретная математика, Теория множеств и Логика

evaf

6

125

15 ноя 2020, 16:25

Эйлеров граф

в форуме Дискретная математика, Теория множеств и Логика

kyle22

1

224

21 фев 2016, 13:43

Эйлеров интеграл

в форуме Интегральное исчисление

Derevyashka

0

152

10 дек 2018, 17:03

Цикл while

в форуме MATLAB

olgaz

3

338

06 май 2016, 21:40

Цикл в цикле

в форуме Теория вероятностей

Elena gidrotechnik

0

196

15 май 2014, 22:34

Цикл в транспортной задаче

в форуме Исследование операций и Задачи оптимизации

ChazAshley

2

2550

24 апр 2014, 10:01

Цикл for с двумя переменными, система диф. уравнений

в форуме Maple

Mokusko

1

767

04 май 2015, 21:42


Часовой пояс: UTC + 3 часа [ Летнее время ]



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

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


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

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved