Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 1 |
[ Сообщений: 6 ] |
|
Автор | Сообщение | |
---|---|---|
Teratore |
|
|
Возникли следующие вопросы: 1. В орграфе, можно ли считать петлю за контур любой длины ? Допустим является ли контуром длиной 3 петля с вершиной в точке 1 ? Как по-мне, да, является. 2. Необходимо найти Эйлеров цикл в неориентированном графе с петлями. Использую алгоритм Флёри, но не знаю что делать с петлями. Их просто не учитывать при построении цикла? 3. Аналогичный двум предыдущим, только для гамильтонова графа. Как воспользоваться теоремой Дирака, если граф содержит петли? (ибо она ведь для простых графов) 4. Посоветуйте, пожалуйста, литературы по хорошей литературы по теории графов. За ранее благодарен. |
||
Вернуться к началу | ||
3D Homer |
|
|
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] довольно полная и неплохая, но отдельные темы лучше смотреть в другом месте. |
||
Вернуться к началу | ||
За это сообщение пользователю 3D Homer "Спасибо" сказали: Teratore |
||
Teratore |
|
|
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 писал(а): Не уверен, что это лучшие книги, но вот. Мне нужны были операции на графах в матричном виде, в итоге я так и не нашел. Посмотрю в книгах, которые Вы предложили, может найду. |
||
Вернуться к началу | ||
3D Homer |
|
|
У Новикова путешествие без ограничений — маршрут, маршрут без повторяющихся ребер — цепь, цепь без повторяющихся вершин — простая цепь. Цикл — замкнутая цепь, простой цикл — простая замкнутая цепь. В орграфах цепь называется путем, цикл — контуром. У вас путь = маршрут, простой путь — без повторяющихся ребер (у Новикова это путь), элементарный путь — без повторяющихся вершин (у Новикова это простой путь). Поэтому я и говорю, что нужно смотреть в конкретную книгу, т.к. определения, к сожалению, различаются.
Teratore писал(а): Тогда получается, что цепь может содержать одинаковые ребра => петля это контур n-й длины. Вы ничего не сказали про определение контура в вашей книге. |
||
Вернуться к началу | ||
Teratore |
|
|
3D Homer писал(а): Вы ничего не сказали про определение контура в вашей книге. Его там просто нету. 3D Homer писал(а): Просто каждый раз, когда вы заходите в вершину, проходите по петле, если она есть. А здесь аналогичная ситуация? Зависит от учебника? То что петли не влияют на Эйлеровость это понятно, но вот нужно ли при построении цикла их обходить - я пока не знаю. |
||
Вернуться к началу | ||
3D Homer |
|
|
Эйлеров цикл проходит по всем ребрам, поэтому с большой вероятностью он должен проходить по петлям в псевдографе. Но если в курсе есть задачи на этот счет, то должно быть дано соответствующее определение.
|
||
Вернуться к началу | ||
За это сообщение пользователю 3D Homer "Спасибо" сказали: Teratore |
||
[ Сообщений: 6 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Эйлеров цикл | 6 |
125 |
15 ноя 2020, 16:25 |
|
Эйлеров граф | 1 |
224 |
21 фев 2016, 13:43 |
|
Эйлеров интеграл
в форуме Интегральное исчисление |
0 |
152 |
10 дек 2018, 17:03 |
|
Цикл while
в форуме MATLAB |
3 |
338 |
06 май 2016, 21:40 |
|
Цикл в цикле
в форуме Теория вероятностей |
0 |
196 |
15 май 2014, 22:34 |
|
Цикл в транспортной задаче | 2 |
2550 |
24 апр 2014, 10:01 |
|
Цикл for с двумя переменными, система диф. уравнений
в форуме Maple |
1 |
767 |
04 май 2015, 21:42 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 24 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |