FPM 2002, ТОМ 8, ВЫПУСК 4, СТР. 1193-1214

ФУНДАМЕНТАЛЬНАЯ И ПРИКЛАДНАЯ МАТЕМАТИКА
2002, ТОМ 8, ВЫПУСК 4, СТР. 1193-1214

Сепараторы в планарных графах как новый способ их характеризации

С. А. Тищенко

Аннотация

Посмотреть как HTML Посмотреть как рисунок Посмотреть в формате LaTeX



Мы рассматриваем планарные графы с неотрицательно взвешенными
вершинами, рёбрами и гранями. Мы также полагаем, что все вершины
и рёбра имеют неотрицательную стоимость. В случае равных
весов для треугольных графов доказана эквивалентность и продемонстрирована
оптимальность полученных результатов. Рассмотрение неотрицательно
взвешенных граней при заданной плоской укладке графа позволяет
формировать сепараторы на двойственных графах. На нескольких классических
примерах --- графы $K_n$, $K_{mn}$, графы диаметра $2$ ---
продемонстрирована высокая эффективность использования сепараторов
для характеризации планарных графов.

Полнотекстовая версия статьи в формате PostScript (193 Kb)

URL страницы: http://mech.math.msu.su/~fpm/rus/k02/k024/k02417t.htm.
Изменения вносились 10 апреля 2003 г.