Операции над графами

Граф Н называется подграфом (или частью) графа G, если VH I VG, ЕH I ЕG. Подграф Н называется остовным подграфом, если VH = VG. Если множество вершин подграфа Н есть U, а множество его ребер совпадает с множеством всех ребер графа G, оба конца которых принадлежат U, то Н называется подграфом, порожденным множеством U.

Граф Н называется объединением графов F и G, если V(H) = V(G)È È V(F) и E(H)= E(G) È E(F). В этой ситуации пишут Н = F È G. Объединение F ÈG называется дизъюнктным, если V(G) Ç V(F) = ?.

Введем операцию произведения графов. Пусть задано два графа G1 = (V1, E1), G2 = (V2, E2). Произведением графов называется граф, для которого – декартово произведение множеств вершин исходных графов, а E(G) определяется следующим образом: вершины (и1, и2) и (v1, v2) в графе G смежны тогда и только тогда, когда или и1 = v1, а и2 и v2 смежны в G2, или и2 = v2, а и2 и v2 смежны в G1 (рис. 2.12).

Очевидно, что ,

.

С помощью операции произведения можно определить п-мерный куб рекуррентно: .

Покажем, что это определение совпадает с данным ранее. Действительно, . Вершины графа можно представить векторами длины п из 0 и 1 таким образом, что две вершины будут смежны тогда и только тогда, когда соответствующие векторы различаются в одной координате.

Для произвольного графа G следующим образом определяется дополнительный граф (или дополнение) : , и две несовпадающие вершины смежны в тогда и только тогда, когда они не смежны в G: (рис. 2.13).

Граф, изоморфный своему дополнению, называется самодопол-нительным.