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).


 

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

21386. Передающее устройство ВГ-020 37.25 KB
  Диапазон частот передатчика 100 400 МГц. Мощность на выходе передатчика не менее 1000 Вт. Время перестройки передатчика на любую частоту 2 мс. Потребляемая мощность передатчика не более 16 кВт без системы охлаждения.
21387. Система электропитания станции. Меры безопасности при работе на станции помех 58.25 KB
  Устройство и принцип работы АСП Р 934У Занятие №6Система электропитания станции. Меры безопасности при работе на станции помех Вопрос№1 Назначение технические характеристики состав устройство и принцип работы системы электропитания. Система электропитания станции предназначена для обеспечения питанием аппаратуры изделия защиты цепей питания от коротких замыканий и перегрузок коммутации цепей а также защиты обслуживающего персонала от поражения электрическим током. Технические характеристики Система электропитания обеспечивает...
21388. ПРАВО СОБСТВЕННОСТИ И ДРУГИЕ ВЕЩНЫЕ ПРАВА 23.75 KB
  наиболее крупные структурные подразделения отдельной отрасли права Это совокупность ГП норм регулирующих отношения собственности Содержание этих норм направленных на регулирование отношений собственности все цело определяются специфическими особенностями Частные имущественные отношения собственности отличаются от других ЧИО ПОНЯТИЕ ОТНОШЕНИЙ СОБСТВЕННОСТИ Собственность как экономическая категория Большинство экономистов и юристов давно поняли что собственность это не вещь и не отношение к вещи а это отношения которые складываются между...
21389. Другие вещные права 21.76 KB
  Вещное право предоставляет управмочнному лицу юр возможность удовлетворять свои потребости за счёт непосредственного взаимодейтсвия с вещью. Вещное право это право не на какуюто вещь право на поведение других. Для удовлетворения потребностей человек нуждается в вещах но зачем ему право если у него есть вещь а это объясняется следующим что удовлетворенияе потребностей в обещстве и любое вещное право и нужно чтобы обеспечить такое повдееие со строны окружающ с при котором можно было бы бесперпятсвенно удовлторять свои потребности за...
21390. ОСНОВАНИЕ ВОЗНИКНОВЕНИЕ И ПРЕКРАЩЕНИЕ ВЕЩНЫХ И ДРУГИХ ПРАВ 23.58 KB
  право собственности т. такой критерий не работает Мы опираемся на критерий воли собственника ПЕРВОНАЧАЛЬНЫЕ СПОСОБЫ Производство изготовление создание вещей: статья 218 ГК: лицо создавшее вещь для себя с соблюдением требования закона становится собственником этой вещи при этом для движимой вещи право собственности в момент ее создания а для недвижимости статья 219 ГК: право собственности на здания сооружения и другое вновь созданное имущество подлежащее гос регистрации возникает с момента такой регистрации Спецификация: изготовление...
21391. ГРАЖДАНСКОЕ ПРАВО КАК ОТРАСЛЬ ПРАВА 26.5 KB
  надо выявить те свойства которые входят в предмет одной отрасли гражданского права Легальное определение статья 2 ГК РФ: перечень наиболее типычных общественных отношений входящих в ГП: отношения собственности обязательственные отношения результаты по поводу интеллектуальной деятельности; предмет ГП входят имущественные и личные неимущественные отношения основанные на равенстве автономии воли и имущественной самостоятельности их участников Определяются внешние признаки В научном определении включаются сущностные признаки т. все обществеенные...
21392. ПРИНЦИПЫ ГРАЖДАНСКОГО ПРАВА 19.19 KB
  их применение все цело зависит от усмотрения участников ГО статья 617; императивных норм гораздо меньше один из недостатков что их еще достаточно много что явно не оправданно статья 807договор займа реальный договор Пункт 1 статья 9 субъекты ГП по своему усмотрению осуществляют принадлежащие им субъективные права в плановой экономике не редко субъекты осуществляли свои права по указанию другихсвобода усмотрения при осуществлении ими своих субъективных прав не безгранична и существует статья 10 пределы осуществления гражданских прав...
21393. СИСТЕМА ГП 28.57 KB
  общие нормы не повторяются в отдельных институтах ГП Особенная часть ГП состоит из подразделений правовые нормы которых рассчитаны на регулирование только одного вида оо входящих в предмет ГП Наиболее крупными подразделениями особенной части являются подотрасли Содержащиеся в подотраслях нормы ГП предназначены для регулирования только одного вида оо состоящих предмет ГП: Право собственности и другие вещные права Право на результаты интеллектуальной деятельности человека которые предназначены для отношений связанные с результатом...
21394. ДЕЙСТВИЕ ГЗ 22.07 KB
  опубликован в течение 7 дней после его подписания президентом официальным опубликованием считается первая публикации закона либо в рос газете либо в собрании законодательства Рф либо парламентской РФ Вступает в силу по истечении 10 дней после дня официального опубликования если самим законом не установлен иной порядок вступления его в силу Вступление в силу подзаконных нпа Указ президента РФ О порядке опубликования и вступления в силу актов президента правительства рф и нормативных актов федеральных органов исполнительной власти от 17.1997...