Эйлеровы графы.

Связность графов.

Операции над графами.

Удаление вершины V или ребра U графа, а переход к подграфу - это операции, с помощью которых можно получить граф с меньшим числом элементов. Однако известны операции позволяющие, получать графы с большим числом элементов.

Добавление ребра. Если вершина vi и uj не смежны, то можно построить граф G+u, где u=(vi,vj).

Объединение. Граф H называется объединением графов F и G, если VH=VF U VG и UH=UF U UG. Объединение G и F называют дизъюнктивным, если VF * VG =∅. Пересечением графов G и F называется граф H такой, что VH=VF ∩VG, UH=UF ∩ UG обозначается H=G∩F.

Произведением G1 * G2 =G называется граф, для которого VG=V1*V2- декартово произведение множеств вершин исходных графов, а UG строится так: вершин (V11, V12) и (V21,V22) смежны в графе G тогда и только тогда, когда или V11=V21 ,а V12и V22 соединены в G2, или V12=V22 ,а V11и V21 соединены в G1.

Важным понятием в теории графов является связность. С ней связано решение ряда прикладных задач, в частности задач кодирования состояний цифрового автомата.

Для неографа орграфа понятие связности несколько отличаются.

Две вершины неографа считаются связанными, если существует маршрут, соединяющии эти вершины.

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

Орграф называется сильно связным, если для любых его двух вершин vi и vj найдется путь из vi в vj и путь из vj в vi.

Орграф называется несильно связным, если для любых его двух вершин vi и vj найдется путь либо из vi в vj либо из vj в vi.. В остальных случаях граф называется несвязным.

Ребро при удалении, которого граф превращается в несвязный называют мостом.

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

Граф, не имеющий мостов и сочленений, называется неразделимым.

Задачи, связанные с эйлеровами и, особенно, с гамильтоновыми, графами часто встречаются в головоломках, в игровых задачах, на практике, в частности, когда для осуществления некоторого комплекса операции необходимо провести их в таком порядке, чтобы эффективность их выполнения была максимальной. К тому же классу задач и известная задача о кенигсбергских мостах, которая на языке теории графов

формулируется так: есть ли в мультиграфе G цикл, соединяющий все ребра мультиграфа? В 1736 году Эйлер доказал, что эта задача неразрешима, но при этом сформулировал важное условие, при котором связный граф содержит эйлеров цикл. Цикл называется эйлеровым, если он содержит все ребра графа, а связный граф с эйлеровым циклом называется эйлеровым.

Эйлеров граф можно нарисовать, не отрывая ручки от бумаги и не повторяя линий. Существует также понятие эйлеровой цепи, т.е цепи содержащей все ребра графа. Эйлер в 1736 году сформулировал теорему: связный граф является эйлеровым тогда и только тогда, когда степени всех его вершин четны.

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

Один из алгоритмов нумерации называется алгоритмом Флёри:

Начиная, с произвольной вершины Vi присваивается произвольному ребру (Vi, Vi+1) номер 1, затем это ребро вычеркивается и переходит в вершину Vi+1.

Пусть Vi- это вершина, в которую пришли на предыдущем шаге, а R-это номер, присвоенный некоторому ребру на этом шаге. Выбирается любое ребро инцидентное вершине Vi, причем мост выбирается только в том случае, когда нет других вариантов. Ребро обозначается R+1 и вычеркивается.

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