Суммарная величина вершинного разделения и профиль графов

Рассматриваются два инварианта графов, определяемые через оптимальные (по различным критериям) нумерации вершин. Это суммарная величина вершинного разделения и профиль графов. Доказывается, что эти два инварианта равны. Приводится ряд свойств профиля графов, полученных с помощью равенства этих инвариантов.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проект 96-02-00285.