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

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

Аналогично определяются вершинное упорядочение (vertex-ranking) и [math]\displaystyle{ c }[/math]-вершинное упорядочение.

Литература

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