Самостоятельная работа №1 План: Аксиоматические теории множеств. Нечеткие множества

Ответ на второй вопрос: – Как получить плоское изображение графа? – дает алгоритм, рассмотренный ниже.
Пусть задана часть G₁ = (V₁, E₁) графа G = (V, E).
Будем называть куском графа G относительно G₁:

1. 
   ребро  вместе с его концами, которые принадлежат V₁,
   
2. 
   а также компоненту связности G’_i = (V’_i, E’_i) подграфа, порожденного подмножеством вершин V\V_l, дополненную всеми ребрами, инцидентными вершинам из V'_i, и всеми вершинами этих ребер, принадлежащими V₁ , которые называются «контактными точками»;
   

Алгоритм использует последовательный процесс присоединения к некоторому плоскому подграфу  цепи  , оба конца которой (и только они) – вершины  . Эта цепь разобьет одну из граней  на две.
В качестве начального плоского графа  выбирают некоторый цикл графа G.
Чтобы перейти от подграфа  к  , предварительно рассматривают все куски P_j графа G относительно  .
Грань f_k графа  и кусок Р_j совместимы, если все его контактные точки принадлежат множеству вершин этой грани.
Для каждого куска определяем грани, которые с ним совместимы. Возможны три случая:

1. 
   Некоторый кусок не совместим ни с какой гранью графа  . Тогда граф не плоский.
   
2. 
   Какой–либо кусок совместим с единственной гранью f_k графа  . Тогда выберем в этом куске цепь  такую, что оба ее конца (и только они) принадлежат  . Дополняя   ребрами и вершинами этой цепи, получаем  , проводя  внутри грани f_k.
   
3. 
   Если каждый из кусков Р_j совместим, по крайней мере, с двумя гранями графа  , то можно выбрать цепь  в любом из кусков и действовать как в случае 2.
   

Пример. Проиллюстрируем этот алгоритм на примере графа G(V,E) рис. 23.3.
Р  исунок 23.3
Шаг 1. Берем произвольный цикл, например u₀ = (1, 2, 6, 5, 1), представляющий плоский граф  (рис. 23.4, а).
Грани :
A₀ — внешняя грань (1, 2, 6, 5, 1),
В₀ — внутренняя грань (1,2,6,5,1).