Операции редуцирования

Вершина v в графе G называется проходной, если ее степень: r (v) = 2.

Пусть задан граф G = (V, E) .

Добавление проходной вершины. Добавление проходной вершины w производится по следующей схеме:

1) удаляется ребро e Î E, инцидентное вершинам u, w Î V;

2) добавляются ребра e' ={ u, w } и e'' = { w, v } .

В результате, получается граф: G' = (V', E'),

где V' = V È { w }, E' = E \{ e }È { e', e'' } .

Удаление проходной вершины. Удаление проходной вершины w производится по следующей схеме:

1) удаляется ребро e', инцидентное вершинам u, w Î V, и ребро e'', инцидентное вершинам w, v Î V;

1) добавляется ребро e, инцидентное вершинам u, v I V.

В результате, получается граф: G' = (V', E'),

где V' = V \{ w }, E' = E \{ e', e'' }E { e } .

Стягивание ребра. Стягивание ребра e инцидентного вершинам u, v в графе
G = (V, E) производится по следующей схеме:

1) удаляется ребро e, инцидентное вершинам u, v I V;

2) склеиваются вершины u, v, образуя вершину uv I V.

В результате, получается граф G' = (V', E'), где V' = V \{ u, v } E { uv }, E'= E\ { e } (рис. 2.25).

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

Рис. 2.25. Операция стягивания ребра

Критерий планарности Понтрягина-Куратовского

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

Если графы гомеоморфные, то они планарные или не планарные одновременно.

Теорема 2.14. (Понтрягина-Куратовского). Граф G планарный тогда и только тогда, когда он не содержит подграфов, гомеоморфных графам K₅ или K_3,3.

(Без доказательства).

Дата добавления: 2015-07-20