Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 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) – пропускная способность дуги.

1. Критический путь – (s, t)–путь в ациклическом орграфе наибольшей величины.

2. Поток в сети называется полным, если любой s–t путь содержит, по крайней мере, одну насыщенную дугу.

3. Наибольшее паросочетание – паросочетание с наибольшей величиной.

4. Кратчайшая цепь – (s, t)–цепь с наименьшей величиной.

5. Расстояние между вершинами s и t – величина кратчайшей (s, t)–цепи. Если s и t несоединимы, то расстояние между этими вершинами равно .

6. Вес цикла – величина цикла.

7. Отрицательный цикл – цикл, который имеет отрицательную величину.

8. Длина маршрута (цепи, пути) – величина маршрута.

9. Дерево кратчайших цепей – корневое остовное дерево, в котором расстояния от корня до всех остальных вершин равны соответствующим расстояниям в исходном графе.

10. Наибольший разрез (максимальный) – разрез с наибольшей возможной величиной.

11. Наименьший разрез (минимальный) – разрез с минимально возможной величиной.

12. Минимальное (наименьшее, кратчайшее) остовное дерево – остовное дерево с минимально возможной величиной.

Учебное издание

Федоров Валентин николаевич

ВВЕДЕНИЕ В ТЕОРИЮ ГРАФОВ

Учебное пособие

(Конспект лекций)

–––––––––––––––––––––––––––––––––––––––––––––––––––––––

Подписано в печать

Формат 60x84 1/16

Объем 7,5 п.л. Тираж 200 экз. Заказ

–––––––––––––––––––––––––––––––––––––––––––––––––––––––

ГОУ ВПО “Московская государственная академия

приборостроения и информатики”

107996, Москва, ул. Стромынка, 20

120

Характеристики

Список файлов книги