Просмотр кода страницы Реберное упорядочение графа

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

Аналогично определяются вершинное упорядочение (vertex-ranking) и
<math>c</math>-вершинное упорядочение.
==Литература==
[WG'96]