Федоров В.Н. - Введение в теорию графов, страница 16
Описание файла
Документ из архива "Федоров В.Н. - Введение в теорию графов", который расположен в категории "". Всё это находится в предмете "дискретная математика" из 4 семестр, которые можно найти в файловом архиве РТУ МИРЭА. Не смотря на прямую связь этого архива с РТУ МИРЭА, его также можно найти и в других разделах. Архив можно найти в разделе "книги и методические указания", в предмете "дискретная математика" в общих файлах.
Онлайн просмотр документа "Федоров В.Н. - Введение в теорию графов"
Текст 16 страницы из документа "Федоров В.Н. - Введение в теорию графов"
2. f(i, j) c(i, j) для любой дуги (i, j) в сети.
3. суммы берутся по всем j для всех ,
где i и j – вершины сети, s – исток, t – сток сети, (i, j) – дуга из вершины i в вершину j, (j,i) – дуга из вершины j в вершину i, c(i, j) – пропускная способность дуги.
-
Критический путь – (s, t)–путь в ациклическом орграфе наибольшей величины.
-
Поток в сети называется полным, если любой s–t путь содержит, по крайней мере, одну насыщенную дугу.
-
Наибольшее паросочетание – паросочетание с наибольшей величиной.
-
Кратчайшая цепь – (s, t)–цепь с наименьшей величиной.
-
Расстояние между вершинами s и t – величина кратчайшей (s, t)–цепи. Если s и t несоединимы, то расстояние между этими вершинами равно .
-
Вес цикла – величина цикла.
-
Отрицательный цикл – цикл, который имеет отрицательную величину.
-
Длина маршрута (цепи, пути) – величина маршрута.
-
Дерево кратчайших цепей – корневое остовное дерево, в котором расстояния от корня до всех остальных вершин равны соответствующим расстояниям в исходном графе.
-
Наибольший разрез (максимальный) – разрез с наибольшей возможной величиной.
-
Наименьший разрез (минимальный) – разрез с минимально возможной величиной.
-
Минимальное (наименьшее, кратчайшее) остовное дерево – остовное дерево с минимально возможной величиной.
Учебное издание
Федоров Валентин николаевич
ВВЕДЕНИЕ В ТЕОРИЮ ГРАФОВ
Учебное пособие
(Конспект лекций)
–––––––––––––––––––––––––––––––––––––––––––––––––––––––
Подписано в печать
Формат 60x84 1/16
Объем 7,5 п.л. Тираж 200 экз. Заказ
–––––––––––––––––––––––––––––––––––––––––––––––––––––––
ГОУ ВПО “Московская государственная академия
приборостроения и информатики”
107996, Москва, ул. Стромынка, 20
120