О

F-область(F-region)
- для данных вершины p и нумерации F такой, что F(p) = i, множество вершин, из которых достижима вершина p в подграфе, порожденном вершинами с F-номерами от i до n = |G|. Наиболее часто это понятие используется для N-нумерации.
Литература:[Касьянов], [Евстигнеев-Касьянов]

Область планарного графа - то же, что и Грань.

Область связности(Region of connectivity)
- множество вершин компоненты связности графа. Для гиперграфа класс эквивалентности отношения связанности.
Литература:[Лекции]

Обратная дуга(Reverse arc, reverse fonds)
- 1. Дуга в цепи, ориентированная против направления движения по цепи. 2. При поиске в глубину дуга, замыкающая контур. 3. См. глубинное остовное дерево}
Литература:[Кристофидес], [Евстигнеев], [Касьянов]

Обратная нумерация - то же, что и N-нумерация.

Обратный орграф(Reverse (converse) digraph)
- орграф, получаемый из исходного заменой всех дуг противоположно ориентированными дугами.
Литература:[Харари]

Обхват(Girth)
- наименьшая длина цикла в графе. Для графа без циклов обхват равен или [infinity], или 0, или неопределен в зависимости от контекста.
Литература:[Лекции]

Обход графа в глубину - то же, что и Поиск в глубину.

Обход графа в ширину - то же, что и Поиск в ширину.

Общий граф(General graph)
- граф, в котором допускаются и кратные ребра, и кратные петли.
См.также мультиграф, псевдограф.
Литература:[Харари-Палмер]

Обыкновенный граф - см. Граф.

Объединение графов(Graphs union)
- операция, которая ставит в соответствие графам F и G граф H с множеством вершин V(H) = V(F) [cup] V(G) и множество ребер E(H) = E(F) [cup] E(G). В этой ситуации пишут H = F [cup] G. Объединение называется дизъюнктным, если V(F) [cap] V(G) = [zero].
Другое название - наложение.
Литература:[Лекции]

Обязательный предшественник(Dominator)
- для некоторой вершины a такая вершина b, что b принадлежит каждому пути
из входа управляющего графа в a.
Другое название - доминатор.
Литература:[Касьянов], [Евстигнеев-Касьянов], [Ахо-Хопкрофт-Ульман]

Обязательный преемник(Postdominator)
- для некоторой вершины a такая вершина b, что b принадлежит каждому пути из a в выход управляющего графа.
Другое название - постдоминатор.
Литература:[Касьянов], [Евстигнеев-Касьянов], [Ахо-Хопкрофт-Ульман]

Ограничение графа(Restriction of a graph)
- для данного графа G частичный граф G|T, порожденный подмножеством T множества ребер графа G.
Литература:[Свами-Тхуласираман]

Г-ограниченный граф(Г-restricted graph)
- граф G = (X,Г), для которого существует такое m, что |Г x| [leq] m для всех x [include] X.
Литература:[Берж]

Одновходовая зона(Single-entry zone)
- зона с единственной входной вершиной. Для сводимого уграфа каждая зона должна быть одновходовой.
Литература:[Касьянов], [Евстигнеев]

Однозначно раскрашиваемый граф(Uniquely coloured graph)
- граф с хроматическим числом \chi(G) = k, у которого каждая k-раскраска порождает одно и то же разбиение множества вершин на одноцветные классы.
Литература:[Харари]

Однородный граф - то же, что и Регулярный граф.

h-однородный гиперграф - то же, что и h-униформный гиперграф.

Односторонне-бесконечный маршрут(One-way infinite sequence)
- маршрут, имеющий либо только начальную, либо только конечную вершину.
Литература:[Оре]

Односторонне связный орграф(Unilaterally connected digraph)
- орграф, в котором для любой пары вершин по меньшей мере одна достижима из другой.
Другое название - односторонний орграф.
Литература:[Лекции]

Односторонний орграф - то же, что и Односторонне связный орграф.

Односторонняя компонента(Unilaterally connected component)
- максимальный односторонне связный подграф.
Литература:[Харари]

Односторонняя связность(Unilaterally connectivity)
- отношение R, определенное на множестве вершин орграфа и такое, что vRw для любых двух вершин v и w, если по крайней мере одна из них достижима из другой.
Литература:[Харари]

Одноцветный класс(Monochromatic class (set))
- в правильной раскраске множество вершин, окрашенных в один цвет.
Литература:[Харари]

Одноциклический граф(Unicyclic graph)
- связный граф, имеющий в точности один цикл.
Другое название - унициклический граф.
Литература:[Харари]

Окрестность вершины(Neighbourhood of a vertex)
- (1) Множество N(v) всех вершин графа G, смежных с вершиной v. (2) Подграф (индуцированный) G[N(v)] на множестве вершин N(v).
Литература:[Харари], [Зыков]

Окружение вершины(Environment of a vertex)
- (1) то же, что и Окрестность вершины. (2) Подграф (индуцированный) G[N(v) [cup] {v}] на множестве вершин N(v) [cup] {v}.
Литература:[Харари], [Зыков]

Окружение графа(Circumference of a graph)
- Длина самого длинного простого цикла в графе.
Другое название - окружность графа.
Литература:[Харари]

Опора - то же, что и Вершинное покрытие.

Оптимальная нумерация(Optimal numbering)
- нумерация вершин, минимизирующая значение некоторого функционала, заданного на графе.
См. укладка.
Литература:[Евстигнеев]

Оптимальная по длине укладка - см. Укладка.

Оптимальная по ширине укладка - см. Укладка.

Орграф - то же, что и Ориентированный граф.

Орграф ациклический - то же, что и Бесконтурный орграф.

Орграф бесконтурный - см. Бесконтурный орграф.

Орграф вершинно-симметрический - см. Вершинно-симметрический орграф.

Орграф гамильтонов - см. Гамильтонов орграф.

Орграф контрафункциональный(Contrafunctional graph)
- орграф, двойственный к функциональному.
Литература:[Харари]

Орграф несвязный - см. Несвязный орграф.

Орграф обратный - см. Обратный орграф.

Орграф односторонне связный - см. Односторонне связный орграф.

Орграф односторонний - то же, что и Односторонне связный орграф.

Орграф полный - см. Полный орграф.

Орграф примитивный - см. Примитивный орграф.

Орграф реберный - см. Реберный орграф.

Орграф самообратный - см. Самообратный орграф.

Орграф связный - то же, что и Слабо связный орграф.

Орграф сильно связный - см. Сильно связный орграф.

Орграф симметричный - см. Симметричный орграф.

Орграф слабо связный - см. Слабо связный орграф.

Орграф строго односторонний - см. Строго односторонний орграф.

Орграф строго слабый - см. Строго слабый орграф.

Орграф транзитивный - см. Транзитивный орграф.

Орграф функциональный - см. Функциональный орграф.

Орграф эйлеров - см. Эйлеров орграф.

Ордерево - то же, что и Ориентированное дерево.

Ориентация графа(Orientation of a graph)
- преобразование неориентированного графа в ориентированный путем превращения каждого ребра в дугу произвольной ориентации.
Литература:[Лекции]

Ориентированная цепь - то же, что и Путь.

Ориентированно-циклически замкнутый граф(Circuit closed graph)
- подграф G(L) орграфа G такой, что если простой контур C имеет общую вершину с G(L), то весь контур C принадлежит G(L).
Литература:[Оре]

Ориентированно-циклически-реберно связанные вершины(Cyclic edge connected vertices)
- вершины v и w такие, что в орграфе найдется последовательность простых контуров C[_1] , ... , C[_k], обладающая следующими свойствами: v принадлежит C[_1], w принадлежит C[_k] и любая пара соседних контуров C[_i] и C[_i+1] имеет хотя бы одну общую вершину.
Литература:[Оре]

Ориентированно-циклическое ребро(Cyclic edge)
- дуга, принадлежащая какому-нибудь контуру.
Литература:[Оре]

Ориентированное дерево(Directed tree)
- корневой орграф, у которого каждая вершина достижима из корня и основание его - дерево.
Литература:[Лекции]

Ориентированное ребро - то же, что и Дуга.

Ориентированный граф(Directed graph)
- пара множеств (V,A), где V - конечное множеств вершин, A - множество дуг (ориентированных ребер), A [subseteq] V[^2].
Литература:[Лекции]

Ориентированный лес(Directed forest)
- лес, каждая компонента связности которого есть ордерево.
Литература:[Ахо-Хопкрофт-Ульман]

Ориентированный маршрут(Directed sequence)
- такая последовательность S = (v[_0] , e[_1] , v[_1] , e[_2] , ... , e[_n] , v[_n]) его чередующихся вершин v[_i] и дуг e[_j], что e[_i] = (v[_i-1] , v[_i]), 1 [leq] i [leq] n. Такой маршрут называется (v[_0] , v[_n])-маршрутом. Вершины v[_0] и v[_n] называются крайними, а остальные - промежуточными или внутренними.
Литература:[Лекции], [Оре]

Ориентированный мультиграф(Directed multigraph)
- орграф, в котором допускаются кратные дуги.
Литература:[Лекции], [Касьянов]

Ориентированный цикл - то же, что и Контур.

Ориентируемый граф(Directable graph)
- граф, у которого каждому ребру может быть приписана ориентация такая, что полученный орграф будет сильносвязным.
Литература:[Уилсон]

Основание орграфа(Bases of a digraph)
- мультиграф, получаемый из орграфа снятием ориентации с дуг.
Литература:[Лекции], [Уилсон]

Остов - то же, что и Каркас.

Остовное дерево - то же, что и Каркас.

Остовный маршрут(Spanning sequence)
- маршрут, содержащий все вершины орграфа.
Литература:[Лекции]

Остовный подграф - то же, что и Суграф.

Отделяющее множество вершин - то же, что и Сечение.

Отец вершины ордерева(Father of a vertex)
- для вершины w такая вершина v, что (v,w) есть дуга ордерева.
Литература:[Лекции]

Отклоненность вершины - то же, что и Эксцентриситет.

Открытый маршрут(Open sequence)
- маршрут, у которого концевые вершины различны; в противном случае он - замкнутый.
Литература:[Свами-Тхуласираман]

Отношение бинарное - см. Бинарное отношение.

Отношение достижимости(Reachibility relation)
- отношение R такое, что vRw тогда и только тогда, когда в орграфе существует путь из v в w.
Литература:[Оре]

Отношение строгого частичного упорядочения(Strict partial order relation)
- антирефлексивное, антисимметричное (если a < ; b и b < ; a, то a=b) и транзитивное (если a < ; b и b < ; c, то a < ; c) отношение.
Литература:[Оре]

Отношение упорядочения(Order relation)
- отношение частичного упорядочения, удовлетворяющее дополнительному условию: для любой пары элементов a и b выполняется одно из соотношений a [leq] b или b [leq] a.
Литература:[Оре]

Отношение частичного упорядочения(Partial order relation)
- рефлексивное (a [leq] a), антисимметричное (из a [leq] b и b [leq] a следует a = b) и транзитивное (если a [leq] b и b [leq] c, то a [leq] c) отношение.
Литература:[Оре]

Отношение эквивалентности(Equivalence relation)
- рефлексивное, симметричное и транзитивное отношение.
Литература:[Оре]

Отождествление вершин - то же, что и Слияние вершин.