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

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

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

Если в орграфе полустепень захода некоторой вершины равна нулю (то есть 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 ₁