Операции над графами
Граф Н называется подграфом (или частью) графа G, если VH I VG, ЕH I ЕG. Подграф Н называется остовным подграфом, если VH = VG. Если множество вершин подграфа Н есть U, а множество его ребер совпадает с множеством всех ребер графа G, оба конца которых принадлежат U, то Н называется подграфом, порожденным множеством U.
На рис.2.11 изображены граф G и три его подграфа Н1, Н2 и Н3 , среди которых Н3 является остовным, а Н2 – порожденным.
 |
Граф Н называется объединением графов 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).
Граф, изоморфный своему дополнению, называется самодопол-нительным.