Дискр. мат._2 Графы
.doc
Метка
— наименьшая из временных меток, делаем
ее постоянной.
— постоянная метка.
3
шаг.
Наименьшие
из временных меток имеют вершины
и
.
Выбираем, например,
.
— постоянная метка.
4
шаг.
.
Метки
не изменились, наименьшей из временных
осталась метка 3, принадлежащая вершине
.
— постоянная метка.
5
шаг.
.
— постоянная метка.
6
шаг.
.
— постоянная метка.
7
шаг.
— постоянная метка.
8
шаг.
— постоянная метка.
9
шаг.
.
— постоянная метка.
10
шаг. Последняя вершина
получает последнюю постоянную метку
— постоянная метка.
Путь строится так же как и раньше, т.е.
или
Рассмотренные вопросы можно изучить по указанной литературе, точнее: [1, гл. 2, § 1, 2], [3, гл. 7, § 7.1—7.5, § 7.7], [4, гл. 4, § 1 — 9], [5, гл. 6, § 6.1—6.2], [6, гл. 4, § 4.1—4.4], [7, разд. 3], [8, гл. 4, § 4.1—4.2], [9, гл. 7 —10], [11, гл. 4, § 4.1—4.8].
Библиографический список
1.Белов В.В., Воробьёв Е.М., Шаталов В.Е. — Теория графов. М.: Высшая школа, 1976, 392 с.
2. Горбатов В.А. Фундаментальные основы дискретной математики. — М.: Наука. Физматлит, 1999. 544 с.
3. Ерусалимский Я.М. Дискретная математика. — М.: Вузовская книга, 2002. 268 с.
4. Зарецкая М.А., Файнштейн А.С. Введение в дискретную математику. — Магнитогорск: МГТУ, 1999. 167 с.
5. Иванов Б.Н. Дискретная математика. Алгоритмы и программы. — М.: Лаборатория базовых знаний, 2003. 288 с.
6. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. — М.: Энергоатомиздат, 1988. 480 с.
7. Москинова Г.И. Дискретная математика. Математика для менеджера в примерах и упражнениях. — М.: Логос, 2000. 240 с.
8. Нефедов В.Н., Осипова В.А. Курс дискретной математики. — М.: МАИ, 1992. 264 с.
9. Новиков Ф.А. Дискретная математика для программистов. — СПб.: Питер, 2000. 304 с.
10. Романовский И.В. Дискретный анализ. — СПб.: Невский Диалект, БХВ — Петербург, 2003. 320 с.
11. Судоплатов С.В., Овчинникова Е.В. Элементы дискретной математики. — М.: ИНФРА — М, Новосибирск: НГТУ, 2002. 280 с.
12. Яблонский С.В. Введение в дискретную математику. — М.: Наука, 1979. 272 с.