это длина кратчайшего пути от

Расстояние между вершинами 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

Содержание Назад Вперед