3.4Направленные орграфы и сети

Если в графе ориентировать все ребра, то получится орграф, который называется направленным. Направленный орграф, полученный из полного графа, называется турниром.

Термин «турнир» имеет следующее происхождение. Рассмотрим спортивное соревно­вание для пар участников (или пар команд), где не предусматриваются ничьи. Пометим вершины орграфа участниками и проведем дуги от победителей к побежденным. В таком случае турнир в смысле теории графов — это как раз результат однокругового турнира в спортивном смысле.

Если в орграфе полустепень захода некоторой вершины равна нулю (то есть d⁺(v) = 0), то такая вершина называется источником, если же нулю равна полу­степень исхода (то есть d^-(v) = 0), то вершина называется стоком. Направлен­ный орграф с одним источником и одним стоком называется сетью.

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

Рассмотрим следующие операции над графами:

8. Дополнением графа G₁(V₁, E₁) (обозначение ) называется граф G(V₂, E₂), где

Пример дополнения графа приведен на рис. 10.

Рис. 10. Граф G₁ и его дополнение

9. Объединением графов G₁(V₁, E₁) и G₂(V₂, E₂) {обозначение , называется граф G(V, E), где

Объединение называется дизъюнктным, если .

10. Пересечением графов G₁(V₁, E₁) и G₂(V₂, E₂) {обозначение , называется граф G(V, E), где

Пример объединения и пересечения графов приведен на рис. 11.

11. Соединением графов G₁(V₁, E₁) и G₂(V₂, E₂) (обозначение при условии , ) называется граф G(V, E), где

Пример соединения графов приведен на рис. 12.

12. Удаление вершины v из графа G₁(V₁, E₁) (обозначение G₁(V₁, E₁) – v, при условии ) дает граф G₂(V₂, E₂), где

Пример удаления вершины из графа приведен на рис. 13.

G₁ G₂

Рис. 11. Графы G₁, G₂ и их объединение и пересечение

K₂ K₃ K₅ = K₂ + K₃

Рис. 12. Графы K₂, K₃ и их соединение

G₁ G₁ – v

Рис. 13. Удаление вершины v из графа G₁

13. Удаление ребра е из графа G₁(V₁, E₁) (обозначение G₁(V₁, E₁) – e, при усло­вии ) дает граф G₂(V₂, E₂), где

Пример удаления ребра из графа приведен на рис. 14.

G₁ G₁ – е

Рис.14. Удаление ребра е из графа G₁

14. Добавление вершины v в граф G₁(V₁, E₁) (обозначение G₁(V₁, E₁) + v, при условии ) дает граф G₂(V₂, E₂), где

Пример добавления вершины в граф приведен на рис. 15.

G₁ G₁ + v

Рис. 15. Добавление вершины v в граф G₁

15. Добавление ребра е в граф G₁(V₁, E₁) (обозначение G₁(V₁, E₁) + e, при усло­вии ) дает граф G₂(V₂, E₂), где

.

Пример добавления ребра в граф приведен на рис. 16.

G₁ G₁ + e

Рис. 16. Добавление ребра e в граф G₁

16. Стягивание подграфа А графа G₁(V₁, E₁) (обозначение G₁(V₁, E₁)/A, при условии ) дает граф G₂(V₂, E₂), где

Пример стягивания подграфа приведен на рис. 17.

G₁ G₁/A

Рис. 17. Стягивание подграфа A в графе G₁

17. Размножение вершины v графа G₁(V₁, E₁) (обозначение G₁(V₁, E₁)  v, при условии , ) дает граф G₂(V₂, E₂), где

Пример размножения вершины приведен на рис. 18.

G₁ G₁  v

Рис. 18. Размножение вершины v в графе G₁