Операции над частями графа. Графы и бинарные отношения

Граф H называется частью графа G, H G если V(Н) V(G) и E(H) Е(G).

Если V(Н) = V(G), часть H графа G называется суграфом. Суграф является покрывающим для н-графа G если любая вершина графа G инцидентна хотя бы одному ребру из H.

Подграфом G(V’) графа G(V) с множеством вершин V V’ называется часть, которой принадлежат все ребра с обоими концами из V’.

Над частями графа G могут производиться следующие операции:

· дополнение к части H - определяется множеством всех ребер графа G не принадлежащих H: E(H) Е( ) = , Е(H) Е( ) = Е(G):

· сумма H₁ H₂ частей H₁, и H₂ графа G:

V (H₁ H₂)= V(Н₁) V(H₂) и Е(H₁ H₂)= E(Н₁) E(H₂);

· произведение H₁ H₂:

V (H₁ H₂)= V(Н₁) V(H₂) и Е(H₁ H₂)= E(Н₁) E(H₂).

Две части H₁ и H₂ не пересекаются по вершинам, если они не имеют общих вершин V(Н₁) V(H₂) = , а значит, и общих ребер E(Н₁) E(H₂)= . Части H₁ и H₂ не пересекаются по ребрам, если E(Н₁) E(H₂)= . Если V(Н₁) V(H₂) = , то сумма H₁ Н₂ называется прямой.

Графы и бинарные отношения: отношению R, заданному на множестве V, взаимно однозначно соответствует ориентированный граф G(R) без кратных ребер с множеством вершин V, в котором ребро (v', v") существует, только если выполнено v'Rv".