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

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

1. Подграф получается из подграфа удалением вершины и всех инцидентных этой вершине ребер. Отметим, что если не входит в множество вершин графа , то .

2. Подграф получается из подграфа удалением ребра и всех инцидентных этой вершине ребер. Если не входит в множество ребер графа , то .

3. Подграф получается из подграфа добавлением ребра и двух его концевых вершин. Если входит в множество ребер графа , то .

4. Говорят, что граф получен из графа путем подразбиения ребра , если

,

, ,

, , где - концы ребра .

- граф, полученный из графа путем подразбиения ребра .

Пусть и - подграфы графа .

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

7. Объединением графов и называется граф .

Аналогично определяется пересечение и объединение любого конечного числа подграфов.

Определение. Пусть , ,…, - непустые подграфы графа и выполнены условия:

1. ;

2. .

Тогда семейство множеств называется дизъюнктным разбиением графа .

3.4. Маршруты, цепи и циклы в графе

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

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

Случай, когда длина маршрута равна нулю, не исключается; в этом случае маршрут сводится к одной вершине.

Если , то маршрут называется замкнутым.

Заметим, что в обыкновенном графе маршрут полностью определяется последовательностью своих вершин.

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

Определение. Цепь – это маршрут без повторяющихся ребер.

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

Определение. Цепь называется простой, если в ней нет повторяющихся вершин за исключением, быть может, совпадающих концевых.

Определение. Замкнутая цепь называется циклом.

Определение. Замкнутая простая цепь называется простым циклом.

Пример 1. - -маршрут; его длина равна 4; данный маршрут является -цепью; эта цепь незамкнутая, не простая. Маршрут - цикл длины 5, этот цикл не является простым; - простой цикл.

Лемма (о простой цепи). Если для некоторых вершин и на графе существует -маршрут, то существует и простая - цепь.

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

Лемма (об инвертировании маршрута). Если для некоторых вершин и на графе существует -маршрут, то существует и - маршрут.

Данное утверждение настолько очевидно, что вряд ли нуждается в доказательстве.