Каноническое упорядочение

Материал из GraphLabs Wiki
Перейти к: навигация, поиск

Для любого цикла в графе назовём хордой ребро, соединяющее любые две не следующие друг за другом вершины. Для 2-связного графа мы обозначим за ) его внешний цикл, т.е. границу его внешней грани. Вершины, принадлежащие назовём внешними вершинами, рёбра – внешними рёбрами. Планарный граф назовём внутренне-триангулированным, если любая его внутренняя грань – треугольник. Пусть – триангулированный планарный граф на вершинах, как показано на рис. 1. Т.к. граф триангулированный, то его внешний цикл содержит ровно три вершины. Положим, что эти три вершины (обозначим их ) образуют цикл в указанном порядке против часовой стрелки. Пусть – упорядочение вершин графа . Для любого целого числа , мы обозначим за планарный подграф графа , образованный вершинами . Тогда .

Рис. 1. Каноническое упорядочение для триангулированного планарного графа на n=16 вершинах

Будем называть каноническим упорядочением графа , если для любого целого , выполнены условия:

  1. – двусвязный и внутренне-триангулированный граф;
  2. – внешнее ребро ;
  3. Если , то вершина принадлежит внешней грани , и все вершины, соседние с , последовательно входят в ).

Алгоритм нахождения канонического упорядочения

Для каждой вершины введём следующие переменные:

  • , если уже входит в упорядочение, иначе false, для любых ;
  • , если вершина является внешней для текущего планарного графа, иначе false;
  • – число хорд внешнего цикла, одним из концов которых является вершина .
  1. Пусть – произвольный цикл на трёх вершинах в графе .
  2. Установим для всех вершин .
  3. Присвоим и .
  4. Присвоим .
  5. for k=n down to 3 do
    BEGIN
  6. Выберем любую вершину такую, что и .
  7. Установим и .
  8. Пусть , где и .
  9. Пусть – смежные с вершины, для которых
  10. Для каждой вершины присвоим ; обновим переменную для и соседних с ней вершин следующим образом: если , то мы уменьшаем на единицу и , т.к. ребро , входящее в текущий внешний цикл , было хордой в предыдущем внешнем цикле . Если же , то мы изменяем значение для каждой вершины а также для каждой вершины , смежной с : если и , то – это хорда , и, следовательно, надо увеличить значение на 1; если и и , то мы увеличиваем на 1.
END

(На рис. 2 новые хорды, принадлежащие , изображены толстыми сплошными линиями, а хорды – толстыми точечными).

Рис. 2. G_k