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

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


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

Навигация