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

Граф 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".

Пример 3.

Какими особенностями отличается граф G, взаимно однозначно соответствующий бинарному отношению R, если R:

а) симметрично;

б) антисимметрично;

в) рефлексивно;

г) антирефлексивно;

д) транзитивно.

Пусть бинарное отношение R определено на множестве V= {v₁,... ,v_n }.

а) Симметричному отношению R взаимно однозначно соответствует неориентированный граф без кратных ребер G(R) в котором ребро ( ) существует, если и только если выполнено (а значит, и в силу симметричности R).

б) Антисимметричному отношению R взаимно однозначно соответствует ориентированный граф без кратных ребер, не содержащий пар вершин с ребрами, противоположно направленными к разным вершинам.

в) Если R рефлексивно, то граф G(R) без кратных ребер имеет петли во всех вершинах.

г) Если R антирефлексивно, то граф G(R) без кратных ребер не имеет петель.

д) Если R транзитивно, то в графе G(R) без кратных ребер для каждой пары ребер ( ) и ( ) имеется замыкающее ребро ( ).

Вопросы для повторения

1.Чему посвящен раздел дискретной математики, изучающий теорию графов?

2.В чем отличие ориентированного и неориентированного графов?

3.Дайте определение графа?

4.В чем заключается смысл отношения инцидентности?

5.Локальная степень вершины графа это?

6.В каком случае графы называются изоморфными?

7.Назовите способы задания графов?

8.Перечислите отличия матрицы инцидентности и матрицы смежности?

9.Когда граф называется частью графа?

Резюме по теме

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