Лабораторная работа 9

Занятие 17. Тема «Элементарные задачи на графах. Задача о максимальном потоке»

Формы проведения и используемые методы: индивидуальная работа, консультация.

Вопросы для обсуждения:

1. Дана транспортная сеть с источником , стоком и пропускными способностями . Величиной потока (value of flow) называется сумма потоков из источника . Задача о максимальном потоке заключается в нахождении потока такого, что величина потока максимальна.

Список рекомендуемой литературы.

1. Компьютерная математика: теория и практика / Дьяконов В. - М.: Нолидж, 2001. - 1296 с.: илл.

2. Компьютерная математика/ Самсонов Б., Плохов Е., Филоненков А. - Ростов-на-Дону: Феникс, 2002. - 512 с.

3. Компьютерная математика /Д.Кук, Г.Бейз М.: Наука. Гл. ред. физ.-мат. лит., 1990, 384 стр.

4. Основы теории графов/ Зыков А.А. - М.: Вузовская книга, 2004. - 664 с.

Занятие 18. Тема «Элементарные задачи на графах. Задача об упаковках и покрытиях.»

Формы проведения и используемые методы: индивидуальная работа, консультация.

Вопросы для обсуждения:

1. Отыскать (по произвольно заданной тройке (V, Е, Г)) покрытия и упаковки, доставляющие экстремум указанных функционалов.

Список рекомендуемой литературы.

1. Компьютерная математика: теория и практика / Дьяконов В. - М.: Нолидж, 2001. - 1296 с.: илл.

2. Компьютерная математика/ Самсонов Б., Плохов Е., Филоненков А. - Ростов-на-Дону: Феникс, 2002. - 512 с.

3. Компьютерная математика /Д.Кук, Г.Бейз М.: Наука. Гл. ред. физ.-мат. лит., 1990, 384 стр.

4. Основы теории графов/ Зыков А.А. - М.: Вузовская книга, 2004. - 664 с.