Связность графов и компоненты связности

Граф G(X,U), в котором все вершины соединены простой цепью на­зывается связным. Отношение связности вершин графа называется эк­вивалентностью. Классы эквивалентности по отношению к связности называются компонентами связности графа, или компонентой связно­сти графа называется его связный подграф.

На рис. 10.22, а граф имеет две компоненты связности, на рис. 10.20, 6 у графа 3 компоненты связности.

 

 

Рис. 10.22

Число компонент связности графа G обозначается k(G). Граф G явля­ется связным, когда k(G) = 1. Если k(G) > 1, то граф называется несвязным. Например, для графа на рис. 10.24 k(G) = 1, для графа (рис. 10.25) k(G) = 2 и для графа G, представленного на рис. 10.26, k(G) = 3.

Вершина графа G называется точкой сочленения, если ее удаление увеличивает число компонент связности. Мостом называется ребро гра­фа, удаление которого увеличивает число компонент связности. Блоком называется связный граф, не имеющий точек сочленения. На рис. 10.23, вграфе G: вершины х₃ и х₄ являются точками сочленения, ребро U₄ (x₃, х₄) называется мостом и связные подграфы { x₁,x₂,x₃ }, { x_4,x₅,x₆ }, { x_s,x₆,x₇ }, { х₄,х₅,х₆,х₇ }являются блоками.

 

Рис. 10.23

 

Теорема. Граф G = (X,U) связен тогда и только тогда, когда его нельзя представить в виде объединения двух графов.

Орграф G₁ называется сильно связным графом или сильным, если для любых различных двух вершин х_i и х_к существует по крайней мере один путь, соединяющий эти вершины, т.е. любые две вершины взаимно достижимые (рис. 10.24).

Орграф G₂ называется односторонне связным или односторонним, если для двух вершин х_i и х_к существует путь либо из х_i в х_к либо из х_к в х_i (рис. 10.25).

Рис. 10.24

Рис. 10.25

Орграф G₃ называется слабосвязным или слабым, если для двух любых вершин графа существует по крайней мере один маршрут (рис. 10.26).

Орграф G₄ называется несвязным, если для некоторой пары вершин его не существует маршрута, соединяющего их (рис. 10.27).

Рис. 10.26

Рис. 10.27

Длиной маршрута называется количество ребер в нем (с повторения­ми). Обозначается ׀ М ׀ = К.

Расстоянием между вершинами х_i и х_к называется длина кратчайшей цепи, а сама кратчайшая цепь называется геодезической. Обозначается расстояние l (x_i, x_k).

Диаметром графа G (обозначается D(G)) называется длина наиболь­шей геодезической.

Эксцентриситетом е(х_i) вершины х_i в связном графе G(X,U) называ­ется максимальное расстояние от вершины до других вершин графа G.

Радиусом R(G) графа G называется наименьший из эксцентриситетов вершин.

Вершина x_i называется центральной, если ее эксцентриситет совпа­дает с радиусом графа, т.е. е(х_i) = R(G).

Рис. 10.28.

На рис. 10.28 указаны эксцентриситеты вершин и центры двух графов G₁ и G₂.

Вершины, составляющие центры, выделены.

Циклы Эйлера и Гамельтона

Задача Эйлера (о кенигсбергских мостах) заключается в нахождении маршрута путем обхода семи мостов по одному разу, который начинает­ся и оканчивается в одной части города, рис. 10.29.

При решении задачи (рис. 10.29, а) Эйлер составил граф G (рис. 10.29, б) и доказал, что поставленная задача решений не имеет. Указанный замк­нутый маршрут, называемый циклом, существует в графах с четными степенями вершин.

Рис. 10.29

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

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

Рис. 10.30

Теорема Эйлера. Если граф G = (X,U) связан и нетривиален, то сле­дующие утверждения эквивалентны:

1. G = (X,U) — эйлеров граф.

2. Каждая вершина имеет четную степень.

3. Множество ребер можно разбить на простые цепи.

Название гамельтоновых циклов произошло от задачи о кругосвет­ном путешествии, сформированной У. Гамельтоном: Необходимо обойти все вершины графа, диаграмма которого представляла укладку додека­эдра (рис. 10.31), по одному разу и вернуться в исходную точку. В началь­ной постановке задачи вершинами графа были столицы государств.

Рис. 10.31

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

Гамельтонов цикл не обязательно содержит все ребра графа, но сам граф может быть только связным.

Теорема. Если в графе G = (Х,U) с п вершинами степень каждой вер­шины не меньше чем,то граф является гамельтоновым.

Задача коммивояжера заключается в отыскании кратчайшего гамельтонова цикла в нагруженном полном графе. Имеется п городов, расстоя­ние между которым известны, коммивояжер должен посетить все n го­родов по одному разу, вернувшись в исходный город. Требуется найти такой маршрут движения, при котором суммарное пройденное расстоя­ние будет минимальным.

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

Эйлером получено просто проверяемое необходимое и достаточное условие существования в графиках эйлерова цикла.

Для гамельтоновых графов таких условий нет, поэтому алгоритма построения таких циклов нет.

 

12	Поделиться:

Воспользуйтесь поиском по сайту: