Практическая работа №12. Маршруты связных графов, оценка по их цене (расстоянию)

Практическая работа № 12. Маршруты связных графов, оценка по их цене (расстоянию).

1. Цель работы: приобретение практических навыков в определении характеристик связности неориентированных графов, изучение различных алгоритмов нахождения кратчайших маршрутов. Изучение неориентированных графов (способы задания графов, анализ графов на минимум и максимум).


2. Теоретическая часть:
Граф – это система, которая интуитивно может быть рассмотрена как множество точек и множество соединяющих их линий Точки - называются вершинами графа, линии со стрелками – дугами, без стрелок – рёбрами.
Неориентированный граф  задается двумя множествами  , где  — конечное множество, элементы которого называют вершинами или узлами;  — множество неупорядоченных пар на  , т.е. подмножество множества двухэлементных подмножеств  , элементы которого называют ребрами. Для каждого ребра  считаем, что  и  — различные вершины.
Граф называется ориентированным (или орграфом), если некоторые ребра имеют направление. Это означает, что в орграфе некоторая вершина может быть соединена с другой вершиной, а обратного соединения нет.
Вершины  и  , соединенные ребром  , называют смежными, а также концами ребра  . Если  , говорят, что вершины  и  связаны отношением непосредственной достижимости.
Ребро  называют инцидентным вершине  , если она является одним из его концов.
Степенью вершины  называют число  всех инцидентных ей ребер.
Маршрут в графе – это последовательность соседних (смежных) вершин.
Цикл – замкнутый маршрут, являющийся цепью.
Длина маршрута – это количество ребер с повторениями