Алгоритмы на графах
Определение 1. Маршрутом в графе между заданной парой вершин v1 и vk+1 называется чередующаяся последовательность вершин и рёбер вида: v1 e1 v2 e2 …. vk ek vk+1 где ei ={vi vi+1} , для всех i от 1 до k. Если нет кратных рёбер, то маршрут часто задают простым перечислением его вершин: v1 v2 …. vk vk+1 Маршрут может проходить по некоторым рёбрам несколько раз. Длина маршрута – число рёбер в нём. Определение 2. Для взвешенного графа вес маршрута между заданной парой вершин v1 и vk+1 определяется как сумма весов рёбер, входящих в этот маршрут. маршрут 5, 3, 2, 4, 3, 2, 1 ФПМИ БГУ Определение 3. Цепь - маршрут, в котором каждое ребро встречается не более одного раза (цепь может проходить через некоторые вершины несколько раз). Замкнутая цепь называется циклом. Определение 4. Простая цепь – цепь, в которой каждая вершина встречается не более одного раза. Замкнутая простая цепь называется простым циклом. цепь: 5, 3, 2, 4, 3 ,1 ФПМИ БГУ
