Маршруты, циклы и связность
Маршруты, циклы и связность
Значительная часть теории графов и ее приложений занимается вопросами существования и изучения свойств маршрутов в графах.
Пусть G = (V, E) – граф. Маршрутом длины k в графе G из вершины v в вершину w называется последовательность <v0, v1, v2, …, vk> вершин (необязательно различных) vi Î V, таких, что v0 = v, vk = w, а [vi-1, vi] Î E для i = 1, …, k.
Маршрут называется замкнутым, если v0 = vk.
Маршрут называется цепью, если все его вершины различны. Замкнутая цепь называется циклом. Цикл называется простым, если только v0 = vk, а остальные вершины vi различны.
Если существует маршрут из v в w, v, w Î V, то говорят, что w достижима из v.
Обратите внимание на лекцию "Экзаменационные билеты".
Граф без циклов называется ациклическим.
Граф G = (V, E) называется связным, если каждая пара различных вершин может быть соединена маршрутом.
Деревом называется связный ациклический граф. Корневым деревом называется дерево с выделенной вершиной, называемой корнем.
Остовным деревом для G = (V, E) называется остовный подграф, являющийся деревом.
Пусть {Vi : 1 £ i £ p} – разбиение графа G = (V, E), определяемое отношением R*. (R* - отношение рефлексивного замыкания). Тогда p – число связности графа G = (V, E). Подграфы (Vi, Ei), порожденные классами эквивалентности, называют компонентами связности графа G.
Лесом называется граф, в котором каждая связная компонента является деревом. Остовный лес для графа G = (V, E) – это совокупность вершин разъединенных деревьев Ti = (Vi, Ei):
