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

Маршрутом называют последовательность вершин и ребер, в которой любые два соседних элемента инцидентны, Если маршрут в простом графе задан последовательностью вершин V0, V1.....Vk, то вершины V0, Vk называют концами маршрута.Если v0 = vk, то маршрут называют замкнутым, в противном случае - незамкнутым.

пример маршрута: 1-2-3-5-7-4-3-5-6-2-3

пример замкнутого маршрута : 3-4-5-7-3-4-1-3

 

Цепь - маршрут, в котором нет повторений ребер, соединяет концы.

пример цепи: 6-5-3-4-5-7-3-2-6-8

 

Цикл - замкнутая цепь.

пример цикла: 5-3-2-6-5-7-4-5

 

42. Операции над графами.

1. объединение - граф G (V U) называется объединением графов,если V1 объединено с V2, а U1 объединено с U2.

2. произведение - граф G (V U) называется произведением графов G1(V1 U1) и G2(V2 U2) (G=G1хG2), если V=V1хV2 - декартово произведение множеств вершин исходных графов.

3. Пересечение графов- Пересечение графов G1и G2, обозначаемое как , представляет собой граф . Таким образом, множество вершин графа G4состоит из вершин, присутствующих одновременно в G1и G2

4.Добавление вершины - к любому графу можно добавить одну вершину, не соединенную с другими вершинами и ребрами.

5.добавление ребра - любые две вершины можно соединить ребром.

6.удаление вершины - Если в графе есть вершина,которая не связана ребрами с другими вершинами, то данную вершину можно удалить из графа.

7. удаление ребра - любое ребро можно удалить из графа.

8. разбитие графа - любое ребро можно "разбить" путем добавления на него новую вершину.

9. расщепление вершины - любую вершину можно расщеплять на две. при этом часть ребер остается у исходной вершины, а оставшиеся ребра идут в новую вершину.

10. склейка вершин - любые две вершины можно склеить в одну : при этом все ребра, которые вели в две указанные вершины теперь ведут в одну вершину.

 

43. Деревья.(ориентированные, сбалансированные, бинарные, остовные)

Деревом называют связный граф, не содержищий циклов. т.к любой граф без циклов называются лесом, то компонентами леса являются деревья.

Ориентированным деревом ( или ордеревом) называется ориентированный граф без циклов, во все вершины которого, кроме одной, входит ровно одна дуга. Единственная вершина, из которой дуги только выходят, называется корнем дерева. Остальные вершины называются узлами дерева.

Висячая вершина ордерева называется листом. Путь из корня в лист называется ветвью. Длина наибольшей ветви называется высотой ордерева.

Расстояиние от корня до некоторой вершины называется уровнем вершины. Сам корень имеет уровень 0. Вершины одного уровня образуют ярус дерева.

 

Бинарным деревом называется ордерево, из каждой вершины которого выходит не более двух дуг.

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

 

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