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

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

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

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

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




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

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Эйлеров цикл и контуры.
СообщениеДобавлено: 30 окт 2017, 18:41 
Не в сети
Beautiful Mind
Зарегистрирован:
06 июн 2013, 17:17
Сообщений: 1121
Cпасибо сказано: 59
Спасибо получено:
321 раз в 305 сообщениях
Очков репутации: 97

Добавить очки репутацииУменьшить очки репутации
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, 19:28 
Не в сети
Одарённый
Зарегистрирован:
02 дек 2015, 12:16
Сообщений: 167
Cпасибо сказано: 89
Спасибо получено:
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, 19:40 
Не в сети
Beautiful Mind
Зарегистрирован:
06 июн 2013, 17:17
Сообщений: 1121
Cпасибо сказано: 59
Спасибо получено:
321 раз в 305 сообщениях
Очков репутации: 97

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

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

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

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

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

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Эйлеров цикл и контуры.
СообщениеДобавлено: 30 окт 2017, 23:21 
Не в сети
Beautiful Mind
Зарегистрирован:
06 июн 2013, 17:17
Сообщений: 1121
Cпасибо сказано: 59
Спасибо получено:
321 раз в 305 сообщениях
Очков репутации: 97

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

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

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

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

kyle22

1

91

21 фев 2016, 14:43

Эйлеров граф, обладающий висячей вершиной

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

iwan

0

219

29 ноя 2012, 13:02

Цикл while

в форуме MATLAB

olgaz

3

150

06 май 2016, 22:40

Цикл Карно

в форуме Молекулярная физика и Термодинамика

Kikki

0

508

07 июн 2013, 11:49

Цикл в цикле

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

Elena gidrotechnik

0

104

15 май 2014, 23:34

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

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

ChazAshley

2

726

24 апр 2014, 11:01

Цикл или программирование, а может что полегче?

в форуме MathCad

NICOTINE

0

282

30 мар 2014, 08:50

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

в форуме Maple

Mokusko

1

318

04 май 2015, 22:42

Отображение двумерного массива через цикл for

в форуме Maple

IOF

6

527

16 ноя 2013, 17:18

Газообразный азот проведён через обратимый цикл

в форуме Молекулярная физика и Термодинамика

student-himik

0

205

27 май 2012, 21:01


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



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

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


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

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

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

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