Док-во его корректности.

Пусть G-эйлеров граф, тогда степень каждой вершины четна. В силу этого алгоритм может закончить свою работу в начальной точке U. Построив при этом некоторый цикл С. Нужно док-ть,что цикл включ. все ребра графа G. Если это не так, то после удаления ребер С,граф распад-ся на компонеты связностей(В),хотя бы одна из них содерж. ребра. Пусть А-семейство всех ребер цикла С инцидентных вершинам В. Пусть а-номер ребра наибольший,полученный в результате работы алгоритма Флёри(а А).Тогда к моменту удаления этого ребра из графа оно было мостом. Однако это противоречит правилу алгоритма о выборе очередного ребра. Поскольку в компаненте В степень каждой вершины четна,то в ней сущ-т свой эйлеров цикл,идя по которому можно избежать преждевременного удаления моста.Т.о. доказана корректность алг. Флёри.

Циклы Гамильтона:теорема,ее следствие(теор.Дирака).Задача китайского почтальона.Задача коммивояжера.

Теорема. Пусть граф G(V,E) связный,граф с (n≥3) вершинами, для каждой пары различ. вершин u,v V: deg(u)+deg(v)≥n граф G явл. гамильтоновым.

Док-во: Пусть -макс. простой путь в графе G. Пусть а= deg(V1), b= deg(Vm) покажем, что перестановка вершин входивших в путь дает возможность формировать простой цикл. Если V1и Vm смежны, то - цикл и искомый цикл найден.Если V1 и Vm не смеж., то согласно теореме a+b≥n. Покажем теперь, что в данном случае вершины Vi и Vi+1,входящие в путь при условии, что V1иVi+1-смежны, Vm смеж. с Vi, если это так, то начнем путь с . Удалим ребро между Vi и Vi+1. Начнем новый путь с Vi+1 и продолжим его до вершины V1, продолжим путь дальше, и т.к. Vi и Vm смежны, мы получим . Движемся в обратном направл. и получим искомый цикл . Теперь покажем, что вершины Vi и Vi+1.входящие в путь и такие что Vi+1 смежна с V1, Vi смеж. с Vm. Предположим обратное, т.е. Vi не явл. смеж. ни к одной из вершин входящих в путь. Поскольку если вершина w не входящая в путь и смеж. с V1,то путь w V1V2… Vm простой, а это противоречит, что V1,V2,V3… Vn- макс. простой путь в графе G и тогда сущ-т а вершин вход-х в путь V1,V2,V3… Vn и смеж. с вершиной V n,аналогично сущ-т вершина вход-ая в путь V1,V2,V3… V m и смеж. с V m. Если включить вершину V1 в этот путь то он будет содерж. а+1 вершин, совпад-х с V1 или смеж. с ней. также вершины вход-е в путь V1,V2,V3… Vn и смеж. с Vm, или для которой вершины Vi, вход-ей в путь и смеж. с V m,вершина Vi+1 не явл. смеж. с V1,то путь содерж. а+1 вершин совпадающих с V1 или смеж. с ней и вершины,вход-щие в путь,которые не совп. с V1 и не смеж. с ней. Т.о. путь V1,V2,V3… Vn содерж. а+b+1 вершин,что невозможно=> сделанное предположение не верно и сущ-ют такие вершины Vi и Vi+1,которые входят в путь,причем Vi+1смеж. с V1, Vi смеж. с Vm. Т.о. искомый цикл получен. Предположим теперь для простоты,что вершины переобозначены,так что цикл имее вид V1,V2…VmV1. Покажем теперь,что этот цикл содерж. все вершины мн-ва V,если это не выполн-ся и вершина V` не совп. ни с одной из вершин цикла,то поскольку граф G связ. сущ-т путь из V` в вершину Vi цикла U,еще сущ-т вершина w не вход-ая в путь V1,V2,V3… Vn и смеж. с одной из вершин Vj-ых. Тогда w Vj Vj+1… Vm V1V2… Vj-1-простой путь,который длиннее пути V1,V2,V3…Vn,что явл. противоречием=> V1,V2,V3… V m V1-явл. гамильтоновым графом.

Следствие(теорема Дирака).

Если G(V,E) связный,граф с n вершинами(n≥3),если для некоторой вершины ϑ V выполн-ся deg(ϑ)≥n/2,то граф G имеет гамильтоновый цикл.