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

граф, каждому ребру к-рого приписана ориентация. Г. о. Gзадается множеством вершин Vи набором Еупорядоченных пар вершин, наз. дугами. Говорят, что дуга [img: http://localhost:8080/file/010428-261.jpg] исходит из вершины [img: http://localhost:8080/file/010428-262.jpg] и входит в вершину [img: http://localhost:8080/file/010428-263.jpg]. Число дуг, исходящих из [img: http://localhost:8080/file/010428-264.jpg], наз. полустепенью исхода вершины [img: http://localhost:8080/file/010428-265.jpg], а число дуг, входящих в v, наз. полустепенью захода вершины и. Чередующаяся последовательность вершин и дуг [img: http://localhost:8080/file/010428-266.jpg], [img: http://localhost:8080/file/010428-267.jpg] в к-рой [img: http://localhost:8080/file/010428-268.jpg] наз. маршрутом (ориентированным). Маршрут наз. замкнутым, если его первая и последняя вершины совпадают. Путь - это маршрут, в к-ром все вершины различны. Контур - это нетривиальный (содержащий хотя бы одну дугу) замкнутый маршрут, у к-рого все вершины различны, кроме первой и последней. Если существует путь из вершины ив вершину v, то говорят, что vдостижима из u. Г. о. G с нумерованными вершинами [img: http://localhost:8080/file/010428-269.jpg] и дугами [img: http://localhost:8080/file/010428-270.jpg] можно задать матрицей инцидентности, т. е. матрицей [img: http://localhost:8080/file/010428-271.jpg] размера [img: http://localhost:8080/file/010428-272.jpg], в к-рой [img: http://localhost:8080/file/010428-273.jpg] Матрицей смежности A(G).вершин Г. о. G наз. матрица [img: http://localhost:8080/file/010428-274.jpg] размера [img: http://localhost:8080/file/010428-275.jpg], в к-рой элемент [img: http://localhost:8080/file/010428-276.jpg] равен числу дуг, идущих из [img: http://localhost:8080/file/010428-277.jpg] в [img: http://localhost:8080/file/010428-278.jpg]. по строкам матрицы A(G).равны полустепеням исхода вершин Г. о. G, а суммы элементов по столбцам - полустепеням захода. Элемент [img: http://localhost:8080/file/010428-279.jpg] матрицы [img: http://localhost:8080/file/010428-280.jpg] (т. е. k-ii степени матрицы смежности графа G).равен числу маршрутов длины k, идущих из [img: http://localhost:8080/file/010428-281.jpg] в [img: http://localhost:8080/file/010428-282.jpg]. В Г. о. можно определить несколько типов связности (см. Графа связность). Т. о. наз. сильносвязным, или сильным, если любые две его вершины взаимно достижимы; односторонне связным, если для любых двух его вершин по крайней мере одна достижима из другой; слабосвязным, или слабым, если любые две его вершины соединены цепью в графе, полученном из исходного Г. о. заменой каждой дуги (неориентированным) ребром. Г. о. используются: в теории вероятностей для представления Маркова цепей;в теории игр при описании множества игровых ситуаций и результатов состязаний; в математич. экономике при решении транспортных задач; в теории автоматов для задания диаграмм переходов и т. п. В самой теории графов при решении нек-рых задач относительно неориентированных графов иногда вводят ориентацию, сводя исходную задачу к задаче над Г. о. Основное отличие Г. о. от неориентированного графа проявляется при определении таких понятий, как путь, связность, достижимость, расстояние н др. Наиболее интересными типами Г. о. являются турниры, транзитивные графы, графы частичных порядков, растущие деревья, графы однозначных отображений, бесконтурные графы.