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

Дополнение графа F(V, E) имеет в качестве множества вершин множество V, причем две вершины в смежные тогда и только тогда, когда они не являются смежными в F.

Пример (рис. 3.3). Граф 3.3, г является дополнением к графу 3.3, б.

Пусть графы F₁ и F₂ имеют непересекающиеся множества V₁ и V₂ вершин и непересекающиеся множества ребер E₁ и E₂.

Объединением F₁ÈF₂ таких графов называется граф с множеством вершин V₁ÈV₂ и множеством ребер E₁ÈE₂. Соединение F₁+F₂графовсостоит из их объединения F₁ÈF₂ и всех ребер, соединяющих V₁ и V₂.

Чтобы определить произведение F₁´F₂, рассмотрим любые две вершины u = (u₁, u₂) и v = (v₁, v₂) из декартова произведения V₁´V₂. Вершины u и v смежные в F₁´F₂ тогда и только тогда, когда: либо u₁ = v₁ и u₂ - вершина, смежная с v₂, либо u₂ = v₂ и u₁ - вершина, смежная с v₁.

Композиция F₁ [F₂] также имеет декартово произведение V₁´V₂ в качестве множества вершин, и вершина u = (u₁, u₂) смежная с вершиной v = (v₁, v₂) тогда и только тогда, когда: либо u₁ - вершина, смежная с v₁, либо u₁ = v₁ и u₂ - вершина, смежная с v₂.