ГРАФ ОРИЕНТИРОВАННЫЙ

ГРАФ ОРИЕНТИРОВАННЫЙ - граф, каждому ребру к-рого приписана ориентация. Г. о. G задается множеством вершин V и набором Е упорядоченных пар вершин, наз. дугами. Говорят, что дуга (u, v) исходит из вершины u и входит в вершину v. Число дуг, исходящих из u, наз. полустепенью исхода вершины u, а число дуг, входящих в v, наз. полустепенью захода вершины v. Чередующаяся последовательность вершин и дуг v₀, e₁, е₂, ..., е_n, v_n, в к-рой e_i = {v_i-1, v_i), i = 1, 2, ..., n, наз. маршрутом (ориентированным). Маршрут наз. замкнутым, если его первая и последняя вершины совпадают. Путь - это маршрут, в к-ром все вершины различны. Контур - это нетривиальный (содержащий хотя бы одну дугу) замкнутый маршрут, у к-рого все вершины различны, кроме первой и последней. Если существует путь из вершины и в вершину v, то говорят, что v достижима из u.

Г. о. G с нумерованными вершинами v₁, ..., v_n и дугами e₁, ..., e_m можно задать матрицей инцидентности, т. е. матрицей ||b_ij|| размера n × m, в к-рой

Матрицей смежности A(G) вершин Г. о. G наз. матрица ||a_ij|| размера n × n, в к-рой элемент а_ij равен числу дуг, идущих из v_i в v_j. Суммы элементов по строкам матрицы A(G) равны полустепеням исхода вершин Г. о. G, а суммы элементов по столбцам - полустепеням захода. Элемент (i, j) матрицы A^k(G) (т. е. k-й степени матрицы смежности графа G) равен числу маршрутов длины k, идущих из v_i в v_j.

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

Г. о. используются: в теории вероятностей для представления Маркова цепей; в теории игр при описании множества игровых ситуаций и результатов состязаний; в математич. экономике при решении транспортных задач; в теории автоматов для задания диаграмм переходов и т. п. В самой теории графов при решении нек-рых задач относительно неориентированных графов иногда вводят ориентацию, сводя исходную задачу к задаче над Г. о. Основное отличие Г. о. от неориентированного графа проявляется при определении таких понятий, как путь, связность, достижимость, расстояние и др. Наиболее интересными типами Г. о. являются турниры, транзитивные графы, графы частичных порядков, растущие деревья, графы однозначных отображений, бесконтурные графы.

Лит.: [1] Зыков А. А., Теория конечных графов, [в. 1] Новосиб., 1969; [2] Xарари Ф., Теория графов, пер. с англ., М., 1973; [3] Picard С. F., Graphes et questionnaires, v. 1_2, P., 1972.

А. А. Сапоженко.

Источники:

1. Математическая Энциклопедия. Т. 1 (А - Г). Ред. коллегия: И. М. Виноградов (глав ред) [и др.] - М., «Советская Энциклопедия», 1977, 1152 стб. с илл.