Реберное упорядочение графа: различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером '''Реберное упорядочение графа''' (''Edge-ranking of a graph'') - разметка ребер натуральн...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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] | ||
Версия от 12:15, 25 января 2010
Реберное упорядочение графа (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]-вершинное упорядочение.
Литература
[WG'96]