4625
правок
Реберное упорядочение графа: различия между версиями
Перейти к навигации
Перейти к поиску
Реберное упорядочение графа (посмотреть исходный код)
Версия от 12:15, 25 января 2010
, 25 января 2010нет описания правки
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] | ||