3. Операции на графах (объединение, пересечение, декартово произведение, произведение, композиция графов).

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

Пусть G1 ( X1 , E1 ) и G2 ( X2 , E2 ) – произвольные графы. Объединением G1 ∪ G2 графов G1 и G2 называется граф с множеством вершин X1 ∪ X2, и с множеством ребер (дуг) E1 ∪ E2.

Операция объединения обладает следующими свойствами, которые следуют из определения операции и свойств операций на множествах:

1. G1 ∪ G2 = G2 ∪ G1 – свойство коммутативности;
2. G1 ∪ ( G2 ∪ G3 ) = ( G1 ∪ G2 ) ∪ G3 – свойство ассоциативности.

Пересечение графов.

Пусть G1 ( X1 , E1 ) и G2 ( X2 , E2 ) – произвольные графы. Пересечением G1 ∩ G2 графов G1 и G2 называется граф с множеством вершин X1 ∩ X2 с множеством ребер (дуг) E = E1 ∩ E2.

Операция пересечения обладает следующими свойствами, которые следуют из определения операции и свойств операций на множествах:

1. G1 ∩ G2 = G2 ∩ G1 – свойство коммутативности;
2. G1 ∩ ( G2 ∩ G3 ) = ( G1 ∩ G2 ) ∩ G3 – свойство ассоциативности.

Композиция графов.

Пусть G1 ( X , E1 ) и G2 ( X , E2 ) — два графа с одним и тем же множеством вершин X. Композицией G1 ( G2 ) графов G1 и G2 называется граф с множеством вершин E, в котором существует дуга ( xi , xj ) тогда и только тогда, когда существует дуга ( xi , xk ), принадлежащая множеству E1 , и дуга ( xk , xj ), принадлежащая множеству E2.

Декартово произведение графов.

Пусть G1 ( X, E1 ) и G2 ( Y, E2 ) — два графа. Декартовым произведением G1 ( X, E1 ) × G2 ( Y, E2 ) графов G1 ( X, E1 ) и G2 ( Y, E2 ) называется граф с множеством вершин X × Y, в котором дуга (ребро), идущая из вершины ( xi , yj ) в ( xk , xl ), существует тогда и только тогда когда существует дуга ( xi , xk ), принадлежащая множеству дуг E1 и j = l или когда существует дуга ( yj , yl ), принадлежащая множеству E2 и i = k.

Операция произведения графов.

Пусть G1 ( X, E1 ) и G2 ( Y, E2 ) - два графа. Произведением G1 · G2 графов G1 и G2 называется граф с множеством вершин X × Y, а дуга из вершины ( xi , yj ) в вершину ( xk , yl ) существует тогда и только тогда, когда существуют дуги ( xi , xk ) ∈ E1 и ( yj , yl ) ∈ E2.