Операции над графами. Критерий планарности графов

Определение 6.1. Дополнением G’ графа G =( V, U ) (обозначение ) называется такой граф G’ =( V’, U’ ) у которого множество вершин V‘ совпадает с множеством вершин V исходного графа G, а вершины v_i и v_j графа G’ соединены ребром (смежные) тогда и только тогда, когда они не являются смежными в графе G.

Пример 6.1.

v₁v₂v₁v₂

Если G:, то :

v₃v₄v₃v₄

Определение 6.2. Удаление вершины v из графа G =( V, U ) (обозначение G – v ) приводит к графу G’ =( V’, U’ ) в котором V’ = V \{ v }, а U’= U \{ { v_i, v_j }|(v_i = v)˅(v_j = v)}. Иными словами из графа G удаляется вершина вместе со всеми ребрами графа, которым она была инцидентна.

Пример 6.2.

v₁v₂v₅v₁v₅

Если G:, то G – v₂:

v₃v₄v₃v₄

Определение 6.3. Удаление ребра e = { v_i, v_j } из графа G =( V, U ) (обозначение G – e ) приводит к графу G’ =( V’, U’ ) в котором V’ = V, а U’= U \{ { v_i, v_j }}. Иными словами из графа G удаляется ребро с сохранением всех существовавших в графе G вершин.

Пример 6.3.

v₁v₂v₅v₁v₂v₅

Если G:, то G – { v₂, v₄ } :

v₃v₄v₃v₄

Определение 6.4. Стягивание графа G =( V, U ) по его подграфу H = ( V_H, U_H ) (обозначение G \ H ) приводит к графу G’ =( V’, U’ ) в котором V’ = ( V \ V_H )∪{ v }

(здесь v ∉ V ), а U’= U \{ { v_i, v_j }|( v_i ∊ V_H )˅( v_j ∊ V_H )}∪{e = { z, v }| z ∊ ( O ( V_H )\ V_H )}

(здесь O ( V_H ) = ∪ O ( v_i ), а окружения вершин O ( v_i ) рассматриваются для всех v_i ∊V_H ). Иными словами, из графа G удаляются все вершины подграфа H = ( V_H, U_H ) и добавляется новая вершина v. Из исходного графа удаляются также все ребра, инцидентные удаленным вершинам подграфа H, но те ребра исходного графа, которые были инцидентны вершинам объединенного окружения вершин подграфа H (без учета вершин этого подграфа) восстанавливаются, как ребра, инцидентные добавленной вершине v.

Пример 6.4. Пусть нам задан граф

v₁ v₂ v₃ v₄ v₅

G:

v₆ v₇ v₈ v₉ v₁₀

Выберем в нем какой-либо подграф H, например,

v₁ v₂

Н:

v₆ v₇

Тогда граф

v₃ v₄ v₅

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