Операции на графах

Операция удаления ребра ,()- частичный граф графа.
Операция удаления вершины ,(- подграф графа, у которого удалена вершина)
Операция объединения графов () Результат зависит от того, выполняется ли условие
Операция сложения графов (,- полный двудольный граф, построенный на элементахи элементах, которые не являются общими для этих двух графов.)
Операция дополнения графа (до полного) ,(,) Граф, изоморфный своему дополнению называется самодополнительным.
Операция произведения графов ()

Пример

Сколько ребер имеет граф ?

Связность в графах Понятие цепи

Пусть - некоторый граф. Последовательность попарно инцидентных между собой вершин и ребер графа называетсяцепью.

и -концевые вершиныцепи.

Длина цепи - число ребер, образующих цепь (и- концевые вершины цепи).

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

1) ; 2); 3).

Диаметром графаназывается величина.

Пример

(целая часть числа).

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

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

Примеры

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

ТеоремаДля любого графа.

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

Максимальный по включению вершин подграф графа, любые две вершины которого связны (имеется ввиду вершины подграфа) называется компонентой связности графа.- число компонент связности графа.

Теорема Любая вершина графа принадлежит ровно одной компоненте связности.

Число компонент связности графа является инвариантом. Если , то граф связен. Инварианты и являются зависимыми друг от друга.

Теорема

СледствиеЕсли, то граф связен ().

Нахождение компонент связности

Шаг 0:поместить в список.Итерационный шаг: 1. Найти в списке первую непросмотренную вершину (). 2. Вычислить и добавить в список те вершины из окрестности, которых нет в списке. 3. Отметить как просмотренную.Заключительный шаг:Итерационный шаг выполняется до тех пор пока в списке есть непросмотренные вершины.

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

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

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

Пример

Максимальный по включению вершин подграф орграфа, любые две вершины которого сильно связны, называется компонентой сильной связностиорграфа (КСС).

Отношение сильной связности является отношением эквивалентности на множестве вершин. Таким образом разбиение орграфа на КСС – это разбиение множества вершин на классы эквивалентности.