ФУНДАМЕНТАЛЬНАЯ И ПРИКЛАДНАЯ МАТЕМАТИКА
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/k02417h.htm.
Изменения вносились 10 апреля 2003 г.