Маршруты, цепи и циклы

Маршрутом в графе называется чередующаяся последовательность вершин и ребер Маршруты, цепи и циклы - student2.ru Маршруты, цепи и циклы - student2.ru Маршруты, цепи и циклы - student2.ru Маршруты, цепи и циклы - student2.ru Маршруты, цепи и циклы - student2.ruМаршруты, цепи и циклы - student2.ru Маршруты, цепи и циклы - student2.ru , в которой любые два соседних элемента инцидентны. Если Маршруты, цепи и циклы - student2.ru = Маршруты, цепи и циклы - student2.ru , то маршрут называется замкнутым, а если Маршруты, цепи и циклы - student2.ru , то – открытым.

Длиной маршрута считается число ребер, которые он содержит.

Маршрут называется цепью, если каждое ребро встречается в нем не более одного раза. Цепь, в которой все вершины различны, называется простой цепью.

Замкнутая цепь называется циклом, а простая замкнутая цепь – простым циклом.

Если есть цепь, соединяющая две вершины Маршруты, цепи и циклы - student2.ru и Маршруты, цепи и циклы - student2.ru , то есть и простая цепь, соединяющая эти вершины. Две вершины называются связными, если существует связывающая их простая сеть; в противном случае вершины называются несвязными.

Граф называется связным, если каждые две его вершины связные; в противном случае – несвязным.

Деревья

Неориентированный граф называется деревом, если он связен и не имеет циклов.

Основные свойства деревьев:

– любые две вершины дерева можно соединить ровно одной простой цепью;

– если дерево G содержит хотя бы одно ребро, на нем найдется висячая вершина;

– число ребер дерева G на единицу меньше числа его вершин.

Справедливо и обратное утверждение: если у связного графа число ребер на единицу меньше числа вершин, то такой граф является деревом.

Дерево Маршруты, цепи и циклы - student2.ru множество вершин которого совпадает с множеством вершин графа Маршруты, цепи и циклы - student2.ru а ребра являются ребрами графа G( Маршруты, цепи и циклы - student2.ru ), называется остовным (покрывающим) деревом графа G. Иными словами, остовное дерево графа G – это его подграф, содержащий все вершины и являющийся деревом.

Если n – число вершин, а m – число ребер графа G, то любое его остовное дерево имеет n вершин и (n – 1) ребер. Таким образом, остовное дерево получается отбрасыванием (m – n + 1) ребер графа G. Число Маршруты, цепи и циклы - student2.ru называется цикломатическим числом графа G.

Если каждому ребру графа приписано некоторое положительное число, называемое его весом или стоимостью, то граф называется нагруженным. Стоимостью нагруженного графа считается суммарная стоимость всех его ребер. Многие задачи, связанные с построением экономичных систем сообщения или информационных систем, приводят к задаче поиска остовного дерева минимальной стоимости.

Пример 11.Построить остовное дерево минимальной стоимости для графа, представленного на рисунке 6. Определить его стоимость.

Маршруты, цепи и циклы - student2.ru Маршруты, цепи и циклы - student2.ru

Рис. 6 Рис. 7

Р е ш е н и е. Остовное дерево содержит все вершины исходного графа, т.е. в нем будет 5 вершин и 4 ребра. Прежде всего, найдем на нагруженном графе самое легкое ребро. В данном случае это ребро, соединяющее вторую и пятую вершины Маршруты, цепи и циклы - student2.ru и имеющее стоимость 1. Это будет первым ребром остовного дерева минимальной стоимости (рис. 7).

Теперь среди оставшихся ребер выберем следующие по стоимости ребра Маршруты, цепи и циклы - student2.ru и Маршруты, цепи и циклы - student2.ru . Поскольку оба они соединяют одну из уже отобранных в оставное дерево вершину Маршруты, цепи и циклы - student2.ru или Маршруты, цепи и циклы - student2.ru с новой, еще не присоединенной вершиной Маршруты, цепи и циклы - student2.ru и Маршруты, цепи и циклы - student2.ru соответственно, то оба эти ребра нужно добавить к дереву.

Среди ребер стоимостью 3 два ребра Маршруты, цепи и циклы - student2.ru и Маршруты, цепи и циклы - student2.ru соединяют между собой вершины, уже присоединенные к дереву, и, следовательно, не могут быть включены в него. Третье ребро Маршруты, цепи и циклы - student2.ru соединяет вершину дерева Маршруты, цепи и циклы - student2.ru с еще не присоединенной вершиной Маршруты, цепи и циклы - student2.ru , т.е. может быть присоединено к дереву. Получившееся остовное дерево имеет минимальную стоимость, которая равна сумме стоимостей ребер в него отобранных: 1+2+2+3 = 8.►

Тема 5. Теория алгоритмов

Общее понятие алгоритм. Требования к алгоритмам. Понятие рекурсии. Рекурсивные функции. Простейшие рекурсивные функции. Операторы образования примитивно-рекурсивных и частично-рекурсивных функций. Тезис Чёрча. Разрешимые и перечислимые множества. Машина Тьюринга[5]*. Универсальная машина Тьюринга*. ([1, часть 8, кроме разд. III]; [3, § 14.1, 14.2]).

Наши рекомендации