какая-то теория / операции над графами

3. Операция введения ребра

Пусть дан граф G=(V,E) и u, v V− две его несмежные вершины, то есть ребро e=<u,v> E (дуга e =(u,v) E ).

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

Задача 3.

Пусть дан граф G=(V,E). Выполнить над графом операцию введения ребра <v1, v5>.

Задача 3.

Пусть дан граф G=(V,E). Выполнить над графом операцию введения ребра <v1, v5>.

Решение.

4. Операция введения вершины в ребро

Пусть дан граф G=(V,E) и (u, v) – некоторое его ребро.

Добавлением вершины w в ребро (u, v)

называется операция, в результате которой

получается два ребра (u, w) и (w, v) , а ребро (u, v) удаляется из графа G.

Замечание 5. Для орграфов операция введения вершины в ребро выполняется с учетом ориентации этого ребра

Задача 4.

Пусть дан граф G=(V,E). Выполнить над графом операцию введения вершины в ребро <v3, v4>.

Задача 4.

Пусть дан граф G=(V,E). Выполнить над графом операцию введения вершины в ребро <v3, v4>.

Решение.

5. Операция объединения графов

Пусть даны графы G1=(V1,E1) и G2=(V2,E2).

1

Задача 5.

Найти объединение следующих графов: а) G1 и G2

Задача 5.

Найти объединение следующих графов: а) G1 и G2

Решение.

Задача 5.

Найти объединение следующих графов: б) H1 и H2