Р

Равенство Кемпе(Kempe's equality)
- равенство [Formula-13]( 6- i ) n[_i] = 12, где n[_i] есть число вершин степени i; равенство верно для плоских триангуляций.
Литература:[Зыков]

Радиально-критический граф(Radially critical graph)
- связный граф, у которого добавление любого ребра приводит к уменьшению радиуса графа.
Литература:[Зыков]

Радиус графа(Radius of a graph)
- минимальный из эксцентриситетов вершин связного графа; вершина, на которой достигается этот минимум называется центральной вершиной.
Литература:[Лекции]

Радиус абсолютный внешний - см. Абсолютный внешний радиус.

Радиус абсолютный внутренний - см. Абсолютный внутренний радиус.

Радиус внешний - см. Внешний радиус.

Радиус внутренний - см. Внутренний радиус.

Разбивающий треугольник(Separating triangle)
- простой цикл длины 3 в триангуляции, не являющийся краем никакой ее грани.
Литература:[Зыков]

Разбиение графа(Partition of a graph)
- представление числа 2q в виде суммы степеней вершин графа.
Литература:[Харари]

Разбиение числа графическое - см. Графическое разбиение числа.

Разборный граф(Collapsible graph)
- уграф G, который может быть преобразован в тривиальный итеративным применением следующих двух преобразований: T1 - удаление петли и T2 - слияние двух вершин. Преобразование T1 определено для любой вершины p уграфа G и состоит в удалении дуги (p,p) из G. Преобразование T2 определено только для такой пары вершин p и q , что p - единственный предшественник q; оно удаляет p и (p,q) из G и заменяет в нем дуги, заходящие в p, на дуги, заходящие в q.
Литература:[Касьянов],[Евстигнеев-Касьянов]

Разделимый граф(Separable graph)
- граф, имеющий точку сочленения.
Литература:[Татт]

Разделяющая вершина - то же, что и Точка сочленения.

Разделяющее множество сочленения - то же, что и Сечение.

Разложимый гамак - см. Гамак.

Разметка графа(Graph labeling)
- приписывание меток - слов из некоторого алфавита вершинам графа; в отличие от нумерации вершин одну и ту же метку могут иметь несколько вершин.
См. Раскраска.
Литература:[Евстигнеев], [Касьянов]

Разность графов(Difference of graphs)
- граф G[_1] - G[_2], получающийся из G[_1] удалением элементов, соответствующих графу G[_2].
Литература:[Алгоритмы]

Разрез(Cut-set)
- множество ребер связного графа, удаление которых приводит к несвязному графу.
Литература:[Харари]

Разрез простой - см. Простой разрез.

Разрезающая вершина(Cut-vertex (cutting vertex))
- вершина x графа G такая, что после ее удаления множество V(G) \ {x} разбивается на непересекающиеся непустые подмножества V' и V'', между которыми нет ребер графа G.
См. также точка сочленения.
Литература:[Татт], [Оре]

Разумная нумерация(Reasonable numbering)
- такая нумерация F уграфа G, что справедливы два свойства:
(1) F(p)[leq] F(q) для любых вершин p и q таких, что p обязательно предшествует q;
(2) если G - аранжируемый уграф, то F является аранжировкой.
Литература:[Касьянов], [Евстигнеев], [Евстигнеев-Касьянов].

Ранг графа(Rank of a graph)
- ранг матрицы смежности графа.
Литература:[Лекции]

Ранг графа коциклический - см. Коцикломатический ранг графа.

Ранг графа циклический - то же, что и Цикломатическое число графа.

Ранг группы графов(Rank of a graph group)
- число орбит фиксатора вершины в транзитивной группе Aut(G).
Литература:[Алгоритмы]

Ранговая функция(Rank function)
- функция r : 2[^S] [RightLeftArrow] Z, определенная для любого подмножества элементов матроида M = (S, [ii]) во множество неотрицательных целых чисел r(A) = max {|X| / X [subseteq] A, X [include] [ii]}.
Литература:[Welsh]

Раскраска(Colouring)
- для некоторого графа G и натурального числа k функция вида f: V(G) [rarr] {1,2,...,k}, отображающая множество вершин в множество цветов. Иногда, чтобы подчеркнуть мощность множества цветов, говорят о вершинной k-раскраске или просто о k-раскраске. Интерес представляют только те раскраски, при которых смежные вершины окрашиваются в различные цвета. Такие раскраски называются правильными. Поскольку функция f не обязательно сюръективна, то при k-раскраске фактически может быть использовано менее k цветов. Таким образом, правильную k-раскраску графа G можно рассматривать как разбиение множества вершин на не более чем k непустых классов, каждый из которых является независимым множеством.
Литература:[Лекции]

Раскраска полная - см. Полная раскраска.

Раскраска последовательная - см. Последовательная раскраска.

Раскраска правильная - см. Правильная раскраска.

k-раскраска реберная - см. Реберная k-раскраска.

Раскрашенный граф(Colored graph)
- граф с заданным на множестве его вершин отношением эквивалентности таким, что любые смежные вершины не эквивалентны.
Литература:[Харари-Палмер]

k-раскрашенный граф(k-colored graph)
- раскрашенный граф с k классами эквивалентности.
Литература:[Харари-Палмер]

Раскрашенный мультиграф(Colored multigraph)
- мультиграф с заданным на множестве его ребер отношением эквивалентности таким, что любые неинцидентные ребра эквивалентны.
Литература:[Харари-Палмер]

k-раскрашиваемая карта(k-colourable map)
- карта, грани которой можно раскрасить k цветами так, чтобы никакие две смежные грани (т.е. грани с общими ребрами на границе) не были одного цвета.
Литература:[Уилсон]

k-раскрашиваемый гиперграф(k-colourable hypergraph)
- гиперграф, для которого существует правильная расраска в k цветов.
Литература:[Лекции]

k-раскрашиваемый граф(k-colourable graph)
- граф, для которого существует правильная k-раскраска.
Литература:[Лекции]

Рассечение(Dissection)
- совокупность простых путей или простых контуров такая, что никакие два пути рассечения не имеют общих вершин и каждая вершина графа принадлежит одному из путей рассечения.
Литература:[Берж]

Расстояние между вершинами(Distance between two vertieces)
- длина кратчайшей цепи (в орграфе пути), соединяющей заданные вершины; если такой цепи (пути) не существует, расстояние полагается равным [infinity].
Литература:[Лекции]

Растущее дерево(Growing tree)
- ориентированное дерево, все дуги которого ориентированы от корня.
Литература:[Евстигнеев-Касьянов], [Майника]

Расщепление вершины(Vertex splitting)
- 1) преобразование графа, заключающееся в замене вершины v вершинами v' и v'', соединенными ребром (v',v''), причем вершины, смежные с v, распределяются между новыми вершинами каким-то способом. При расщеплении вершины в орграфе последняя заменяется вершинами v' и v'', соединенными дугой (v',v''), причем дуги, заходившие в v, теперь заходят в v', а дуги, исходившие из v, теперь исходят из v'';
2) преобразование уграфа, при котором некоторая вершина p, не являющаяся ни начальной, ни конечной и не имеющая петли, заменяется на r экземпляров по одному для каждой из r заходящих в p дуг.
Литература:[Лекции],[Евстигнеев-Касьянов],[Касьянов]

Расщепляемая последовательность(Split sequence)
- графическая последовательность, для которой существует расщепляемая реализация, т.е. существует такой расщепляемый граф, для которого данная последовательность является графической.
Литература:[Лекции]

Расщепляемый граф(Split graph)
- граф, для которого существует разбиение множества его вершин на клику и независимое множество.
См. также Пороговый граф.
Литература:[Лекции]

Реализация гиперграфа(Realization of hypergraph)
- для гиперграфа H = (V,[ee]) граф G, удовлетворяющий следующим условиям:
(1) V(G) = V(H);
(2) любое ребро графа G содержится в некотором ребре гиперграфа H;
(3) для любого ребра e [include] [ee] порожденный подграф G(e) является связным.
Литература:[Лекции]

Реберная группа графа(Line (edge) group of a graph)
- группа подстановок, действующая на множестве ребер графа.
Литература:[Харари]

Реберная k-раскраска(Edge k-colouring)
- функция [phi], ставящая в соответствие каждому ребру e графа число [phi](e) из множества {1,2,...,k};
1)если [phi] - реберная раскраска и [phi](e) = c, то говорят, что ребро e окрашено в цвет c;
2)реберная раскраска [phi] является правильной, если инцидентные одной вершине ребра получают разные цвета.
Литература:[Лекции]

Реберная реконструируемость(Edge reconstructibility)
- восстановление структуры графа по набору его частичных графов вида G \ e для всех e [include] E(G).
См. также Реконструкция графа; Гипотеза Харари.
Литература:[Лекции]

Реберная связность(Edge connectivity)
- наименьшее число ребер, удаление которых приводит к несвязному или тривиальному графу.
Реберная связность несвязного графа равна 0, а реберная связность графа, имеющего мост, равна 1.
Литература:[Харари]

Реберно изоморфные графы(Edge isomorphic graphs)
- два графа G и G' реберно изоморфны, если существует такое взаимно однозначное соответствие между их ребрами, что если e[_1] и e[_2] - смежные ребра в G, то соответствующие ребра e'[_1] и e'[_2] смежны в G', и наоборот. Ясно, что любой обычный (вершинный) изоморфизм между G и G' определяет также реберный изоморфизм, но обратное, вообще говоря, не имеет места.
Литература:[Оре]

Реберно критический граф(Edge critical graph)
- пусть граф G обладает свойством P; G называется реберно критическим, если граф G \ e не обладает свойством P для любого ребра e.
Литература:[Харари]

Реберно раскрашиваемый граф(Edge colourable graph)
- граф, допускающий правильную раскраску ребер.
Литература:[Харари]

Реберно k-раскрашиваемый граф(Edge k-colourable graph)
- граф, допускающий правильную реберную k-раскраску.
Литература:[Лекции]

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

k-реберно связный граф(k-edge connected graph)
- граф, у которого мощность любого разреза не меньше k.
Литература:[Оре]

Реберно-симметрический граф(Line-symmetric graph, edge symmetric graph)
- граф, у которого любая пара ребер подобна.
Литература:[Харари]

Реберно-хроматическое число(Line-chromatic number, edge chromatic number})
- для данного графа G хроматическое число его реберного графа L(G).
Литература:[Харари-Палмер]

Реберное покрытие(Line-covering, edge covering)
- такое подмножество E' ребер графа, что каждая вершина в графе инцидентна по крайней мере одному ребру из E'. Р.п. называется минимальным, если в нем не содержатся покрытия с меньшим числом ребер, и наименьшим, если число ребер в нем наименьшее среди всех покрытий. Мощность наименьшего Р.п. называется числом реберного покрытия и обозначается через [beta][_1](G).
Литература:[Лекции]

Реберное хроматическое число - см. Хроматический индекс.

Реберное ядро(Edge core)
- подграф графа G, порожденный объединением таких независимых множеств Y ребер (если они есть),
что |Y| = [alpha][_0] (G), где [alpha][_0] (G) - число вершинного покрытия.
Литература:[Харари]

Реберный граф(Line (edge) graph)
- для заданного графа G граф L(G), вершинами которого служат ребра графа G и две вершины смежны в L(G) тогда и только тогда, когда соответствующие ребра смежны в G.
Литература:[Лекции]

Реберный граф гиперграфа(Line graph of a hypergraph)
- для гиперграфа H = (V,[ee]) такой граф L(H) = ([ee], E), множество вершин которого совпадает с множеством ребер [ee] гиперграфа H, при этом две вершины графа L(H) смежны тогда и только тогда, когда смежны соответствующие им ребра гиперграфа H. Таким образом, L(H) - граф пересечений ребер гиперграфа H.
Литература:[Лекции]

Реберный орграф(Line digraph)
- граф L(D), множество вершин которого есть множество дуг орграфа D, и две его вершины x и y смежны тогда и только тогда, когда дуги x и y порождают маршрут в орграфе D.
Литература:[Харари]

Реберный цветной класс(Edge monochromatic graph)
- множество всех ребер графа, окрашенных в фиксированный цвет.
Литература:[Лекции]

Ребра кратные - см. Кратные ребра.

Ребра независимые(Independent edges)
- множество попарно несмежных ребер.
Литература:[Харари]

Ребра подобные - см. Подобные ребра.

Ребра смежные - см. Смежные ребра.

Ребро - см. Граф.

Ребро висячее - см. Висячее ребро.

Ребро гиперграфа - см. Гиперграф.

Ребро, инцидентное вершине(Line (edge) incident with a vertex)
- ребро, для которого данная вершина является концевой.
Литература:[Харари]

Ребро касания - см. Поиск в глубину.

Ребро критическое - см. Критическое ребро.

Ребро подразбитое - см. Подразбитое ребро.

Ребро симметричное - см. Симметричное ребро.

Регрессивно конечный граф(Regressive finite graph)
- орграф (X,Г) такой, что соответствующий орграф (X[^-1]) прогрессивно конечный.
Литература:[Берж]

Регрессивно ограниченный граф(Regressive bounded graph)
- орграф (X,Г) такой, что соответствующий орграф (X[^-1]) прогрессивно ограниченный.
Литература:[Берж]

Регуляризуемый граф(Regularizable graph)
- уграф G, для которого существует такая последовательность уграфов

G[_0]=G,G[_1], ... ,G[_l],
что G[_l] - тривиальный уграф, а каждый G[_i], i > 0, является фактор уграфом уграфа G[_i-1] относительно некоторого множество попарно непересекающихся интервалов.
Справедлива теорема Касьянова--Хехта--Ульмана:
Уграф регуляризуем тогда и только тогда, когда справедливо любое из следующих свойств: G - сводим, G - аранжируем, G - разборный, G - одновходовый, G не содержит запрещенного подграфа.
Литература:[Касьянов],[Евстигнеев-Касьянов]

Регулярная группа графа(Regular group of a graph)
- транзитивная по вершинам полурегулярная группа графа.
Литература:[Алгоритмы]

Регулярный граф(Regular graph)
- граф, у которого степени всех вершин равны между собой; степень его вершин называется степенью регулярного графа. Все полные графы регулярны; регулярны также графы платоновых тел. Регулярным графом степени n является n-мерный куб.
Другое название - Однородный граф.
Литература:[Лекции]

Регулярный степени 0 граф - то же, что и Пустой граф.

Редукция транзитивная - см. Транзитивная редукция орграфа.

Реконструируемый граф(Reconstructible graph)
- граф, изоморфный каждой своей реконструкции.
Cм. также Гипотеза реконструируемости.
Литература:[Лекции]

Реконструкция графа(Reconstructing of graph)
- для данного графа G такой граф H, у которого набор подграфов вида H \ v (H \ e) для всех v [include] V(H)
(для всех e [include] E(H)) равен соответствующему набору для графа G.
Литература:[Лекции]

Рефлексивно-транзитивное замыкание графа(Reflexive-transitive closure of a graph)
- псевдограф, получаемый из транзитивного замыкания орграфа добавлением к каждой вершине петли.
Литература:[Оре]

Решетчатый d-мерный граф(d-dimensional lattice)
- граф d-мерной целочисленной решетки; представляет собой декартово произведение d простых цепей.
Литература:[Харари-Палмер]

Род графа(Genus of a graph)
- наименьшее число [gamma](G) ручек, которые необходимо добавить к сфере, чтобы граф G можно было уложить на полученной таким образом поверхности. Очевидно, что [gamma](G) = 0 тогда и только тогда, когда G планарный, и [gamma](G) = 1 тогда и только тогда, когда G тороидальный.
Литература:[Лекции]