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

Рассмотрим операции над графами.

I. Бинарные операции.

1. Объединение графов. Рассмотрим графы и . Объединение графов и , обозначаемое как , представляет собой такой граф , что множество его вершин является объединением и , а множество ребер – объединением и .

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

3. Кольцевой суммой графов G₁ и G₂ называется граф , где .

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

Пример. Для графов найдем G₁ =({ x ₁, x ₂, x ₃}, {(x ₁, x ₂), (x ₂, x ₃)}) и G₂ =({ x ₁, x ₂, x ₄}, {(x ₁, x ₂), (x ₄, x ₁)}) (рис. 4.17) найдем , , . По определению имеем

=({ x ₁, x ₂, x ₃, x ₄},{(x ₁, x ₂), (x ₂, x ₃),(x ₄, x ₁)}),

=({ x ₁, x ₂}, {(x ₁, x ₂)}),

=({ x ₁, x ₂, x ₃, x ₄}, {(x ₂, x ₃), (x ₄, x ₁)}).

4. Соединением графов G₁ + G₂ называется граф {(x_i, x_j) | x_i Î X ₁, x_j Î X ₂, x_i ¹ x_j }).

Пример. Для графов G₁ и G₂, показанных на рис. 4.18 а, соединением G₁+G₂ является граф, представленным на рис. 4.18 б.

5. Произведением графов G ₁ и G ₂ называется граф , в котором ((x ₁, y ₁), (x ₂, y ₂))Î V тогда и только тогда, когда x ₁= x ₂ и (y ₁, y ₂)Î V ₂, или y ₁= y ₂ и (x ₁, x ₂)Î V _1.

Пример. На рис. 4.19 изображено произведение графов G ₁=({1, 2}, {(1, 1), (2, 1)}) и G ₂ = ({ a, b, c },{(a, b), (b, a), (b, c)}).

II. Унарные операции.

1. Удаление вершины. При удалении вершины из графа удаляются и все инцидентные ей ребра (дуги).Пусть – граф и . Удалить вершину x из графа G – это значит построить новый граф , в котором и получается из V удалением всех ребер, инцидентных вершине x. Вот иллюстрация удаления вершины x из графа:

До удаления вершины x После удаления вершины x

2. Удаление ребра (дуги). Пусть – граф и . Удалить ребро (дугу) v – это значит построить новый граф , в котором и . Вот иллюстрация удаления ребра графа:

До удаления ребра v. Послеудаления ребра v

При удалении ребра (дуги) его концевые вершины не удаляются. Операцией, являющейся обратной к удалению ребра, является добавление ребра.

3. Слияние или отождествление вершин. Говорят, что вершины и в графе G отождествляются (сливаются), если они заменяются такой новой вершиной , что все ребра (дуги) графа, инцидентные и , становятся инцидентными новой вершине .

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

Пример. Из графа G, показанного на рис. 4.20, добавлением вершины 5 образуется граф G₁, добавлением дуги (3,1) – граф G₂, удалением дуги (3,2) – граф G₃, удалением вершины 2 – граф G₄, отождествлением вершин 1 и 4 – граф G₅, стягиванием дуги (2,3) – граф G₆.

5. Подразбиение ребра. Пусть – граф и . Выполнить подразбиение ребра v – это значит построить новый граф , в котором (т.е. z – некая новая вершина) и . С графической точки зрения эта операция означает «внесение в ребро новой вершины». Вот графическая иллюстрация:

xx

z

yy

До внесения вершины z После внесения вершины z

Граф называется дополнением простого графа, если ребро (x_i, x_j) входит в в том и только в том случае, если она не входит в V. Другими словами, две вершины смежны в тогда и только тогда, когда они не смежны в G.

Пусть G’ =(X’, V’) является подграфом графа G =(X, V). Подграф G’’ =(X, V \ V’) графа G называется дополнением графа G’ в графе G.

Дата добавления: 2014-12-27