Программирование на языке Pascal
это длина кратчайшего пути от
Расстояние между вершинами u и v - это длина кратчайшего пути от u до v. Из этого определения видно, что расстояние между вершинами a и c в графе на рис. 11.1 равно 2.
Цикл - это замкнутый путь. Все вершины в цикле, кроме первой и последней, должны быть различны. Например, циклом является путь abda в графе на рис. 11.1.
Эйлеров граф - это граф, в котором существует путь или цикл, содержащий все ребра графа (вершины могут повторяться). Именно такие графы положительно решают упомянутую в начале лекции задачу о кенигсбергских мостах. Например, граф на рис. 11.5 является Эйлеровым: искомым путем в нем будет dbacfbcd.
Рис. 11.5. Граф Эйлера
Гамильтонов граф - это граф, в котором существует путь или цикл (без повторений), содержащий все вершины графа (см. рис. 11.5; искомый цикл: abdfca).
on_load_lecture()
1
|
2
|
3
|
4
|
вопросы | »
учебники
|
для печати и PDA
|
Курсы | Учебные программы | Учебники | Новости | Форум | Помощь Телефон: +7 (495) 253-9312, 253-9313, факс: +7 (495) 253-9310, email: info@intuit.ru © 2003-2007, INTUIT.ru::Интернет-Университет Информационных Технологий - дистанционное образование |
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий