Унитарный граф: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Создана новая страница размером '''Унитарный граф''' (''Unitary graph'') - Пусть в некотором графе, рассматриваемом ка...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 1: | Строка 1: | ||
'''Унитарный граф''' (''Unitary graph'') | '''Унитарный граф''' (''[[Unitary graph]]'') — Пусть в некотором [[граф|графе]], рассматриваемом как ''[[транспортная сеть]]'', найден ''[[поток]]'' <math>f</math>; тогда '''унитарный граф''' получается заменой каждой [[дуга|дуги]] <math>u</math> с потоком <math>f(u)</math> <math>f(u)</math> дугами с единичным потоком. Очевидно, '''унитарный граф''' | ||
Пусть в некотором графе, рассматриваемом как ''транспортная сеть'', | есть ''[[мультиграф]]''. | ||
найден ''поток'' <math>f</math>; тогда ''' | |||
с потоком <math>f(u)</math> <math>f(u)</math> дугами с единичным потоком. Очевидно, ''' | |||
есть ''мультиграф''. | |||
==Литература== | ==Литература== | ||
* Кристофидес Н. Теория графов. Алгоритмический подход. — М.: Мир, 1978. | |||
Текущая версия от 11:21, 22 сентября 2011
Унитарный граф (Unitary graph) — Пусть в некотором графе, рассматриваемом как транспортная сеть, найден поток [math]\displaystyle{ f }[/math]; тогда унитарный граф получается заменой каждой дуги [math]\displaystyle{ u }[/math] с потоком [math]\displaystyle{ f(u) }[/math] [math]\displaystyle{ f(u) }[/math] дугами с единичным потоком. Очевидно, унитарный граф есть мультиграф.
Литература
- Кристофидес Н. Теория графов. Алгоритмический подход. — М.: Мир, 1978.