Граф Ориентированный

граф, каждому ребру к-рого приписана ориентация. Г. О. 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. А. А. Сапоженко.