![]() КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Эйлеровы цепи и циклы в графах. Эйлеровы графы. Гамильтоновы цепи и циклы в графах. Гамильтоновы графыОпределение: Эйлеровацепь в графе – это цепь, содержащая все ребра графа, причем через каждое ребро проходим ровно один раз. Определение: Эйлеровцикл в графе – цикл, содержащий все ребра графа, причем через каждое ребро проходим ровно один раз. Определение: Граф, обладающий эйлеровым циклом, называется эйлеровымграфом. Необходимое условие существования эйлерова цикла и эйлеровой цепи – связность графа. Теорема(необходимое и достаточное условия существования эйлерова цикла): Связный неориентированный псевдограф тогда и только тогда является эйлеровым (т. е. обладает эйлеровым циклом), когда степень каждой его вершины есть четное число. Теорема (необходимое и достаточное условия существования эйлеровой цепи): Связный неориентированный псевдограф обладает эйлеровой цепью тогда и только тогда, когда он имеет ровно две вершины нечетной степени. Замечание: Если в графе G эйлерова цепь существует, то она цепь соединяет вершины нечетной степени. Рассмотрим задачу построения алгоритма выделения эйлеровой цепи или эйлерова цикла в псевдографе. Утверждение 1: Пусть G = (V, X) – связный псевдограф. X( Утверждение 2: Если G=(V,X) – связный псевдограф, не содержащий висячих вершин, то в графе G существует хотя бы один цикл. Алгоритм выделения эйлерова цикла в связном мультиграфе (алгоритм Флери): Пусть G = (V, X), X Шаг 1: Выделим из графа G цикл Шаг 2: Удаляем из графа G’ ребра, принадлежащие множеству X( Шаг 3: Присваиваем l:= l + 1 и переходим к шагу 2. Шаг 4: По построению Шаг 5: Присваиваем l: = l – 1
Рассмотрим задачу о выделении эйлеровой цепи. Пусть дан связный псевдограф G = (V, X), X ≠ Ø , имеющий ровно две вершины v и w нечетной степени. Добавим в G ребро (v,w), получим псевдограф G’ с четными степенями вершин. Выделим из G’ эйлеров цикл (по алгоритму) и удалим из него ребро (v,w). В результате получим эйлерову цепь, соединяющую v,w. Определение: Гамильтоновцикл (цепь) – цикл (цепь), проходящий (проходящая) через каждую вершину графа в точности по одному разу. Гамильтонов цикл (цепь) всегда является простым (простой). Он (она) может не содержать всех ребер графа. Определение: Граф, обладающий гамильтоновым циклом, называется гамильтоновымграфом. С понятием гамильтоновых циклов тесно связана так называемая задача коммивояжера: в нагруженном графе G определить гамильтонов цикл минимальной длины (иными словами, коммерсант должен совершить поездку по городам и вернуться обратно, побывав в каждом городе ровно один раз, и при этом стоимость такой поездки должна быть минимальной). Математическая постановка задачи выглядит так: требуется найти гамильтонов цикл минимального веса. На первый взгляд, понятие «гамильтонов цикл» сходно с понятием эйлерова цикла. Пример: – существуют гамильтонов и эйлеров циклы
– существует эйлеров цикл, но не существует гамильтонова цикла. – не существует эйлерова цикла и не существует гамильтонова цикла. Данные примеры показывают независимость понятий гамильтонова и эйлерова циклов. Несмотря на схожесть задач о нахождении этих циклов, решение о нахождении гамильтонова цикла значительно сложнее. Известны следующие достаточные условия существования гамильтоновых циклов в связном неорграфе G без петель, имеющем n полнота графа (если граф полный, то он гамильтонов); если для любых двух различных несмежных вершин vi, vj (i если для любой вершины v графа G выполнено условие δ(v) Необходимое условие существования гамильтонова цикла – связность графа и отсутствие точек сочленения.
|