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

Материал из WikiGrapp
Версия от 13:56, 30 августа 2011; KEV (обсуждение | вклад)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

Реберное упорядочение графа (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.