Решение.

Примеры.

П. 7. Ориентированные графы.

Вводя понятие графа, мы интерпретировали ребро (дугу) u как символ связи между двумя объектами. Но часто такая связь бывает неравнозначной. Например: 1. Два человека могут быть не просто знакомыми, а, допустим, один из них по службе подчиняется другому, или один из них является родителем другого. 2. Схема города – граф с вершинами на перекрестках и поворотах, а если ввести одностороннее движение транспорта, то на ребрах необходимо ставить указатели направления движения.

Чтобы отразить подчинение одной вершины другой, рассматривают упорядоченные пары вершин, а соответствующий граф называют ориентированным графом или орграфом.

Определение 33. Ориентированным графом называется упорядоченная пара , где – множество вершин, – множество упорядоченных пар различных вершин из V.

Определение 34. Упорядоченная пара (a, b)называется ориентированным ребром или дугой , идущим из вершины а к вершине b.

На диаграммах ориентированных графов и мультиграфов ребра снабжают стрелкой, указывающей, в какую вершину идет данное ребро.

Иногда ориентированное ребро (или дугу) от А к В обозначают: , А – начальная вершина, В – конечная вершина.

Замечание. Ориентированный граф определяется как кортеж , где V – набор вершин, а W – подмножество , обозначающее ребра.

Пример. Пусть Х – множество лиц некоторой военной организации. Бинарное отношение R на множестве Х введем следующим образом: xRy, если лицо у подчинено лицу х. Итак, (X, G) – граф. Связь любого начальника с подчиненным изобразиться в виде ребра графа (X, G).

Определение 33 можно переписать: Граф, все ребра которого ориентированы, называется ориентированным графом.

Соответствующим образом можно определить и ориентированные мультиграфы.

1. Изобразить орграф , где , .

2. Проводится круговой турнир по баскетболу между командами A, B, C, D, E. Каждая команда играет с каждой командой по одному разу. Требуется изобразить итоги турнира: В выиграла все встречи, С проиграла все, А выиграла у С и D и проиграла у В и D.