67603

Эйлеровы циклы и цепи

Лекция

Математика и математический анализ

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

Русский

2014-09-12

62 KB

1 чел.

Лекция №12

Эйлеровы циклы и цепи

Нужно пройти по всем мостам по одному разу и вернуться обратно..

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

Доказательство ||

Если в G имеется петля, то это уже цикл, если в G есть кратные ребра, то это тоже цикл. Допустим, что петель и кратных ребер нет.

Пусть v1 и v2 – произвольные смежные вершины. Будем строить последовательность v1, v2, v3… такую, что для любого i>2 вершины vi, vi-1 смежны и vivi-1 (т.к. в G нет висячих вершин, то эту последовательность можно продолжать неограниченно). Но рано или поздно какая-то из вершин повторится. Это и будет искомый цикл.

Утв. Для того чтобы связный псевдограф G обладал эйлеровым циклом необходимо и достаточно чтобы степени всех его вершин были четными.

См. алгоритм.

Утв. Для того чтобы связный псевдограф G обладал эйлеровой цепью необходимо и достаточно, чтобы он имел ровно 2 вершины нечетной степени.

(Нужно соединить начало и конец. Тогда задача сводится к предыдущей).

Алгоритм выделения эйлерова цикла в связном мультиграфе с четными степенями вершин

1) Выделим из G цикл 1. (т.к. степени верш. четны, то висячие верш. отсутств.). Положим l=1, G’=G.

2) Удаляем из G’ ребра, принадлежащие выделенному циклу. Полученный псевдограф снова обозначаем G’. Если в G’ отсутствуют ребра, то переходим к шагу 4.

3) Выделяем из G’ цикл. Присваиваем l:=l+1 и переходим к шагу 2.

4) По построению выделенные циклы содержат все ребра по одному разу. Если l:=1, то искомый эйлеров цикл найден (конец работы алгоритма). В противном случае находим циклы, содержащие хотя бы по одной общей вершине (в силу связности графа это всегда можно сделать). Склеиваем эти циклы. Повторяем эти операции, пока не останется один цикл. Он и является искомым.

Пример. Задача о Кенигсбергских мостах не имеет решения, т.к. есть вершины с нечетными степенями.

Гамильтоновы циклы и цепи

Опр || Пусть G псевдограф. Цепь и цикл в G называются гамильтоновыми если они проходят через каждую вершину ровно один раз.

Задача коммивояжера: в нагруженном графе G определить гамильтонов цикл минимальной длины.

Решение этой задачи проводится с помощью метода ветвей и границ.

Гамильтоновы цепи и циклы относятся к числу специальных маршрутов в графах. Очевидно, что свойство маршрутов: проходить через каждую вершину не более одного раза является латинским, а следовательно, все гамильтоновы циклы и цепи можно получить применяя метод латинской композиции.

В этом случае все гамильтоновы цепи будут перечислены в непустых элементах матрицы Ln-1(G), за исключением элементов главной диагонали, а все гамильтоновы циклы – в каждом диагональном элементе матрицы Ln(G).


Деревья и циклы

Опр. Граф G называется деревом если он является связным и не имеет циклов.

Опр. Граф G называется лесом если все его компоненты связности - деревья.

Свойства деревьев:

Следующие утверждения эквивалентны

1) Граф G есть дерево.

2) Граф G является связным и не имеет простых циклов.

3) Граф G является связным и число его ребер ровно на 1 меньше числа вершин.

4)   две различные вершины графа G можно соединить единственной (и при этом простой) цепью.

5) Граф G не содержит циклов, но, добавляя к нему любое новое ребро, получаем ровно один и притом простой цикл

Утв. Если у дерева G имеется, по крайней мере, 1 ребро, то у него найдется висячая вершина.

Предположим, что в графе G нет висячей вершины, тогда найдется цикл (в начале лекции это было доказано), тогда граф - не дерево.

Утв.  Пусть G связный граф, а  висячая вершина в G, граф  получается из G в результате удаления вершины  и инцидентного ей ребра. Тогда  тоже является связным.

Д-во: иллюстрация.

Утв. Пусть G - дерево с n-вершинами и m-ребрами. Тогда m(G)=n(G)-1.

Если m<n-1 то граф не связный.

Если m>n-1, и висячих вершин в графе нет, то можно выделить цикл, а следовательно, это – не дерево. В противном случае удалим висячую вершину вместе с инцидентным ей ребром. Повторяя эту операцию n-2 раза, придем к графу с двумя вершинами и более чем одним ребром это не дерево.

Утв. Пусть G – дерево. Тогда любая цепь в G будет простой.

Если цепь – не простая, то в G есть циклы  G – не дерево.

Цепь единственна по той же причине.

Опр. Остовным деревом связного графа G называется любой его подграф, содержащий все вершины графа G и являющийся деревом.

Пусть G – связный граф. Тогда остовное дерево графа G должно содержать n(G)-1 ребер. Значит, для получения остовного дерева из графа G нужно удалить  ребер. Число  называется цикломатическим числом графа G.

Алгоритм выделения остовного дерева

1) Выберем в G произвольную вершину , которая образует подграф, являющийся деревом. Положим i=1.

2) Если i=n(G), то задача решена и Gi – искомое остовное дерево графа G. Иначе переходим к п. 3.

3) Пусть уже построено дерево  являющееся подграфом графа G, в которое входят вершины , где . Строим граф , добавляя к графу Gi новую вершину , смежную с некоторой вершиной  графа  и  новое ребро . Во-первых, это можно всегда сделать, поскольку граф связен. Во-вторых,  - дерево, т.к. если в  не было циклов, то и в  их не могло появиться.

Присваиваем i:=i+1 и переходим к шагу 2).

Замечание. Остовное дерево может быть выделено, вообще говоря, не единственным способом.

Если граф – нагруженный, то можно выделить остовное дерево с минимальной суммой длин содержащихся в нем ребер.

Алгоритм выделения минимального остовного дерева нагруженного графа

1) Выберем в графе G ребро минимальной длины. Вместе с инцидентными ему двумя вершинами оно образует подграф G2 графа G. Положим i=2.

2) Если i=n(G), то задача решена и Gi – искомое минимальное ост. дерево графа G. Иначе переходим к шагу 3).

3) Строим граф Gi+1, добавляя к графу Gi новое ребро минимальной длины из оставшихся, которое инцидентно какой-нибудь верш. графа Gi и одновременно вершине, не содержащейся в Gi. Вместе с этим ребром включаем в Gi+1 и эту инцидентную ему верш. Присваиваем i:=i+1 и переходим к шагу 2).


 

А также другие работы, которые могут Вас заинтересовать

22564. Визначення та класифікація емоцій 24 KB
  Визначення та класифікація емоцій Емоції рефлекторна адаптаційна психофізіологічна реакція яка повязана з проявом субєктивного ставлення до значущої ситуації і забезпечує організацію доцільної поведінки. Емоції поділяють на вищі та нижчі. Нижчі емоції найбільш елементарні повязані з органічними потребами тварин і людей поділяються на 2 види : 1 гомеостатичні проявляються в вигляді неспокою пошуковорухової активності спраги голоду і ін. Вищі емоції виникаютьлишу у людини в звязку з задоволенням соціальних потреб інтелектуальних...
22565. Функції емоцій 23 KB
  Сигнальна функція полягає в тому що емоції сигналізують про корисний чи негативний вплив даного організму чи успішність чи неуспішність виконання даної дії. Це призводить до моментальної мобілізації всіх систем організму для реакції відповіді характер якої залежить від того сигналом корисного чи негативного впливу на організм є даний подразник. Таким чином впливи що надходять з зовнішнього середовища і від самого організму призводять до виникнення емоційних переживань що дають загальну якісну характеристику фактору що впливають...
22566. Основні фізіологічні теорії емоцій 25 KB
  Основні фізіологічні теорії емоцій В першій класичній теорії відомій як теорія Джеймся Ланге робили висновок про характеристику стенічних та астенічних емоційних станів.Пізніше Кеннон та Бард показали що емоції гніву та стаху під впливом таламічних розрядів супроводжуються повишеним поступанням адреналіну в кров що призводить до розвитку симпатікотонії яка відіграє позитивну роль в підготовці організму до діяльності і навіть боротьби внаслідок чого ця теорія отримала незву таламічної теорії емоцій. Кортикальні емоційні процеси...
22567. Сон 42 KB
  Існує величезна кількість емпіричних даних і забобонів щодо значення сну і сновидінь але справжнє наукове вивчення сну почалося лише у другій половині ХІХ ст. Прибічники хімічної теорії сну спочатку пояснювали сон накопиченням в організмі гіпнотоксичних речовин молочна вугільна та карбонові кислоти холестерин а нині надають важливого значення особливим хімічним регуляторам сну таким як речовина сну фактор сну чи пептид дельтасну які являють низькомолекулярні поліпептиди 850 920 Да . Кортикальна теорія сну І. Нарешті...
22568. будливий та гальмівний постсиниптичні потенціали 23.5 KB
  Постсинаптичне гальмування ГПСП обумовлене виділенням пресинаптичним закінченням аксона гальмівного медіатора який знижує або гальмує збудливість мембран соми і дендритів нерв клітини з якою він контактує. Прикладами гальмівних нейронів є клітини Реншоу в спинному мозку клітини Пуркіньє мозочку зірчасті клітини кіркової речовини великого мозку . Збудження нейрона супроводжуеться змінами метаболізму зокрема синтезу РНК та іншими зрушеннями в процесі білкового синтезу посиленням теплопродукції поглинанням кисню які відображають...
22569. Постсинаптичне гальмування у ЦНС та його природа.Значення ггальмування у роботі 22.5 KB
  Значення ггальмування у роботі. Гальмування особливий нервовий процес який зумовлюється збудженням і зовнішньо проявляється пригніченням іншого збудження. Постсинаптичне гальмування ГПСП обумовлене виділенням пресинаптичним закінченням аксона гальмівного медіатора який знижує або гальмує збудливість мембран соми і дендритів нерв клітини з якою він контактує.
22570. ЦНС 22.5 KB
  Особливе місце в цій складній організації займае місце ЦНС що повязує в функціональну єдність всі клітини тканини і органи людського організму. Дякуючи великій кількості різних рецепторів ЦНС сприймає багаточисельні зміни що виникають в зовн средовищі і всередині організму і відіграє велику роль в регуляції всіх сторін життєдіяльності огранізму в зовн середовищі. Процеси що відбуваються в ЦНС лежать в основі психічної діяльності та поведінки людини. Діяльність ЦНС найчастіше наз координаційною або узгоджувальною.
22571. Спинний мозок 49.5 KB
  Він є сегментарним органом: у людини від спинного мозку відходять 31 пара спинномозкових корінців у жаби 10 які у кожному сегменті поділяються на дві частини: на передній вентральний і задній дорзальний корінці. Сіра речовина спинного мозку на поперечному перетині має вигляд метелика або літери Н . Є також дорзальні роги спинного мозку з'єднані з вентральними широкою перетинкою сірої речовинитак зване тіло сірої речовини . Крім вентральних і дорзальних рогів у грудному відділі спинного мозку є бокові роги сірої речовини рис.
22572. Рефлекси спинного мозку 24 KB
  Це залежить від сили подразників їх просторової та часової взаємодії а також від стану нервових центрів спинного мозку. Нервові центри спинного мозку також необхідні для регуляції як соматичних так і вегетативних функцій.Нервові центри шийного відділу спинного мозку виявляють кооординуючий вплив на активність мотонейронів які інервують мязи згиначі і розгиначі нижчележачих відділів тіла.