Ориентированные графы - основные определения
Ориентированные графы
Основные определения
Во многих приложениях теории графов требуется, чтобы ребра графа имели направление. Например: поток данных, проходящий через программу.
Ориентированный граф G (или просто орграф) есть пара G = (V, E), где V – конечное множество вершин, а E – произвольное подмножество.
Ориентированный граф G = (V, E) определяет отношение на V. Этот факт можно доказать следующим образом. Пусть R – отношение, такое, что vRw тогда и только тогда, когда (v, w) Î E. Очевидно, что R является отношением.
Обратное утверждение также верно: пусть V – конечное множество вершин. Тогда отношение на V определяет ориентированный граф, у которого множество вершин V. Этот факт можно доказать так. Если R – отношение на V, то орграф G = (V, E), определяемый отношением R, имеет множество ребер E, где (v, w) Î E тогда и только тогда, когда vRw.
Направление ребра обозначают порядком в V ´ V. Например, если (v, w) Î E, то ребро выходит из v и входит в w.
Приведем пример построения ориентированного графа (рис. 3).
Пусть V = {v1, v2, v3}, E1 = {(v1, v2), (v2, v3), (v3, v1)}. Тогда получим граф G1 = (V, E1) (рис. 3, а).
Если Вам понравилась эта лекция, то понравится и эта - 8. Операционный метод математического описания.
Пусть V = {v1, v2, v3}, E2 = {(v1, v1), (v1, v2), (v1, v3), (v2, v3), (v3, v1)}. Тогда получим граф G2 = (V, E2) (рис. 3, б).
Рис. 3. Примеры ориентированных графов:
а – граф G1 = (V, E1); б – граф G2 = (V, E2);
Для орграфа реберное отношение необязательно симметрично или рефлексивно. Поэтому допустимы ребра типа (v, v), называемые петлями. Степень вершины v ÎV обозначается s(v) = s + (v) + s - (v), где s - (v) – число ребер, входящих в v, s + (v) – число ребер, выходящих из v.
Множества {w: (w, v) Î E} и {w: (v, w) Î E} называют соответственно входящим узлом и выходящим узлом.