Лекции ДМ

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

Так как граф G(V, X) задается двумя множествами V и X , то для него определены теоретико-множественные операции : объединение и пересечение.

Объединением графов G₁(V₁, X₁), G₂(V₂, X₂) называется граф G(V, X), где V = V₁ V₂ , X = X₁ X₂ .

Пересечением графов G₁(V₁, X₁), G₂(V₂, X₂) называется граф G(V, X), где V = V₁ V₂ , X = X₁ X₂ .

Кроме этих операций познакомимся с понятиями : подграф и сурграф.

Подграфом графа G(V, X) называется граф G^’(V^’, X^’) , где G^’ G, X’ X.

Подграф G^’(V^’, X^’) графа G(V, X) называется собственным, если G^’ G, X’ X.

Подграфом графа G(V, X) , порожденным множеством V₁  V, где V₁ , называется граф G₁(V₁, X₁), где Х₁  Х и соединяет вершины только из V₁ .

Сурграфом графа G(V, X) называется граф G”(V, X”), где V=V, X”  X.

Рис.13.6.

Рис. 13.7.

Рис.13.8.

На рисунке 13.6 представлен собственный подграф графа 13.5.

На рисунке 13.7 – подграф графа 13.5, порожденный множеством V₁ ={v₁, v₂, v₄, v₆}.

На рисунке 13.8 – сурграф графа 13.5.