6.6. Основные операции над графами.

Объединением графов G₁=(V₁, E₁) и G₂=(V₂, E₂) называется граф G₃=(V₁V₂, E₁E₂). Объединение называется дизъюнктным , если V₁V₂=0.

Пересечение графов G₁=(V₁, E₁) и G₂=(V₂, E₂) называется граф G₃=(V₁V₂, E₁E₂).

Аналогично определяются объединение, дизъюнктное объединение и пересечение любого количества графов. Операции объединения и пересечения являются коммутативными, т.е. G₁ G₂= G₂ G₁, а также G₁ G₂= G₂ G₁

Пример. На ниже приведённом рисунке показаны: а) – граф G₁, б) – граф G₂, в) – их объединение, г) – пересечение.

б)

Рис. 20

Удаление вершины. При удалении вершины из графа удаляются и все инцидентные ей рёбра (дуги).

Удаление ребра (дуги). При удалении ребра (дуги) его концевые вершины не удаляются. Операцией обратной к операции удаления ребра является операция добавления ребра.

Слияние (отождествление) вершин. Говорят, что вершины v_i и v_j в графе G отождествляются (сливаются) если они заменяются новой вершиной v_k такой, что все ребра (дуги) графа инцидентные v_i и v_j становятся инцидентными к вершине v_k .

Стягивание ребра – эта операция означает удаление ребра и отождествление его концевых вершин. Граф G называется стягиваемым графу Н, если граф Н может быть получен из G в результате некоторой последовательности стягиваний ребер.

Подразбиение ребра. При выполнении этой операции из графа удаляется ребро (v_i, v_j) и добавляются два новых (v_i, v_k) и (v_k, v_i), где v_k – новая вершина графа.

П ример: На следующем рисунке представлены: а) - исходный граф, б) – граф после удаления вершины v₃, в) - результат удаления ребра e₂, г) –отождествления вершин v₃ и v₄, д) –стягивание ребра e₁, е) – подразбиение ребра e₂.

Рис. 21

6.7. Маршруты в графах

Маршрутом в графе G=(V,E) называется чередующаяся последовательность вершин и ребер (дуг) – v₁, e₁, v₂, e₂, …., v_n, e_n,v_n+1, в которой любые два соседних элемента инциденты.

Маршрут, соединяющий вершины v₁ и v_n+1 можно также задать последовательностью из одних вершин v₁, v₂, v₃,…,v_n, v_n+1 или последовательностью ребер e₁, e₂,…,e_n. Число n ребер (или дуг) в маршруте называется его длиной. Маршрут называется циклическим, если v₁=v_n+1.

Маршруты в неориентированных графах.

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

Н еорграф без циклов называется ациклическим графом. Минимальная из длин циклов неорграфа называется его обхватом.

Пример 1: Рассмотрим неорграф

Рис. 22

В данном примере наборы вершин: (1,2) ; (1,2,4,7) являются простыми цепями,: (1,2,4,7,8,4) - непростая цепь, (1,2,4,7,8,4,2) – маршрут, который не является цепью, (1,2,4,8,7,4,1) – непростой цикл, (1,2,4,1) – простой цикл. Обхват графа равен 3.

Маршруты в ориентированных графах.

Маршрут ориентированного графа называется путем, если все его дуги различны.

Путь называется контуром, если v₁=v_n+1. Граф не имеющий контуров называется безконтурным. Вершина v называется достижимой из вершины u, если существует путь из u в v.

П ример 2: Рассмотрим ориентированный граф

Рис. 23

В данном примере наборы вершин (1,2,3,1) образуют контур. Заметим, что здесь вершина 5 – достигается из любой другой вершины, а из вершины 5 не достигается ни одна из остальных вершин.