Реберное упорядочение графа: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
Строка 1: Строка 1:
'''Реберное упорядочение графа''' (''[[Edge-ranking of a graph]]'') -
'''Реберное упорядочение графа''' (''[[Edge-ranking of a graph]]'')
[[разметка дуг|разметка ребер]] натуральными числами такая, что каждая [[цепь]] между
[[разметка дуг|разметка ребер]] натуральными числами такая, что каждая [[цепь]] между
двумя [[ребро|ребрами]] с одной и той же [[метка|меткой]] <math>i</math> содержит ребро с меткой <math>j >
двумя [[ребро|ребрами]] с одной и той же [[метка|меткой]] <math>i</math> содержит ребро с меткой <math>j >
Строка 14: Строка 14:
[[c-Вершинное упорядочение|<math>c</math>-вершинное упорядочение]].
[[c-Вершинное упорядочение|<math>c</math>-вершинное упорядочение]].
==Литература==
==Литература==
[WG'96]
* Workshop. Cadenabbia, 1996 // Lect. Notes Comp. Sci., 1997, vol. 1197.

Текущая версия от 13:56, 30 августа 2011

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