Примеры типовых задач:

Рис.6

Пример 1. Задать граф G1, представ­ленный на рис.6, через множества вер­шин V1 и ребер E1.

Граф G1 может быть полностью оп­ределен:

• двумя множе­ствами поимено­ванных вершин V1 = {v1, v2, v3, v4, v5} и поименованных ребер Е1 = {е1, e2, e3, e4} (в строгом смысле требуется установление от­ношения инцидентности ребер соответствующим вер­шинам);

• множеством ребер, каждое из которых представлено па­рой своих концевых вершин: Е= {(v1, v4), (v4, v3), (v3, v5), (v5,v2)}.

• Порядок указания вершин при описании ребра здесь без­различен, так как все ребра в графе G неориентированные.

Рис. 7

Пример 2. На рис.7 изображены графы G1- G12 с че­тырьмя вершинами в каждом. Сравнить графы. Результаты сравнения графов таковы:

G1 - G7 - неориентированные;

G8 - G12 - ориентирован­ные;

G1, G2 - полные, причем G1 = G2;

G7 - не является полным, так как хотя каждая пара вер­шин и соединена ребром, но имеется одна петля. (Иногда полным называют граф с петлями во всех вершинах, каждая пара которых соединена ребром. Граф G7 не отвечает и это­му определению. В дальнейшем мы будем придерживаться определения полного графа, данного в начале параграфа.)

G3 - все вершины этого графа являются изолированными (граф с пустым множеством ребер, т.е. Е = );

G4 и G5 являются дополнением друг другу: G= G5 и G5= G4;

G6 - мультиграф, так как содержит кратные ребра а и b, a также е и f;

G8 - ориентированный, канонически соответствующий неориентированному графу G5;

G9 и GI0 не являются равными, так как имеют отличаю­щиеся ребра: (4, 1) - в G9 и (1, 4) - в GI0;

G11 - ориентированный мультиграф: ребра а и b-крат­ные, тогда как G12 мультиграфом не является, поскольку в нем ребра а и b различно ориентированы.

Рис. 8

Пример 3. Чему равны степени вершин графов G1, G3 на рис. 8?

Оба графа имеют по четыре вершины: V= {1, 2, 3, 4}.

Степени вершин неориентированного графа G1: ρ (1) = 3, ρ (2) = 4, ρ (3) = 3, ρ (4) = 4, если условиться считать вклад петли в степень вершины, равный 2, и ρ(4) = 3, если петля дает вклад 1 в степень вершины. Сумма степеней всех вер­шин графа G1 равна 14, т.е. вдвое больше числа ребер графа:

где т = 7 - число ребер графа.

Степени вершин ориентированного графа G3:

ρ 1(1) = 2, ρ 1(2) = 3, ρ 1(3)=1, ρ 1(4)=1;

ρ 2(1)=1, ρ 2(3) = 1, ρ 2(3) = 2, ρ 2(4) = 3.

Суммы степеней вершин первого и второго типа графа G3 совпадают и равны числу т ребер графа:

Задачи для самостоятельного решения.

1. Задать графы G2 – G5 (см. рис. 6) множествами их вершин и ребер. Сравнить графы G1 – G5 (см. пример 1):

2. Равны ли графы G1 - G2 на рис. 8? Задать графы G1 – G5 множествами их вершин и ребер. Сравнить графы.

3. Определить дополнение графа G, если:

a) G - пятиугольник; б) G - треугольник.

4. Какой ориентированный граф канонически соответству­ет графу G (представить графически)?

5. Докажите, что сумма всех степеней вершин графа равна удвоенному количеству рёбер.

6. Докажите, что в любом графе количество вершин нечётной степени – чётное число.