Реберное упорядочение графа

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

Реберное упорядочение графа (Edge-ranking of a graph) — разметка ребер натуральными числами такая, что каждая цепь между двумя ребрами с одной и той же меткой i содержит ребро с меткой j >
i. Ясно, что разметка ребер есть реберное упорядочение тогда и только тогда, когда для любого i удаление всех ребер с меткой > i порождает компоненты связности, каждая из которых имеет самое большее одно ребро с меткой i. Проблема реберного упорядочения состоит в нахождении реберного упорядочения с наименьшим числом меток. Обобщением данного понятия служит c-реберное упорядочение, при котором образующиеся при удалении ребер с меткой > i, содержат самое большее c ребер с меткой i.

Аналогично определяются вершинное упорядочение (vertex-ranking) и c-вершинное упорядочение.

Литература

  • Workshop. Cadenabbia, 1996 // Lect. Notes Comp. Sci., 1997, vol. 1197.