Г

Гамак(Hammock)
- альт, множество конечных вершин которого либо пусто, либо состоит из единственной вершины, являющейся преемником каждой выходной вершины альта и не являющейся предшественником его начальной вершины. Гамак называется разложимым, если его можно представить как объединение двух непересекающихся гамаков, и неразложимым (или простым) в противном случае. Максимальный разложимый гамак называется составным. См. также Иерархия вложенных альтов.
Литература:[Евстигнеев], [Евстигнеев-Касьянов], [Касьянов]

Гамачное представление(Hammock presentation)
- представление уграфа в виде иерархии вложенных простых и составных гамаков.
Литература:[Евстигнеев-Касьянов], [Касьянов]

Гамильтонов граф(Hamiltonian graph)
- граф, содержащий гамильтонов цикл или гамильтонову цепь, соединяющую некоторую пару вершин. К настоящему времени известны лишь достаточные условия гамильтоновости графов, принадлежащие В.Хваталу, О.Оре, Г.Дираку, Х.Уитни и др. Примерами гамильтоновых графов служат полные графы, графы каркасов, графы правильных многогранников. Слово "гамильтонов" в этом и других терминах связано с именем ирландского математика У.Гамильтона, который в 1859 г. предложил головоломку "Кругосветное путешествие"где требовалось обойти по ребрам все вершины додекаэдра.
Литература:[Харари], [Зыков], [Лекции]

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

Гамильтонов орграф(Hamiltonian directed graph)
- орграф, содержащий гамильтонов контур или гамильтонов путь, соединяющий некоторую пару вершин. К настоящему времени известны лишь достаточные условия гамильтоновости орграфа.
Литература:[Зыков], [Лекции]

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

Гамильтонов центр(Hamiltonian center)
- 1. Вершина в графе, которая связана с любой другой вершиной гамильтоновой цепью. 2. Вершина в орграфе, из которой выходит гамильтонов путь к каждой из оставшихся вершин.
Литература:[Оре]

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

Гамильтонова линия - то же, что и гамильтонов цикл.

Гамильтонова цепь(Hamiltonian chain)
- цепь в графе, проходящая через каждую вершину в точности один раз.
Литература:[Зыков], [Лекции]

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

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

Геодезическая цепь(Geodetic chain)
- кратчайшая простая (v,w)-цепь. См. Кратчайший путь.
Литература:[Харари]

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

Геометрически двойственный граф - см. Двойственный граф.

Гиперграф(Hypergraph)
- пара (V,[ee]), где V - непустое множество объектов некоторой природы, называемых вершинами гиперграфа, а [ee] - семейство непустых (необязательно различных) подмножеств множества V, называемых ребрами гиперграфа. Ясно, что Г. является таким обобщением понятия графа, когда ребрами могут быть не только двухэлементные, но и любые подмножества вершин.
Литература:[Лекции]

Гиперграф абсолютный - см. Абсолютный гиперграф.

Гиперграф бихроматический - см. Бихроматический гиперграф.

Гиперграф двойственный - см. Двойственный гиперграф.

Гиперграф нормальный - см. ?????Нормальный гиперграф.

Гиперграф k-однородный - см. h-однородный гиперграф.

Гиперграф k-раскрашиваемый - см. k-раскрашиваемый гиперграф.

Гиперграф сбалансированный - см. Сбалансированный гиперграф.

Гиперграф связный - см. Связный гиперграф.

Гиперграф тотально сбалансированный - см. Тотально сбалансированный гиперграф.

Гиперграф k-униформный - см. h-униформный гиперграф.

Гиперграф k-униформный полный - см. Полный k-униформный гиперграф.

Гиперграф k-хроматический - см. k-хроматический гиперграф.

Гиперграф k-цветной - см. k-цветной гиперграф.

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

Гипотеза Бержа(Conjecture of Berge)
- Граф G является совершенным тогда и только тогда, когда ни он, ни его дополнение [G^~] не содержат порожденных подграфов вида G[_2k+1], k [geq] 2. Эта гипотеза, высказанная в 1962 г. и не доказанная до сих пор (но и не опровергнутая), сыграла большую роль в исследовании совершенных графов.
Литература:[Лекции]

Гипотеза Брэттона(Conjecture of Bratton)
- У всякого сильно связного графа без петель с m дугами и n вершинами диаметр больше или равен [delta](m,n)-1, где [delta](m,n) определяется следующим образом. Пусть q - частное, а r - остаток от деления n-1 на [nu] = m-n+1. Тогда

[Formula-6]
Гипотеза решена М.Гольдбергом в 1966 г. См. Докл. АН СССР, т.170, N4, 1966.
Литература:[Берж]

Гипотеза (вершинной) реконструируемости - см. Гипотеза Келли-Улама.

Гипотеза Келли-Улама(Conjecture of Kelly and Ulam)
- Все графы порядка n > 2 реконструируемы. Иначе говоря, любой граф G = (V,E) с |V| > 2 однозначно восстанавливается по набору подграфов вида G \ v, v [include] V. Справедливость гипотезы, известной с 1945 г., подтверждена для графов с 3 [leq] |V| [leq] 10. Известно также, что если граф G реконстрируем, то дополнительный граф [G^~] также реконструируем. Другие названия - гипотеза (вершинной) реконструируемости, гипотеза Улама.
Литература:[Лекции]

Гипотеза Рамачандрана(Conjecture of Ramachandra)
- вариант гипотезы Келли-Улама для орграфов.
Литература:[Харари], [Лекции]

Гипотеза реберной реконструируемости - см. Гипотеза Харари.

Гипотеза Улама - см. Гипотеза Келли-Улама.

Гипотеза Хадвигера(Conjecture of Hadwiger)
- Каждый связный n-хроматический граф стягиваем к полному n-вершиннику K[_n]. Гипотеза верна для n [leq] 4 (Дирак, 1952). Из нее при n = 5 следует гипотеза четырех красок; обратное было установлено Вагнером.
Литература:[Харари], [Лекции]

Гипотеза Харари(Conjecture of Harary)
- Граф G = (V,E) с |V| > 2 однозначно восстанавливается по набору подграфов вида G \ e, e [include] E. Гипотеза подтверждена для многих классов графов.
Другое название - гипотеза реберной реконструируемости.
Литература:[Лекции]

Гипотеза четырех красок(Graph colouring conjecture)
- Каждый планарный граф 4-раскрашиваем. Первоначальная формулировка гипотезы гласит: любая карта на плоскости или на сфере может быть раскрашена четырьмя красками так, что никакие две смежные страны не были одного и того же цвета. Гипотеза имеет интересную историю, но в ее появлении остается много непонятного. Имеются сообщения, что Мебиус был знаком с этой проблемой в 1840 г., но точно известно лишь то, что о данной проблеме Гутри сообщал де Моргану примерно в 1850 г. Сформулировал гипотезу британский математик А.Кэли в 1879 г. в статье, посвященной проблеме раскраски карт в первом томе Трудов Лондонского географического общества. Первое из многих ошибочных "доказательств" было дано Кемпе в 1879г. Новую фазу в истории гипотезы открыло машинное доказательство Хакена и Апеля, появившееся в 1976г. Это доказательство не было принято математической общественностью и породило новую проблему - проблему методологии и корректности доказательств математических теорем с помощью ЭВМ.
Литература:[Лекции]

Глубина аранжировки(Depth of arrangement)
- наибольшее число обратных дуг (т.е. дуг, номера концов которых не превышают номеров их начал), принадлежащих одному простому пути.
Литература:[Евстигнеев-Касьянов], [Касьянов]

Глубина аранжируемого уграфа(Depth of arrangeable control-flow graph)
- инвариант аранжируемого уграфа, равный глубине его аранжировки.
Литература:[Евстигнеев-Касьянов], [Касьянов]

Глубина вершины(Depth of a vertex)
- длина пути из корня дерева в данную вершину.
Литература:[Ахо-Хопкрофт-Ульман]

Глубина нумерации(Depth of a numbering)
- наибольшее число F-обратных дуг (для заданной нумерации F), принадлежащих одному простому пути.
Другое название - число несоответствия нумерации.
Литература:[Касьянов], [Евстигнеев-Касьянов]

Глубинное остовное дерево(Depth-first spanning tree)
- 1. Оркаркас в виде растущего ордерева, образованный древесными дугами при реализации поиска в глубину в орграфе; корень ордерева совпадает с началом поиска в глубину. Все множество дуг орграфа разбивается относительно его Г.о.д. на четыре класса: древесные - дуги, принадлежащие дереву; обратные - дуги, ведущие от потомков к предкам (возможно, от вершин в себя); прямые - дуги, идущие от предков к потомкам, но не являющиеся древесными; поперечные - дуги, соединяющие вершины, которые не являются ни предками, ни потомками одна другой. 2. Каркас, построенный поиском в глубину в неориентированном графе.
Литература:[Евстигнеев], [Евстигнеев-Касьянов], [Касьянов], [Лекции]

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

Гомеоморфно несводимое дерево(Homeomorphically irreducible tree)
- дерево, не имеющее вершин степени 2.
Литература:[Харари]

Гомеоморфные графы(Homeomorphical graphs)
- графы, получаемые из одного графа с помощью последовательности подразбиений ребер. Например, два простых цикла гомеоморфны.
Литература:[Харари]

Гомоморфизм элементарный(Elementary homomorphism)
- преобразование графа, состоящее в отождествлении двух его несмежных вершин.
Литература:[Харари]

Гомоморфизм графа(Homomorphism of a graph)
- преобразование графа, представляющее последовательность его элементарных гомоморфизмов. Гомоморфизмом является, в частности, каждый изоморфизм. Гомоморфизм может рассматриваться как функция

[phi] : G [rarr] G'
такая, что если вершины u и v смежны в G, то вершины [phi](u) и [phi](v) смежны в G'. Говорят также, что [phi] есть гомоморфизм графа G на граф G'. Граф G' называется гомоморфным образом графа G и обозначается [phi]G.
Литература:[Харари]

Гомоморфный образ графа(Homomorphic image of a graph)
- граф, в который гомоморфно отображается исходный граф.
Литература:[Харари]

Грамматика автоматная - см. Порождающая грамматика.

Грамматика атрибутная - см. Атрибутная грамматика.

Грамматика контекстно-свободная - см. Порождающая грамматика.

Грамматики эквивалентные - см. Порождающая грамматика.

Граница грани(Boundary of a face)
- множество вершин и ребер плоского графа, принадлежащих этой грани. Граница грани представляет собой простой цикл.
Литература:[Лекции]

Граничная вершина фрагмента(Boundary vertex of a fragment)
- вершина фрагмента, среди смежных вершин которой есть вершины, не принадлежащие фрагменту.
Литература:[Евстигнеев-Касьянов]

Граничный оператор(Boundary operator)
- оператор [partial], относящий 1-цепям графа 0-цепи в соответствии со следующими правилами:
а) [partial] - линейный оператор;
б) если x = (u,v), то [partial] x = u + v.
См. также: Кограничный оператор.
Литература:[Харари]

Грань(Face, facet)
- для плоского графа максимальное по включению множество точек плоскости, каждая пара которых может быть соединена жордановой кривой, не пересекающей ребра графа. Тем самым каждая точка плоскости принадлежит хотя бы одной грани плоского графа. Всякий плоский граф имеет одну и притом единственную, неограниченную грань, называемую внешней гранью; остальные грани называются внутренними.
Литература:[Лекции]

Грань внешняя - см. Грань.

Грань внутренняя - см. Грань.

Граф (неориентированный граф)(Graph (undirected graph)
-) 1. Пара (V,E), где V - непустое множество объектов некоторой природы, называемых вершинами графа, а E - подмножество двухэлементных подмножеств множества V, называемых ребрами графа. Множества вершин и ребер графа G обозначают V(G) и E(G), соответственно. Если |V(G)| = n и |E(G)| = m, то говорят о (n,m)-графе G. 2. Пара (V,E), где V - множество вершин графа, а E - множество ребер - есть подмножество множества V[_-^2] / [sim] классов эквивалентности, на которые множество V[_-^2] = {(v,w) | v [neq] w } разбивается отношением эквивалентности:

(v[_1],w[_1]) [sim] (v[_2],w[_2]) [LeftRightDoubleArrow] (v[_1],w[_1]) = (v[_2],w[_2]) или (v[_1],w[_1]) = (w[_2],v[_2])
3. Тройка (V,E,P), где V - множество вершин, E - множество объектов некоторой природы, отличной от природы вершин, называемых ребрами, P - инцидентор, сопоставляющий каждому ребру e [include] E пару граничных вершин v и w из V. 4. Общее название как для неориентированного, так и для ориентированного графов.
Литература:[Лекции]

Граф абстрактный - см. Абстрактный граф.

Граф антисимметрический - см. Антисимметрический граф.

Граф аранжируемый - см. Аранжируемый граф.

Граф асимметрический - см. Асимметрический граф.

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

Граф без сочленений - то же, что и блок.

Граф без циклов(Circuitless graph)
- граф, компоненты связности которого являются деревьями.
    Другое название - лес.
Литература:[Лекции]

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

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

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

Граф бихроматический - см. Бихроматический граф.

Граф блоков(Block graph)
- граф B(G), вершины которого суть блоки графа G и две вершины смежны тогда и только тогда, когда соответствующие им блоки имеют общую точку сочленения. Граф блоков представляет собой разновидность графа пересечений.
Литература:[Харари]

Граф блоков и точек сочленения(Block-cutpoint-graph)
- двудольный граф bc(G), вершинами которого являются блоки B[_i] и точки сочленения c[_j], причем две вершины смежны тогда и только тогда, когда одна соответствует блоку B[_i], а другая - точке сочленения c[_j], принадлежащей этому блоку.
Литература:[Харари]

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

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

Граф k-вершинно-связный - см. k-вершинно-связный граф.

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

Граф взвешенный - см. Взвешенный граф.

Граф внешнепланарный - см. Внешнепланарный граф.

Граф воспроизведения( Reproduction graph)
- бесконтурный орграф, моделирующий связи членов некоторой популяции со своим потомством; множество вершин Г.в. есть множество членов популяции, а две вершины a и b соединены дугой (a,b), если b есть непосредственный потомок a. См. также Граф потомства.
Литература:[Оре]

Граф вполне несвязный - см. Вполне несвязный граф.

Граф вызовов - см. Граф процедур.

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

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

Граф Герца(Graph of Herz)
- для орграфа G бесконтурный орграф, получаемый из G путем стягивания каждой бикомпоненты в отдельную вершину. Другими словами, Г.Г. для графа G есть фактор-граф графа G по семейству бикомпонент. Другое название - граф конденсации.
Литература:[Евстигнеев]

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

Граф двойственный - см. Двойственный граф.

Граф двудольный - см. Двудольный граф.

Граф двумерной целочисленной решетки - см. Граф решетки.

Граф двусторонний - см. Двусторонний граф.

Граф Дезарга(Desargues' graph)
- граф, дополнительный к графу Петерсена.
Литература:[Оре]

Граф додекаэдра - см. Граф многогранника.

Граф k-дольный - см. k-дольный граф.

Граф дополнительный - то же, что и дополнение графа.

Граф звездный - см. Звездный граф.

Граф знаково-помеченный - см. Знаково-помеченный граф.

Граф икосаэдра - см. Граф многогранника.

Граф индуктивный - см. Индуктивный граф.

Граф интервалов(Interval graph)
- граф, изоморфный графу пересечений [omega](F) для семейства F замкнутых интервалов на действительной оси.
Литература:[Харари]

Граф информационный - см. Информационный граф.

Граф зацепленности - см. Граф процедур.

Граф каркасов(Tree graph)
- граф [gg](G), вершины которого суть каркасы графа G и две вершины смежны, если соответствующие каркасы имеют в точности (n-2) общих ребер, где n = |V(G)|. Г.к. любого графа гамильтонов.
Литература:[Кристофидес]

Граф клик(Clique graph)
- граф Q(G) пересечений максимальных клик графа; вершины его соответствуют максимальным кликам и две вершины смежны тогда и только тогда, когда соответствующие клики имеют непустое пересечение.
Литература:[Харари], [Лекции]

Граф конденсации - то же, что и граф Герца.

Граф конечный - см. Конечный граф.

Граф Г-конечный - см. Г-конечный граф.

Граф Г[^-1]-конечный - см. Г[^-1] -конечный граф.

Граф корневой - см. Корневой граф.

Граф критический - см. Критический граф.

Граф куба - см. Граф многогранника.

Граф кубический - см. Кубический граф.

Граф локально конечный - см. Локально конечный граф.

Граф локально ограниченный - см. Локально ограниченный граф.

Граф локально счетный - см. Локально счетный граф.

Граф максимальный сильно сингулярный - см. Максимальный сильно сингулярный граф.

Граф максимальный сингулярный - см. Максимальный сингулярный граф.

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

Граф многогранника(Polytop graph, polyhedron graph)
- плоский граф, получаемый проектированием выпуклого многогранника на поверхность описанной вокруг него сферы и последующей стереографической проекцией полученного изображения на плоскость; полученный плоский граф является связным графом, каждая грань которого ограничена многоугольником. В зависимости от вида многогранника различают граф куба, граф додекаэдра, граф призмы и т.д.
Литература:[Лекции]

Граф многоугольный - см. ?????Многоугольный граф.

Граф нагруженный - см. Помеченный граф.

Граф накрывающий - см. Накрывающий граф.

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

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

Граф непомеченный - то же, что и абстрактный граф.

Граф неразделимый - см. Неразделимый граф.

Граф неразложимый - см. Неразложимый граф.

Граф несводимый - см. Несводимый граф.

Граф несепарабельный - см. Несепарабельный граф.

Граф несовместимости(Incompatibility graph)
- неориентированный граф, определяемый для некоторого множества объектов и набора свойств {P[_i]} следующим образом: вершины суть рассматриваемые объекты и две вершины смежны, если соответствующие объекты обладают хотя бы одним свойством P[_i]. Г.н. используются при решении задач о составлении расписаний, распределения ресурсов, экономии и перераспределении памяти и пр.
Литература:[Евстигнеев], [Ершов], [Касьянов-Поттосин]

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

Граф общий - см. Общий граф.

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

Граф Г-ограниченный - см. Г-ограниченный граф.

Граф однозначно раскрашиваемый - см. Однозначно раскрашиваемый граф.

Граф однородный - см. Однородный граф.

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

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

Граф одноциклический - см. Одноциклический граф.

Граф октаэдра - см. Граф многогранника.

Граф ориентированно-циклически замкнутый - см. Ориентированно-циклически замкнутый граф.

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

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

Граф остовов - то же, что и граф каркасов.

Граф панциклический - см. Панциклический граф.

Граф Паппа(Pappus' graph)
- граф, дополнение которого состоит из трех компонент, являющихся треугольниками.
Литература:[Оре]

Граф пересечений(Intersection graph)
- граф [omega](F), определенный для покрытия F = (S[_1], S[_2], ... , S[_n]) непустого множества S непустыми несовпадающими подмножествами; вершины графа [omega](F) суть подмножества S[_i] и две вершины S[_i] и S[_j] смежны, если S[_i][cap] S[_j] [neq] [zero].
Литература:[Харари], [Лекции]

Граф [alpha]-перестановочный - см. [alpha]-перестановочный граф.

Граф переходов - то же, что и управляющий граф.

Граф Петерсена(J.Petersen, 1891)
- кубический граф без мостов, представляющий собой сумму 1-фактор и 2-фактора.
Литература:[Харари], [Лекции]

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

Граф плоский - см. Плоский граф.

Граф (a,b)-плоский - см. (a,b)-плоский граф.

Граф подразбиений(Subdivision graph)
- граф C(G), получаемый из графа G подразбиением каждого его ребра, т.е. добавлением на каждое ребро вершины степени 2.
Литература:[Харари]

Граф покрывающий - см. Покрывающий граф.

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

Граф полный двудольный - см. Полный двудольный граф.

Граф полный k-дольный - см. Полный k-дольный граф.

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

Граф полунесводимый - см. Полунесводимый граф.

Граф, получаемый стягиванием альтов в вершины - см. Фактор-уграф.

Граф полуэйлеров - см. Полуэйлеров граф.

Граф помеченный - см. Помеченный граф.

Граф пороговый - см. Пороговый граф.

Граф потока управления - то же, что и управляющий граф.

Граф потомства(Descendence graph)
- транзитивное замыкание графа воспроизведения; выражает отношение предок-потомок среди членов некоторой популяции.
Литература:[Оре]

Граф почти однородный - см. Почти однородный граф.

Граф правильный - см. Правильный граф.

Граф предельный - см. Предельный граф.

Граф прогрессивно конечный - см. Прогрессивно конечный граф.

Граф прогрессивно ограниченный - см. Прогрессивно ограниченный граф.

Граф производный - см. Производный граф.

Граф произвольно вычерчиваемый - см. Произвольно вычерчиваемый граф.

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

Граф произвольно проходимый - см. Произвольно проходимый граф.

Граф простой - см. Простой граф.

Граф процедур(Call graph)
- орграф, вершины которого суть процедуры программы, а дуги отражают возможность прямого обращения из одной процедуры к другой. В Г.п. предполагается, что все исполнения операторов вызова, обращающихся к одной и той же процедуре, приводят к одним и тем же цепочкам вложенных вызовов процедур. Для более точного кодирования межпроцедурных связей используется граф вызовов, вершинами которого являются операторы вызовов процедур, а дуги отражают непосредственную вложенность вызовов. В этом графе склеены, однако, выполнения так называемых особых вызовов - таких, при разных исполнениях которых могут вызываться разные процедуры. Выполнения особых вызовов расклеиваются в графе зацепленности, вершинами которого являются пары оператор вызова - вызываемая процедура, а дуги отражают непосредственную вложенность соответствующих пар.
Литература:[Касьянов]

Граф псевдосимметрический - см. Псевдосимметрический граф.

Граф пустой - см. Пустой граф.

Граф разборный - см. Разборный граф.

Граф раскрашенный - см. Раскрашенный граф.

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

Граф k-раскрашенный - см. k-раскрашенный граф.

Граф k-раскрашиваемый - см. k-раскрашиваемый граф.

Граф расщепляемый - см. Расщепляемый граф.

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

Граф реберно k-раскрашиваемый - см. Реберно k-раскрашиваемный граф.

Граф реберно-регулярный - см. Реберно-регулярный граф.

Граф k-реберно-связный - см. k-реберно-связный граф.

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

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

Граф регрессивно конечный - см. Регрессивно конечный граф.

Граф регрессивно ограниченный - см. Регрессивно ограниченный граф.

Граф регуляризуемый - см. Регуляризуемый граф.

Граф регулярный - см. Регулярный граф.

Граф реконструируемый - см. Реконструируемый граф.

Граф решетки(Lattice graph)
- граф, вершины которого суть пары натуральных чисел (x,y), 1 [leq] x [leq] m, 1 [leq] y [leq] n, и две вершины a = (x,y) и b = (z,t) смежны тогда и только тогда, когда |x-z| = 1 или |y-t| = 1. Иногда такой граф называют графом двумерной целочисленной решетки или просто двумерной целочисленной решеткой.
Литература:[Лекции]

Граф рода g - см. Род графа.

Граф самодополнительный - см. Самодополнительный граф.

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

Граф сбалансированный - см. Сбалансированный граф.

Граф сводимый - см. Сводимый граф; Сводимый управляющий граф.

Граф связный - см. Связный граф.

Граф k-связный - см. k-связный граф.

Граф сильно ориентированно-циклически замкнутый - см. Сильно ориентированно-циклически замкнутый граф.

Граф сильно ориентированно-циклически-реберно связный - см. Сильно ориентированно-циклически-реберный граф.

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

Граф сильно-циклически замкнутый - см. Сильно-циклически замкнутый граф.

Граф сильно-циклически связный - см. Сильно-циклически связный граф.

Граф симметрический - см. Симметрический граф.

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

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

Граф смежности ребер - то же, что и реберный граф.

Граф смешанный - см. Смешанный граф.

Граф совершенный - см. Совершенный граф.

Граф соединяющий - см. Соединяющий граф.

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

Граф составной - см. Составной граф.

Граф строгого частичного упорядочения(Graph of a strict partial order)
- бесконтурный транзитивный орграф, вершины которого суть элементы частично упорядоченного множества, а дуги выражают наличия отношения частичного порядка между элементами множества. На практике для наглядного представления частично упорядоченных множеств используются так называемые диаграммы (Хассе), представляющие собой транзитивную редукцию Г.с.ч.у.
Литература:[Оре]

Граф структурный - см. Структурный граф.

Граф стягиваемый - см. Стягиваемый граф.

Граф счетный - см. Счетный граф.

Граф тетраэдра - см. Граф многогранника.

Граф тождественный - то же, что и асимметрический граф.

Граф топологический - см. Топологический граф.

Граф S-топологический - см. S-топологический граф.

Граф тороидальный - см. Тороидальный граф.

Граф тотальный - см. Тотальный граф.

Граф точек сочленения(Cutpoint-graph)
- граф C(G), вершины которого суть точки сочленения графа G, а две вершины смежны тогда и только тогда, когда соответствующие точки сочленения принадлежат одному и тому же блоку. C(G) определяется лишь для графов, имеющих хотя бы одну точку сочленения.
Литература:[Харари]

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

Граф k-транзитивный - см. k-транзитивный граф.

Граф трехвалентный - то же, что и кубический граф.

Граф триангулированный - см. Триангулированный граф.

Граф тривиальный - см. Тривиальный граф.

Граф узловой - см. Узловой граф.

Граф унитарный - см. Унитарный граф.

Граф k-унитранзитивный - см. k-унитранзитивный граф.

Граф унициклический - см. Унициклический граф.

Граф упорядоченный - см. Упорядоченный граф.

Граф управляющий - см. Управляющий граф.

Граф Хивуда(P.J.Heawood)
- 4-транзитивный граф, представляющий собой цикл длины 14, у которого вершина v[_1] соединена хордой с вершиной v[_6], v[_2] - с вершиной v[_1][_1], v[_3] - с v[_8] и т.д.
Литература:[Харари]

Граф хордальный - то же, что и триангулированный граф.

Граф k-хроматический - см. k-хроматический граф.

Граф цветной Кэлли - см. Цветной граф Кэлли.

Граф циклически жесткий - см. Циклически жесткий граф.

Граф циклически замкнутый - см. Циклически замкнутый граф.

Граф циклический - см. Циклический граф.

Граф частичного упорядочения(Graph of a partial order)
- граф строгого частичного упорядочения, у которого каждая вершина снабжена петлей.
Литература:[Оре]

Граф частичный - см. Частичный граф.

Граф четный - см. Четный граф.

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

Граф-композиция(Composition of graphs)
- результат применения одной или нескольких операций над непересекающимися (без общих вершин) графами. Граф-композицией является, например, граф nG, состоящий из n копий графа G.
Литература:[Харари]

Графическая последовательность чисел(Graphical sequence of numbers)
- последовательность (d[_1], d[_2], ... , d[_n]) целых неотрицательных чисел такая, что существует граф, последовательность степеней которого совпадает с ней.
Литература:[Лекции]

Графический матроид(Graphical matroid)
- матроид, изоморфный циклическому матроиду некоторого графа.
Литература:[Лекции]

Графическое разбиение числа(Graphical partition of a number)
- такое разбиение n = d[_1] + d[_2] + ... + d[_p] числа n на p слагаемых, что найдется граф, степени вершин которого равны d[_i].
Литература:[Лекции]

Графоид(Graphoid)
- комбинаторный объект, состоящий из непустого множества M и двух семейств [cc] и [dd] непустых подмножеств множества M, называемых соответственно циклами и коциклами, которые удовлетворяют следующим аксиомам:
1) |C [cap] D| [neq] 1 для любых C [include] [cc] и D [include] [dd];
2) ни один из циклов не является собственной частью другого цикла и ни один коцикл не является собственной частью другого коцикла;
3) если раскрасить элементы множества M так, что точно один элемент будет зеленого цвета, а остальные красного или синего, то найдется либо цикл C, содержащий зеленый элемент и не содержащий ни одного красного, либо коцикл D, содержащий зеленый элемент и не содержащий ни одного синего.
Литература:[Харари]

Графы гомеоморфные - см. Гомеоморфные графы.

Графы изоморфные - см. Изоморфные графы.

Графы коспектральные - см. Коспектральные графы.

Графы Куратовского(Graphs of Kuratowski)
- графы K[_5] и K[_3][_zpt][_3].
Литература:[Кристофидес]

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

Графы сингулярно связанные - см. Сингулярно связанные графы.

Графы циклически изоморфные - см. Циклически изоморфные графы.

Группа автоморфизмов графа(Graph automorphism group)
- множество всех автоморфизмов графа относительно операции умножения подстановок (обозначение Aut(G)). Связь Г.а.г. с конечными группами устанавливает
Теорема Фрухта (1938). Каждая конечная группа изоморфна группе автоморфизмов некоторого графа.
Существуют примеры групп подстановок, которые хотя и изоморфны группам автоморфизмов графов, но сами таковыми не являются. См.Проблема Кенига. Другие названия - группа графа(дерева), вершинная группа графа.
Литература:[Лекции]

Группа графа - то же, что и группа автоморфизмов графа.

Группа графа вершинная - то же, что и группа автоморфизмов графа.

Группа графа реберная - см. Реберная группа графа.

Группа дерева - см. Группа графа.

Группа орграфа(Group of a directed graph)
- группа подстановок множества вершин орграфа, сохраняющих смежность. См. Группа автоморфизмов графа.
Литература:[Харари-Палмер]

Густота - то же, что и кликовое число.