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

Объединением графов G₁(x₁,г₁x₁) и G₂(x₂,г₂x₂) называется такой граф G(x,гx), у которого множество вершин есть сумма множеств вершин объединяемых графов x=x₁Èx₂, а отображение есть сумма отображений объединяемых графов гx=г₁x₁Èг₂x₂, что обозначается: G=G₁ÈG₂.

Пример. Заданы графы G₁ и G₂:

Требуется определить G(x,гx)=G₁ÈG₂.

Геометрическая реализация складываемых графов и графа-суммы имеет следующий вид (рис. 3.1.14):

Рис. 3.1.14

Граф-сумма содержит все вершины и дуги, встречающиеся хотя бы в одном из двух складываемых графов.