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

граф, каждому ребру к-рого приписана ориентация. Г. о. Gзадается множеством вершин Vи набором Еупорядоченных пар вершин, наз. дугами. Говорят, что дуга исходит из вершины и входит в вершину . Число дуг, исходящих из , наз. полустепенью исхода вершины , а число дуг, входящих в v, наз. полустепенью захода вершины и. Чередующаяся последовательность вершин и дуг ,

в к-рой

наз. маршрутом (ориентированным). Маршрут наз. замкнутым, если его первая и последняя вершины совпадают. Путь - это маршрут, в к-ром все вершины различны. Контур - это нетривиальный (содержащий хотя бы одну дугу) замкнутый маршрут, у к-рого все вершины различны, кроме первой и последней. Если существует путь из вершины ив вершину v, то говорят, что vдостижима из u.

Г. о. G с нумерованными вершинами и дугами можно задать матрицей инцидентности, т. е. матрицей размера , в к-рой

Матрицей смежности A(G).вершин Г. о. G наз. матрица размера , в к-рой элемент равен числу дуг, идущих из в .

по строкам матрицы A(G).равны полустепеням исхода вершин Г. о. G, а суммы элементов по столбцам - полустепеням захода. Элемент матрицы (т. е. k-ii степени матрицы смежности графа G).равен числу маршрутов длины k, идущих из в .

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

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

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