ФУНДАМЕНТАЛЬНАЯ И ПРИКЛАДНАЯ МАТЕМАТИКА
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 г.