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


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

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


Математическая энциклопедия. — М.: Советская энциклопедия. . 1977—1985.

Смотреть что такое "ГРАФ ОРИЕНТИРОВАННЫЙ" в других словарях:

  • ориентированный ациклический граф — Ориентированный граф без циклов, петель, кратных дуг. [http://www.morepc.ru/dict/] Тематики информационные технологии в целом EN DAGdirected acyclic graph …   Справочник технического переводчика

  • Граф (математика) — У этого термина существуют и другие значения, см. Граф (значения). Неориентированный граф с шестью вершинами и семью рёбрами В математической теории графов и информатике граф  это совокупность непустого множества вершин и множества пар… …   Википедия

  • Граф (теория графов) — Неориентированный граф с шестью вершинами и семью рёбрами В математической теории графов и информатике граф  это совокупность объектов со связями между ними. Объекты представляются как вершины, или узлы графа, а связи  как дуги, или рёбра. Для… …   Википедия

  • Ориентированный (направленный) граф — (digraph, orgraph  ) – граф, каждая пара точек которого упорядочена, то есть соединяющее их ребро имеет начало и конец (тогда оно называется дугой) …   Экономико-математический словарь

  • ориентированный (направленный) граф — Граф, каждая пара точек которого упорядочена, то есть соединяющее их ребро имеет начало и конец (тогда оно называется дугой) [http://slovar lopatnikov.ru/] Тематики экономика EN digraphorgraph …   Справочник технического переводчика

  • ориентированный граф — — [http://www.iks media.ru/glossary/index.html?glossid=2400324] Тематики электросвязь, основные понятия EN directed graph …   Справочник технического переводчика

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

  • Граф ожидания — (или граф ожидания транзакций)  инструмент, используемый при разработке СУБД и многопоточных систем и используемый, в частности, для определения ситуации взаимной блокировки (deadlock). Фактически, граф ожидания транзакций представляет собой …   Википедия

  • Ориентированный граф — (кратко орграф)  (мульти) граф, рёбрам которого присвоено направление. Направленные рёбра именуются также дугами, а в некоторых источниках (Оре) и просто рёбрами …   Википедия

  • Граф-схема алгоритма — Ждущая вершина алгоритма Граф схема алгоритма (ГСА) конечный связный ориентированный граф , вершины которого соответствуют операторам, а дуги …   Википедия

Книги

Другие книги по запросу «ГРАФ ОРИЕНТИРОВАННЫЙ» >>


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.