3.04.1. Связные графы и расстояние в графах. Маршруты в графах. Связные графы

Пусть G -- мульти - или псевдограф. Последовательность вершин и рёбер вида:

Такая, что - ребро в графе G, соединяющее Vi C Vi+1 Называется . Вершина V1 при этом называется началом маршрута, а Vn+1 – концом маршрута. Число рёбер N в маршруте называется Длиной маршрута. Во взвешенном графе за длину маршрута принимается сумма весов входящих в маршрут рёбер.

В простом графе, когда смежные вершины соединены только одним ребром, для задания маршрута достаточно указать только последовательность вершин ( разумеется, любые две соседние вершины в этой последовательности должны быть смежными). В этом случае (V1, V N+1) – маршрут обозначается: (V1, V2, V3, …, Vn+1).

В маршруте вершины и рёбра могут повторяться. Если в маршруте все рёбра различны, то он называется Цепью. Если кроме того в цепи различны и все вершины (кроме, может быть, первой и последней), то такой маршрут называется Простой цепью.

Маршрут называется циклическим, если в нём начало совпадает с концом. Циклический маршрут являющийся цепью называется Циклом, а являющийся простой цепью -- Простым циклом.

Минимальная из длин всех циклов графа называется Охватом графа.

Граф G называется Связным, если в нем для любых двух вершин U и υ существует (U,υ)-маршрут.

В ориентированных графах рассматриваются ориентированные маршруты, в которых для любой пары соседних вершин υi и υi+1 существует дуга (υi, υi+1) (υi – начало дуги, υi+1 – конец). Другими словами – это маршруты, по которым можно передвигаться от начала маршрута к концу с соблюдением ориентации (стрелок).

Орграф, в котором для любой пары вершин U и υ существуют ориентированные (U, υ)– и (υ, U)-маршруты , называется Сильно связным. Если же для любой пары вершин U и υ существует ориентированный (U, υ)– или (υ, U)-маршрут, то такой орграф называется Односторонне связным. Орграф в котором любую пару вершин можно соединить маршрутом без соблюдения ориентации (т. е. являющийся связным, если убрать на всех дугах стрелки) называется Слабо связным.

Легко видеть, что всякий (U, υ)–маршрут содержит (U, υ)–цепь. Для того, что бы её получить, достаточно в маршруте исключить дублирование участков, которые проходятся несколько раз. Кроме того, если из (U, υ)–цепи удалить все промежуточные циклические участки, то получим простую (U, υ)–цепь.

Таким образом, можно дать эквивалентное определение связности: граф называется связным, если в нём любую пару вершин U и υ можно соединить простой (U, υ)–цепью.

Для связных графов вводиться также количественная характеристика их связности. Связностью Графа G называется наименьшее число вершин, удаление которых приводит к несвязному или тривиальному графу. Так, например, полный граф KN имеет связность N-1; простая цепь Pn имеет связность 1; простой цикл СN имеет связность 2; колесо Wn имеет связность 3.

Наименьшее число рёбер графа G, удаление которых приводит к несвязному подграфу, называется Ребёрной связностью графа G.

Компоненты связности. Связность графа и его дополнения

Максимальные связные подграфы графа G называются его Компонентами связности. Здесь “максимальные” означает: не содержатся в других подграфах с большим числом элементов.

На множестве вершин V(G) определим бинарное отношение. Положим V~U, если в G Существует (V, U)–маршрут. Легко видеть, что это отношение является отношением эквивалентности, причем V~U тогда и только тогда, когда вершины V и U содержатся в одной и той же компоненте связности. Таким образом, совокупность компонент связности есть разбиение данного графа (объединение компонент дает весь граф; различные компоненты связности не пересекаются).

Граф называется Графом достижимости графа G (или Транзитивным замыканием графа G), если V() = V(G) и в графе вершины V и U соединены ребром тогда и только тогда, когда в G существует (U, υ)–маршрут. Другими словами, в графе V и U смежны, если V~U В графе G (в смысле отношения эквивалентности, введенного выше).

Понятно, что граф G связен в том и только том случае, когда =Kn – полный граф. В случае же, когда G не является связным, является объединением нескольких полных подграфов, которые являются его компонентами связности.

Теорема. Всякий граф или его дополнение является связным.

Доказательство. Предположим, что G – не связный граф, и докажем, что тогда его дополнение Есть связный граф. Действительно, пусть A – множество вершин какой-либо компоненты связности графа G, а B=V(G)\A – остальные вершины. Тогда в графе всякая вершина AÎA соединена ребром с каждой вершиной BÎB. Пусть Ai, Aj Î A, тогда (Ai, b, aj) – маршрут, соединяющий Ai с Aj (здесь B –любая вершина из B). Аналогично, если Bi, bj Î B, то (Bi, a, bj) – маршрут соединяющий Bi с Bj, (A – любая вершина из A). Таким образом, для любых двух вершин в Существует соединяющий их маршрут (длины не более 2), что и требовалось доказать.

< Предыдущая		Следующая >