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

1. Объединение графов. Граф G=(S,U) называется объединением графов G₁=(S₁,U₁) и G₂=(S₂,U₂), если и . Объединение называется дизъюнктным, если .

2. Произведение графов. Граф G=(S,U) называется произведением G₁xG₂ графов G₁=(S₁,U₁) и G₂=(S₂,U₂), если S=S₁xS₂ – декартово произведение множеств вершин исходных графов, а множество ребер получается следующим образом: вершины (x₁,x₂) и (y_1,y₂) смежны в графе G тогда и только тогда, когда или x₁= y₁ а x₂ и y₂ смежны в G₂, x₂ = y₂ а x₁ и y₁ смежны в G₁.

G

G₁

G₂



x₁

(x_1,y₂)

(x_1,y₃)

y₁

y₂

y₃

(x_1,y₁)

x₂

(x_2,y₁)

(x_2,y₂)

(x_2,y₃)

x₃

(x_3,y₁)

(x_2,y₂)

(x_2,y₃)

Р ис. 6

3. Слияние (отождествление) вершин.

Пусть x₁ и x₂ – две произвольные вершины графа G, а

G₁= G\{ x₁}\{ x₂}.

Рис. 7

К графу G₁ присоединим новую вершину y₁ , соединим её ребрами с каждой из вершин, входящих в объединение окружений верши x₁ и x₂ в графе G. Построенный граф G₂ получен из G отождествлением вершин x₁ и x₂.

Операция стягивания ребра означает отождествление двух смежных вершин. Граф G называется стягиваемым к графу G₁ если G₁ получается из G в результате некоторой последовательности стягиваний рёбер.

4

X₂

. Расщепление вершин. Пусть x₁ одна из вершин графа G. Разобьем её окружение на две части N₁ и N₂; удалим вершину x₁ вместе с инцидентными ей рёбрами; добавим новые вершины и соединяющее x₂ и x₃ их ребро (x₂ и x₃); вершину соединим с каждой вершиной из множества N₁, а вершину x₃ с каждой вершиной из множества N₂. в результате получим граф . Он получен из графа G путем расщепления вершины x₁.

G^~

Рис. 9

1.3. Маршруты, цепи, циклы

Чередующаяся последовательность x₁, u₁, x₂, u₂,…, x_k, u_k, x_k+1 , такая, что u_i=x_ix_i+1, i=1,k, называется маршрутом, соединяющим вершины x₁ и x_k+1.

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

Маршрут называется циклическим, если x₁=x_k+1. циклическая цепь называется циклом, а циклическая простая цепь – простым циклом. Число рёбер в маршруте называется длиной маршрута. Гамильтоновым циклом называется простой цикл, содержащий все вершины графа. Длина всякого цикла не менее трёх в графе без петель и кратных рёбер. Минимальная из длин циклов называется его обхватом.

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

Путь – это неориентированный маршрут.

О рграф называется сильно связным, если для любых двух вершин x_i, x_j S найдется путь с началом в x_i и концом в x_j. Для неориентированного графа понятия пути и маршрута совпадают.

Рис. 10

Теорема. Для любого графа G либо он сам, либо его дополнение является связным.

Разложение графа на связные компоненты

Рассмотрим разложение множества S вершин графа G=(S,U) на парно непересекающиеся подмножества, т.е. S= S_i, причем такое, что все вершины в каждом S_i связаны , а вершины из различных S_i несвязны тогда можно разложить граф G на пересекающиеся связные подграфы G(S_i,U_i), т.е.

. Такое разложение называется прямым, а сами подграфы – компонентами связности графа G.

Теорема 1. Любой граф представляется в виде обьединения непересекающихся связных компонент. Разложение графа на связные компоненты определяются однозначно.

П

X₂

X₃

X₆

X₃

X₂

ример. Разложение орграфа на три сильно связные компоненты.

X₁

X₆

X₅

X₅

X₄

X₄

G₂

G₃

G

Рис. 11

Теорема 2. Пусть G=(S,U) является n-вершинным неориентированным графом с к компонентами связности. Тогда число m(G) ребер в таком графе удовлетворяет условию

(1)

причём обе эти оценки достижимы.

П ример.

Рис. 12

N=7, k=2, m(G)=6;

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

Пусть G=(S,U) – орграф. Если каждой дуге принадлежит U поставлено в соответствие некоторое число W(x_i,x_j), то граф G называется графом со взвешенными дугами или сетью. При этом вершины графа называются узлами сети. Число W() называется весом дуги (x_i,x_j). Весом пути µ сети G_ называется число

(2)

Понятия сети и веса маршрута для неориентированного графа определяется аналогично.

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

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

Если , то граф G называют n-связным.

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

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

Пусть G – связный граф, а u, v – две различные его вершины. Множество рёбер Е графа называется u, v–разделяющим множеством в G, если любая простая цепь из u в v содержит ребро из Е. Множество вершинV графа, не содержащее u, v, называется u, v–отделяющим множеством в G, если любая простая цепь из u в v проходит через вершину из V.

Теорема Менгера. Для любых двух множеств вершин , наибольшее число непересекающихся цепей, соединяющих и , равно наименьшему числу вершин, отделяющих и .

Множество вершин называется внутренне устойчивым, если эти вершины попарно не смежны.

Внутренне устойчивое множество вершин называется пустым подграфом, если при добавлении хотя бы одной вершины, не принадлежащей этому множеству, образуется хотя бы одно ребро (дуга).

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

Максимальное число попарно несмежных рёбер графа G называется рёберным числом независимости графа .

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

Множество вершин, покрывающих все рёбра графа G, называется вершинным покрытием графа.

Минимальная мощность вершинного покрытия называется числом вершинного покрытия графа .

Аналогично, множество рёбер, покрывающих все вершины графа G, называется рёберным покрытием графа.

Минимальная мощность рёберного покрытия называется числом рёберного покрытия графа .

Теорема. Для любого нетривиального связного графа G = = (V,U)

. (3)

Множество рёбер графа, в котором никакая пара рёбер не смежна, называется паросочетанием графа.

Множество рёбер паросочетания, в котором число рёбер равно , называется наибольшим паросочетанием графа.

Совершенным паросочетанием из V₁ в V₂ в двудольном графе G(V₁,V₂) называется взаимно однозначное соответствие между вершинами из V₁ и подмножеством вершин из V₂, при котором каждая вершина из V₁ соединена ребром с некоторой вершиной из V₂.

Теорема Холла. Пусть G(V₁,V₂) – двудольный граф и для любого подмножества пусть также - множество тех вершин из V₂, которые смежны, по крайней мере, с одной вершиной из А. Тогда совершенное паросочетание из V₁ в V₂ существует тогда и только тогда, когда число элементов для каждого подмножества .