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

Маршрутом называют последовательность вершин и ребер, в которой любые два соседних элемента инцидентны, Если маршрут в простом графе задан последовательностью вершин 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. склейка вершин - любые две вершины можно склеить в одну: при этом все ребра, которые вели в две указанные вершины теперь ведут в одну вершину.