Просмотр кода страницы Глоссарий теории графов

{{Глоссарий|Теория графов|nocat=1}}
Здесь собраны определения терминов из [[теория графов|теории графов]]. Курсивом выделены ''ссылки'' на термины в этом словаре (на этой странице).
__NOTOC__
{{АБВ}}

== А ==
* {{якорь|автоморфизм
}}'''[[Автоморфизм]]''' — ''[[#изоморфизм|Изоморфизм]]'' графа с самим собой.
* {{якорь|ациклический граф
}}'''Ациклический граф''' — граф без ''[[#цикл|циклов]]''.

== Б ==
* {{якорь|База графа
}}'''База графа''' — минимальное подмножество множества вершин графа, из которых достижима любая вершина графа.
* {{якорь|бесконечный граф
}}'''Бесконечный граф''' — граф, имеющий бесконечно много вершин и/или рёбер.
* {{якорь|биграф
}}'''Биграф''' — см. ''[[#двудольный граф|двудольный граф]]''.
* {{якорь|блок
}}'''Блок''' — граф без ''[[#шарнир|шарниров]]''.
* {{якорь|блок-дизайн
}}'''[[Блок-дизайн]]''' с параметрами (v, k, λ) — покрытие с кратностью λ полного графа на v вершинах полными графами на k вершинах.
<!-- * {{якорь|бинарный граф
}}'''Бинарный граф''' — граф, имеющий вершины двух сортов, причём дуги могут соединять только вершины различных типов. — это же определение двудольного графа! -->

== В ==
* {{якорь|валентность вершины
}}'''Валентность вершины''' — см. ''[[#степень вершины|степень вершины]]''.
* {{якорь|вершина
}}'''[[Вершина (теория графов)|Вершина]]''', '''узел''' — [[базовое понятие]]: [[Точка (геометрия)|точка]], где могут сходиться/выходить ''[[#ребро|рёбра]]'' и/или ''[[#дуга|дуги]]''. Множество вершин графа G обозначается V(G).
*{{якорь|вершинное покрытие
}}'''[[Задача о вершинном покрытии|Вершинное покрытие]]''' — множество вершин графа такое, что каждое ребро [[Инцидентность (геометрия)|инцидентно]] хотя бы одной вершине из этого множества.
* {{якорь|вес ребра
}}'''Вес ребра''' — значение, [[Отображение|поставленное в соответствие]] данному ''[[#ребро|ребру]]'' ''[[#взвешенный граф|взвешенного графа]]''. Обычно вес — [[вещественное число]], в таком случае его можно интерпретировать как «[[Мера множества|длину]]» ребра.
* {{якорь|взвешенный граф
}}'''Взвешенный граф''' — [[Граф (математика)|граф]], каждому ''[[#ребро|ребру]]'' которого [[Отображение|поставлено в соответствие]] некое значение (''[[#вес ребра|вес ребра]]''). <!--пополнить про [[Алгоритм Дейкстры]]--> См. [[Глоссарий теории графов#размеченный граф|Размеченный граф]].
* {{якорь|висячая вершина
}}'''Висячая вершина''' — ''[[#вершина|вершина]]'', ''[[#степень вершины|степень]]'' которой равна 1 (то есть <math>d(v)=1</math>).
{{якорь|вполне несвязный граф}}
* '''Вполне несвязный граф'''<!-- на ВП:КУ статью решено было удалить --> — ''[[#регулярный граф|регулярный граф]]'' степени 0, то есть граф без ''[[#ребро|рёбер]]''.
* {{якорь|высота дерева
}}'''Высота дерева''' — наибольшая длина [[путь (теория графов)|пути]] от ''[[#корень дерева|корня]]'' к ''[[#лист дерева|листу]]''.

== Г ==
* {{якорь|гамильтонов граф
}}'''[[Гамильтонов граф]]''' — граф, в котором есть ''[[#гамильтонов цикл|гамильтонов цикл]]''.
* {{якорь|гамильтонов путь
}}'''Гамильтонов путь''' — ''[[#простой путь|простой путь]]'' в графе, содержащий все ''[[#вершина|вершины]]'' графа ровно по одному разу.
* {{якорь|гамильтонов цикл
}}'''[[Гамильтонов цикл]]''' — ''[[#простой цикл|простой цикл]]'' в графе, содержащий все вершины графа ровно по одному разу.
* {{якорь|геометрическая реализация
}}'''Геометрическая реализация''' — фигура, вершинам которой соответствуют вершины графа, рёбрам — рёбра графа и рёбра в фигуре соединяют вершины, соответствующие вершинам в графе.
* {{якорь|геометрический граф
}}'''Геометрический граф''' — плоская фигура из вершин — точек плоскости и рёбер — линий, соединяющих некоторые пары вершин. Может представлять многими способами всякий граф.
* {{якорь|гиперграф
}}'''[[Гиперграф]]''' — совокупность из множества вершин и множества гиперрёбер (подмножество n-й евклидовой степени множества вершин, то есть гиперрёбра соединяют произвольное количество вершин).
* {{якорь|гомеоморфные графы
}}'''Гомеоморфные графы''' — графы, получаемые из одного графа с помощью последовательности подразбиений рёбер.
* {{якорь|грань
}}'''[[Грань (теория графов)|Грань]]''' — область, ограниченная рёбрами в ''[[#плоский граф|плоском графе]]'' и не содержащая внутри себя вершин и рёбер графа. Внешняя часть плоскости тоже образует грань.
* {{якорь|граф
}}'''[[Граф (математика)|Граф]]''' — базовое понятие. Включает множество ''[[#вершина|вершин]]'' и множество ''[[#ребро|рёбер]]'', являющееся [[подмножество]]м [[прямое произведение|декартова квадрата]] множества вершин (то есть каждое ребро соединяет ровно две вершины).
* {{якорь|граф рода
}}'''Граф рода''' ''g'' — граф, который можно изобразить без пересечений на [[род поверхности|поверхности рода]] ''g'' и нельзя изобразить без пересечений ни на одной поверхности рода ''g''-1. В частности, [[#планарный граф|планарные графы]] имеют род 0.

== Д ==
* {{якорь|двойственный граф
}}'''[[Двойственный граф]]'''. Граф ''А'' называется двойственным к планарному графу ''В'', если вершины графа ''А'' соответствуют ''[[#грань|граням]]'' графа ''В'', и две вершины графа ''A'' соединены ребром тогда и только тогда, когда соответствующие грани графа ''B'' имеют хотя бы одно общее ребро.
* {{якорь|двудольный граф
}}'''[[Двудольный граф]]''' (или '''биграф''', или '''чётный граф''') — такой граф <math>G(V,E)</math>, что множество вершин ''V'' разбито на два непересекающихся подмножества <math>V_1</math> и <math>V_2</math>, причём всякое ребро ''E'' инцидентно вершине из <math>V_1</math> и вершине из <math>V_2</math> (то есть соединяет вершину из <math>V_1</math> с вершиной из <math>V_2</math>). То есть ''[[#правильная раскраска графа|правильная раскраска графа]]'' осуществляется двумя цветами. Множества <math>V_1</math> и <math>V_2</math> называются «долями» двудольного графа. Двудольный граф называется «полным», если любые две вершины из <math>V_1</math> и <math>V_2</math> являются смежными. Если <math>\left|V_1\right| = a</math>, <math>\left|V_2\right| = b</math>, то полный двудольный граф обозначается <math>K_{a,b}</math>.
* {{якорь|двусвязный граф
}}'''Двусвязный граф''' — ''[[#связный граф|связный граф]]'', в котором нет ''[[#шарнир|шарниров]]''.
* {{якорь|дерево
}}'''[[Дерево (теория графов)|Дерево]]''' — ''[[#связный граф|связный граф]]'', не содержащий ''[[#цикл|циклов]]''.
* {{якорь|диаметр графа
}}'''[[Диаметр графа]]''' <math>\mathrm{diam}(G)</math> — максимум расстояния между вершинами для всех пар вершин. Расстояние между вершинами — наименьшее число рёбер ''[[#путь|пути]]'', соединяющего две вершины.
* {{якорь|длина маршрута
}}'''Длина''' ''[[#маршрут|маршрута]]'' — количество рёбер в маршруте (с повторениями). Если маршрут <math>M=v_0,e_1,v_1,e_2,v_2,...,e_k,v_k</math>, то длина ''M'' равна ''k'' (обозначается <math>\left|M\right|=k</math>).
* {{якорь|длина пути
}}'''Длина''' ''[[#путь|пути]]'' — число дуг пути (или сумма длин его дуг, если последние заданы). Так для пути v<sub>1</sub>, v<sub>2</sub>, …, v<sub>n</sub> длина равна n-1.
* {{якорь|дуга
}}'''Дуга''' — ориентированное ''[[#ребро|ребро]]''.
* {{якорь|дополнение графа
}}'''[[Дополнение графа]]''' — граф над тем же множеством вершин, что и исходный, но вершины соединены ребром тогда и только тогда, когда в исходном графе ребра нет.

== Е ==
* {{якорь|Ежевика
}}'''[[Ежевика (теория графов)|Ежевика]]''' неориентированного графа ''G'' — семейство связных подграфов графа ''G'', касающихся друг друга.

== З ==
* {{якорь|граф-звезда
}}'''[[Граф-звезда]]''' — полный двудольный граф <math>K_{1,b}</math>.

== И ==
* {{якорь|изолированная вершина
}}'''Изолированная вершина''' — вершина, ''[[#степень вершины|степень]]'' которой равна 0 (то есть нет рёбер, ''[[#инцидентность|инцидентных]]'' ей).
* {{якорь|изоморфизм
}}'''[[Изоморфизм графов|Изоморфизм]]'''. Два графа называются '''изоморфными''', если существует перестановка вершин, при которой они совпадают. Иначе говоря, два графа называются '''изоморфными''', если существует взаимно-однозначное соответствие между их вершинами и рёбрами, которое сохраняет ''[[#смежность|смежность]]'' и ''[[#инцидентность|инцидентность]]'' (графы отличаются только названиями своих вершин).
* {{якорь|инвариант графа
}}'''[[Инвариант графа]]''' — числовая характеристика графа или их упорядоченный вектор, характеризующая структуру графа инвариантно относительно перенумерации вершин.
* {{якорь|интервальный граф
}}'''[[Интервальный граф]]''' — граф, вершины которого могут быть взаимно однозначно поставлены в соответствие отрезкам на действительной оси таким образом, что две вершины ''[[#инцидентность|инцидентны]]'' одному ребру тогда и только тогда, когда отрезки, соответствующие этим вершинам, пересекаются.
* {{якорь|инцидентность
}}'''Инцидентность''' — понятие, используемое только в отношении ребра или дуги и вершины: если <math>v_1, v_2</math> — вершины, а <math>e=(v_1,v_2)</math> — соединяющее их ребро, тогда вершина <math>v_1</math> и ребро <math>e</math> инцидентны, вершина <math>v_2</math> и ребро <math>e</math> тоже инцидентны. Две вершины (или два ребра) инцидентными быть не могут. Для обозначения ближайших вершин (рёбер) используется понятие ''[[#смежность|смежности]]''.

== К ==
* {{якорь|клетка
}}'''[[Клетка (теория графов)|Клетка]]''' — ''[[#регулярный граф|регулярный граф]]'' наименьшего ''[[#обхват|обхвата]]'' для заданной степени вершин.
* {{якорь|клика
}}'''[[Клика (теория графов)|Клика]]''' — подмножество вершин графа, полностью соединённых друг с другом, то есть подграф, являющийся ''[[#полный граф|полным графом]]''.
** {{якорь|кликовое число
}}'''Кликовое число''' ({{lang-en|clique number}}) — число (G) вершин в наибольшей клике. ''Другие названия — густота, плотность.''
** {{якорь|максимальная клика
}}'''Максимальная клика''' — клика с максимально возможным числом вершин среди клик графа.
* {{якорь|колесо
}}'''[[Колесо (теория графов)|Колесо]]''' (обозначается ''W''<sub>''n''</sub>) — граф с ''n'' вершинами (n ≥ 4), образованный соединением единственной вершины со всеми вершинами (''n''-1)-цикла.
* {{якорь|колчан
}}'''[[Колчан (теория графов)|Колчан]]''' — просто ориентированный граф.
* {{якорь|конечный граф
}}'''Конечный граф''' — граф, содержащий конечное число вершин и рёбер.
* {{якорь|конструктивное перечисление графов
}}'''Конструктивное перечисление графов''' — получение полного списка графов в заданном классе.
* {{якорь|компонента связности
}}'''[[Компонента связности графа]]''' — такое [[подмножество]] ''[[#вершина|вершин]]'' ''[[#граф|графа]]'', для любых двух вершин которого существует ''[[#путь|путь]]'' из одной в другую, и не существует пути из вершины этого подмножества в вершину не из этого подмножества.
* {{якорь|компонента сильной связности графа
}}'''[[Компонента сильной связности графа]]''', '''слой''' — максимальное множество вершин ''[[#орграф|ориентированного графа]]'', такое, что для любых двух вершин из этого множества существует ''[[#путь|путь]]'' как из первой во вторую, так и из второй в первую.
<!-- * {{якорь|контур
}}'''[[Контур (теория графов)|]]''' — путь, у которого конечная вершина совпадает с начальной вершиной. (См. ''[[#длина пути|Длина пути]]'')
 Это ещё что за дубли?! --Incnis Mrsi -->
* {{якорь|контур
}}'''Контур''' — замкнутый ''[[#путь в орграфе|путь в орграфе]]''.
* {{якорь|корень дерева
}}'''Корень дерева''' — выбранная ''[[#вершина|вершина]]'' [[#дерево|дерева]]; в ''[[#орграф|орграф]]е'' — вершина с нулевой степенью захода.
* {{якорь|коцикл
}}'''[[Коцикл]]''' — минимальный ''[[#разрез|разрез]]'', минимальное множество рёбер, удаление которого делает граф несвязным.
* {{якорь|кратные рёбра
}}'''[[Кратные рёбра]]''' — несколько ''[[#ребро|рёбер]]'', ''[[#инцидентность|инцидентных]]'' одной и той же паре вершин. Встречаются в ''[[#мультиграф|мультиграфах]]''.
* {{якорь|кубический граф
}}'''Кубический граф''' — регулярный граф степени 3, то есть граф, в котором каждой вершине инцидентно ровно три ребра.
* {{якорь|k-дольный граф
}}'''[[Многодольный граф|k-дольный граф]]''' — граф G, у которого ''[[#хроматическое число|хроматическое число]]'' c(G)=k
* {{якорь|k-связный граф
}}'''[[k-связный граф]]''' — ''[[#связный граф|связный граф]]'', в котором не существует набора <math>V'</math> из <math>k-1</math> или менее ''[[#вершина|вершин]]'', такого, что удаление всех вершин <math>V'</math> и инцидентных им ''[[#ребро|рёбер]]'' нарушает связность графа. В частности, ''[[#связный граф|связный граф]]'' является 1-связным, а ''[[#двусвязный граф|двусвязный]]'' — 2-связным.

== Л ==
* {{якорь|ламанов граф
}}'''[[Ламанов граф|Лама́нов граф]]''' с ''n'' вершинами — такой граф ''G'', что, во-первых, для каждого ''k'' любой подграф графа ''G'', содержащий ''k'' вершин, имеет не более, чем 2''k'' −3 ребра и, во-вторых, граф ''G'' имеет ровно 2''n'' −3 ребра.

* {{якорь|лес
}}'''Лес''' — неориентированный граф без циклов. ''[[#компонента связности|Компонентами связности]]'' леса являются ''[[#дерево|деревья]]''.
* {{якорь|лист дерева
}}'''Лист дерева''' — ''[[#вершина|вершина]]'' [[#дерево|дерева]] с единственным ''[[#ребро|ребром]]'' или входящей ''[[#дуга|дугой]]''.
* {{якорь|локальная степень вершины
}}'''Локальная степень вершины''' — число рёбер, ей инцидентных. Петля даёт вклад, равный «2», в степень вершины.

== М ==
* {{якорь|макси-код
}}'''Макси-код''' <math>\mu_{max}</math> — трудновычислимый [[полный инвариант графа]], получаемый путём выписывания двоичных значений [[Матрица смежности|матрицы смежности]] в строчку с последующим переводом полученного [[Двоичная система счисления|двоичного числа]] в десятичную форму. Макси-коду соответствует такой порядок следования строк и столбцов, при котором полученное значение является максимально возможным.
* {{якорь|максимальное паросочетание
}}'''Максимальное паросочетание''' в графе. Паросочетание называется максимальным, если любое другое паросочетание содержит меньшее число рёбер.
* {{якорь|маршрут
}}'''Маршрут''' в графе — чередующаяся последовательность вершин и рёбер <math>v_0, e_1, v_1, e_2, v_2, ... , e_k, v_k</math>, в которой любые два соседних элемента ''[[#инцидентность|инцидентны]]''. Если <math>v_0=v_k</math>, то маршрут '''замкнут''', иначе '''открыт'''.
* {{якорь|матрица достижимости
}}'''[[Матрица достижимости]]''' орграфа — матрица, содержащая информацию о существовании путей между вершинами в орграфе.
* {{якорь|матрица инцидентности
}}'''[[Матрица инцидентности]]''' графа — матрица, значения элементов которой характеризуется инцидентностью соответствующих вершин графа (по вертикали) и его рёбер (по горизонтали). Для неориентированного графа элемент принимает значение '''1''', если соответствующие ему вершина и ребро инцидентны. Для ''[[#орграф|ориентированного]]'' графа элемент принимает значение '''1''', если инцидентная вершина является началом ребра, значение '''-1''', если инцидентная вершина является концом ребра; в остальных случаях (в том числе и для ''[[#петля|петель]]'') значению элемента присваивается '''0'''.
* {{якорь|матрица смежности
}}'''[[Матрица смежности]]''' графа — матрица, значения элементов которой характеризуются смежностью вершин графа. При этом значению элемента матрицы присваивается количество рёбер, которые соединяют соответствующие вершины (то есть которые ''[[#инцидентность|инцидентны]]'' обеим вершинам). 
* {{якорь|мини-код
}}'''Мини-код''' <math>\mu_{min}</math> — трудновычислимый [[полный инвариант графа]], получаемый путём выписывания двоичных значений [[Матрица смежности|матрицы смежности]] в строчку с последующим переводом полученного [[Двоичная система счисления|двоичного числа]] в десятичную форму. Мини-коду соответствует такой порядок следования строк и столбцов, при котором полученное значение является минимально возможным.
* {{якорь|минимальный каркас
}}'''[[Минимальный каркас]]''' (или '''каркас минимального веса''', '''минимальное остовное дерево''') графа — ациклическое (не имеющее циклов) множество рёбер в связном, взвешенном и неориентированном графе, соединяющих между собой все вершины данного графа, при этом сумма весов всех рёбер в нём минимальна.
* {{якорь|множество смежности
}}'''Множество смежности''' вершины ''v'' — множество вершин, смежных с вершиной ''v''. Обозначается <math>\Gamma^+(v)</math>.
* {{якорь|минор
}}'''Минором графа''' называется граф, который можно получить из исходного путём удаления и стягивания дуг.
* {{якорь|мост
}}'''[[Мост (теория графов)|Мост]]''' — ''[[#ребро|ребро]]'', удаление которого увеличивает количество ''[[#компонента связности|компонент связности]]'' в графе.
* {{якорь|мультиграф
}}'''[[Мультиграф]]''' — граф, в котором может быть пара вершин, которая соединена более чем одним ребром (ненаправленным), либо более чем двумя дугами противоположных направлений.

== Н ==
* {{якорь|направленный граф
}}'''Направленный граф''' — ''[[#орграф|ориентированный граф]]'', в котором две вершины соединяются не более чем одной дугой.
** {{якорь|направленный ациклический граф
}}'''[[Направленный ациклический граф]]''' — ориентированный граф без ''[[#контур|контуров]]''.
* {{якорь|независимое множество вершин
}}'''[[Задача о независимом множестве|Независимое множество вершин]]''' (известное также как '''внутренне устойчивое множество''') — множество вершин графа G, в котором любые две вершины несмежны (никакая пара вершин не соединена ребром).
** Независимое множество называется '''максимальным''', когда нет другого независимого множества, в которое оно бы входило. Дополнение наибольшего независимого множества называется '''минимальным вершинным покрытием''' графа.
**'''Наибольшим независимым множеством''' называется независимое множество наибольшего размера.
* {{якорь|независемые вершины
}}'''Независимые вершины''' — попарно несмежные вершины графа.<ref>'' Дистель Р.'' Теория графов Пер. с англ. — Новосибирск: Изд-во Ин-та математики, 2002. — С. 17.</ref>
* {{якорь|неразделимый граф
}}'''Неразделимый граф''' — связный, непустой, не имеющий точек сочленения граф.<ref>''Харари Ф.'' Теория графов. — М.: Мир, 1972. — С. 41.</ref>.
* {{якорь|нормированный граф
}}'''Нормированный граф''' — ''[[#орграф|ориентированный граф]]'' без ''[[#цикл|циклов]].<!-- это точно не дубль предыдущего? -->
{{якорь|нуль-граф}}{{якорь|нулевой граф}}
* '''Нуль-граф''' ('''пустой граф''') — граф без ''[[#вершина|вершин]]''.

== О ==
* {{якорь|обхват
}}'''[[Обхват (теория графов)|Обхват]]''' — длина наименьшего ''[[#цикл|цикла]]'' в графе.
<!-- , при отсутствии циклов неопределен.
 «При отсутствии данных обработка данных отсутствует», так? Бессмысленное добавление, лучше было бы напомнить что инфимум пустого множества равен +∞
 --Incnis Mrsi -->
* {{якорь|Объединение графов
}}'''[[Объединение графов]]''' (помеченных графов <math>G_1=(X_1, U_1)</math> и <math>G_2=(X_2, U_2)</math>) — граф <math>G_1 \cup G_2</math>, множеством вершин которого является <math>X_1 \cup X_2</math>, а множеством рёбер — <math>U=U_1 \cup U_2</math>.
* {{якорь|окрестность
}}'''Окрестность порядка''' ''k'' — множество вершин на расстоянии ''k'' от заданной вершины ''v''; иногда толкуется расширительно как множество вершин, отстоящих от ''v'' на расстоянии не больше ''k''.
* {{якорь|окружение
}}'''Окружение''' — множество вершин, смежных с заданной.
* {{якорь|орграф
}}'''[[Орграф]]''', '''ориентированный граф''' G = (V,E) есть пара множеств, где V — множество вершин (узлов), E — множество дуг (ориентированных рёбер). Дуга — упорядоченная пара вершин (v, w), где вершину v называют началом, а w — концом дуги. Можно сказать, что дуга v → w ведёт от вершины v к вершине w, при этом вершина w смежная с вершиной v.
* {{якорь|остов
}}'''[[Остовное дерево]]''' ('''остов''') (неориентированного) связного графа <math>G = (V,E)</math> — всякий ''[[#частичный граф|частичный граф]]'' <math>S=(V,T)</math>, являющийся ''[[#дерево|деревом]]''.
* {{якорь|остовный подграф
}}'''Остовный подграф''' — подграф, содержащий все вершины.

== П ==
* {{якорь|паросочетание
}}'''[[Паросочетание]]''' — набор попарно несмежных рёбер.
* {{якорь|петля
}}'''[[Петля (теория графов)|Петля]]''' — ребро, начало и конец которого находятся в одной и той же вершине.
* {{якорь|пересечение графов
}}'''[[Пересечение графов]]''' (помеченных графов <math>G_1=(X_1, U_1)</math> и <math>G_2=(X_2, U_2)</math>) — граф <math>G_1 \cap G_2</math>, множеством вершин которого является <math>X_1 \cap X_2</math>, а множеством рёбер — <math>U=U_1 \cap U_2</math>.
* {{якорь|перечисление графов
}}'''[[Перечисление графов]]''' — подсчёт числа неизоморфных графов в заданном классе (с заданными характеристиками).
* {{якорь|периферийная вершина
}}'''[[Периферийная вершина]]''' — вершина, [[Глоссарий теории графов#эксцентриситет|эксцентриситет]] которой равен диаметру графа.
* {{якорь|планарный граф
}}'''[[Планарный граф]]''' — граф, который может быть изображён (''[[#укладка|уложен]]'') на плоскости без пересечения рёбер. ''[[#изоморфизм|Изоморфен]]'' плоскому графу, то есть является графом с пересечениями, но допускающий его плоскую укладку, поэтому может отличаться от ''[[#плоский граф|плоского графа]]'' изображением на плоскости. Таким образом, может быть разница между плоским графом и планарным графом при изображении на плоскости.
* {{якорь|плоский граф
}}'''[[Плоский граф]]''' — ''[[#геометрический граф|геометрический граф]]'', в котором никакие два ребра не имеют общих точек, кроме инцидентной им обоим вершины (не пересекаются). Является ''[[#укладка|уложенным]]'' графом на плоскости.
* {{якорь|подграф
}}'''Подграф''' исходного графа — граф, содержащий некое подмножество вершин данного графа и некое подмножество ''[[#инцидентность|инцидентных]]'' им рёбер. (ср. ''[[#суграф|Суграф]]''.) По отношению к подграфу исходный граф называется ''[[#суперграф|суперграфом]]''
* {{якорь|полный граф
}}'''[[Полный граф]]''' — граф, в котором для каждой пары вершин <math>v_1, v_2</math>, существует ребро, инцидентное <math>v_1</math> и инцидентное <math>v_2</math> (каждая вершина соединена ребром с любой другой вершиной).
* {{якорь|полный инвариант графа
}}'''[[Полный инвариант графа]]''' — числовая характеристика графа или их упорядоченный вектор, значения которой [[Необходимое и достаточное условие|необходимо и достаточно]] для установления [[#изоморфизм|изоморфизма]] графов.
* {{якорь|полный двудольный граф
}}'''Полным двудольным''' называется ''[[#двудольный граф|двудольный граф]]'', в котором каждая вершина одного подмножества соединена ребром с каждой вершиной другого подмножества
* {{якорь|полустепень захода
}}'''Полустепень захода''' в ''[[#орграф|орграфе]]'' для вершины <math>v</math> — число дуг, входящих в вершину. Обозначается <math>d^+(v)</math>, <math>\mathrm{deg}^+(v)</math>, <math>\mathrm{indeg}(v)</math> или <math>d_t(v)</math>.
* {{якорь|полустепень исхода
}}'''Полустепень исхода''' в ''[[#орграф|орграфе]]'' для вершины <math>v</math> — число дуг, исходящих из вершины. Обозначается <math>d^-(v)</math>, <math>\mathrm{deg}^-(v)</math>, <math>\mathrm{outdeg}(v)</math> или <math>d_o(v)</math>.
* {{якорь|помеченный граф
}}'''[[Помеченный граф]]''' — граф, вершинам или дугам которого присвоены какие-либо метки, например, натуральные числа или символы какого-нибудь алфавита.
* {{якорь|порождённый подграф
}}'''Порождённый подграф''' — подграф, порождённый подмножеством вершин и множеством всех рёбер исходного графа, которые соединяют вершины из заданного подмножества. Содержит не обязательно все вершины графа, но эти вершины соединены такими же рёбрами, как в графе.
* {{якорь|порядок графа
}}'''Порядок графа''' — количество вершин графа.<ref>'' Дистель Р.'' Теория графов Пер. с англ. — Новосибирск: Изд-во Ин-та математики, 2002. — С. 16.</ref>
* {{якорь|правильная раскраска графа
}}'''[[Правильная раскраска графа]]''' — [[раскраска графа|раскраска]]<!-- TODO: может, определить её уже где-нибудь? -->, при которой каждый цветной класс является независимым множеством. Иначе говоря, в правильной раскраске любые две смежные вершины должны иметь разные цвета.
* {{якорь|произведение графов
}}'''Произведение графов''' — для данных графов <math>G_1=(V_1,E_1)</math> и <math>G_2=(V_2,E_2)</math> произведением называется граф <math>G = (V,E)</math>, вершины которого <math>V(G) = V_1 \times V_2</math> — декартово произведение множеств вершин исходных графов.
* {{якорь|простая цепь
}}'''Простая цепь''' — ''[[#маршрут|маршрут]]'', в котором все вершины различны.
* {{якорь|простой граф
}}'''[[Простой граф]]''' — ''[[#граф|граф]]'', в котором нет ''[[#кратные рёбра|кратных рёбер]]'' и ''[[#петля|петель]]''.
* {{якорь|простой путь
}}'''[[Простой путь]]''' — ''[[#путь|путь]]'', все вершины которого попарно различны<ref name="Кузнецов">''Кузнецов О. П., Адельсон-Вельский Г. М.'' / Дискретная математика для инженера. / М.: Энергия, 1980—344 с., ил. Стр. 120—122</ref>. Другими словами, простой путь не проходит дважды через одну вершину.
** {{якорь|простой цикл
}}'''Простой цикл''' — ''[[#цикл|цикл]]'', не проходящий дважды через одну вершину.
* {{якорь|псевдограф
}}'''Псевдограф''' — граф, который может содержать ''[[#петля|петли]]'' и/или кратные рёбра.
{{якорь|пустой граф}}
* '''Пустой граф''' ('''нуль-граф''') — граф без ''[[#ребро|рёбер]]''.
* {{якорь|путь
}}'''[[Путь (теория графов)|Путь]]''' — последовательность ''[[#ребро|рёбер]]'' (в неориентированном графе) и/или дуг (в ориентированном графе), такая, что конец одной дуги (ребра) является началом другой дуги (ребра). Или последовательность вершин и дуг (рёбер), в которой каждый элемент инцидентен предыдущему и последующему<ref name="Кузнецов" />. Может рассматриваться как частный случай ''[[#маршрут|маршрута]]''.
<!-- В другой трактовке<ref name="Harary 233">Ф. Харари ''Теория графов'' стр. 233</ref> '''Путь''' — ''[[#маршрут|маршрут]]'' в орграфе, в котором все вершины различны.
 Ничего не имею против, но сначала определите маршрут для случая ОРГРАФА!
 --Incnis Mrsi -->
* {{якорь|путь в орграфе
}}'''[[Путь в орграфе]]''' — последовательность вершин v<sub>1</sub>, v<sub>2</sub>, …, v<sub>n</sub>, для которой существуют дуги v<sub>1</sub> → v<sub>2</sub>, v<sub>2</sub> → v<sub>3</sub>, …, v<sub>n-1</sub> → v<sub>n</sub>. Говорят, что этот путь начинается в вершине v<sub>1</sub>, проходит через вершины v<sub>2</sub>, v<sub>3</sub>, …, v<sub>n-1</sub>, и заканчивается в вершине v<sub>n</sub>.

== Р ==
* {{якорь|радиус графа
}}'''Радиус графа''' — минимальный из ''[[#эксцентриситет|эксцентриситетов]]'' вершин связного графа; вершина, на которой достигается этот минимум, называется центральной вершиной.
* {{якорь|разбиение графа
}}'''[[Разбиение графа]]''' — представление исходного графа в виде [[множество|множества]] подмножеств вершин по определённым правилам.
* {{якорь|разделяющая вершина
}}'''Разделяющая вершина''' — то же, что и ''[[#шарнир|шарнир]]'' и ''[[#точка сочленения|точка сочленения]]''.
* {{якорь|развёртка графа
}}'''[[Развёртка графа]]''' — функция, заданная на вершинах ориентированного графа.
* {{Якорь}}'''Размер графа''' — количество рёбер графа.
* {{якорь|размеченный граф
}}'''Размеченный граф''' — граф, для которого задано множество меток S, функция разметки вершин f : A → S и функция разметки дуг g : R → S. Графически эти функции представляются надписыванием меток на вершинах и дугах. Множество меток может разделяться на два непересекающихся подмножества меток вершин и меток дуг.
* {{якорь|разрез
}}'''[[Разрез графа|Разрез]]''' — множество ''[[#ребро|рёбер]]'', удаление которого делает граф [[#связный граф|несвязным]].
* {{якорь|рамочный граф
}}'''[[Рамочный граф]]''' — граф, который можно нарисовать на плоскости таким способом, что любая ограниченная грань является четырёхугольником и любая вершина с тремя и менее соседями инцидентна неограниченной грани.<ref>{{статья
| автор = А. В. Карзанов 
| заглавие = Расширения конечных метрик и задача о размещении оборудования
| издание = Труды ИСА РАН
| год = 2007
| том = 29
| страницы = 225—244 (241)
}}</ref>
* {{якорь|раскраская графа
}}'''[[Хроматическое число|Раскраска графа]]''' — разбиение вершин на множества (называемые цветами). Если при этом нет двух смежных вершин, принадлежащих одному и тому же множеству (то есть две смежные вершины всегда разного цвета), то такая раскраска называется правильной.
* '''[[Расстояние (теория графов)|Расстояние]] между вершинами''' — длина кратчайшей цепи (в орграфе пути), соединяющей заданные вершины. Если такой цепи (пути) не существует, расстояние полагается равным бесконечности.
* {{якорь|рёберное покрытие
}}'''[[Рёберное покрытие]]''' — множество рёбер графа такое, что каждая вершина инцидентна хотя бы одному ребру из этого множества.
*{{якорь|Рёберный граф
}}'''[[Рёберный граф]]''' неориентированного графа — это граф, представляющий соседство рёбер графа.
* {{якорь|ребро
}}'''Ребро''' — базовое понятие. Ребро соединяет две ''[[#вершина|вершины]]'' графа.
* {{якорь|регулярный граф
}}'''[[Регулярный граф]]''' — граф, ''[[#степень вершины|степени]]'' всех вершин которого равны. Степень регулярности является [[Инвариант (математика)|инвариантом]] графа и обозначается <math>r(G)</math>. Для нерегулярных графов <math>r(G)</math> не определено. Регулярные графы представляют особую сложность для многих алгоритмов.
** '''Регулярный граф степени 0''' ('''вполне несвязный граф''', '''пустой граф''', '''нуль-граф''') — граф без ''[[#ребро|рёбер]]''.

== С ==
* {{якорь|самодвойственный граф
}}'''Самодвойственный граф''' — граф, ''[[#изоморфизм|изоморфный]]'' своему ''[[#двойственный граф|двойственному графу]]''.
* {{якорь|сверхстройное дерево 
}}'''Сверхстройное (звездообразное) дерево''' — дерево, в котором имеется единственная вершина степени больше 2.
* {{якорь|связность
}}'''Связность'''. Две вершины в графе '''связаны''', если существует соединяющая их (простая) ''[[#цепь|цепь]]''.
* {{якорь|связный граф
}}'''[[Связный граф]]''' — граф, в котором все вершины связаны.
* {{якорь|сечение графа
}}'''Сечение графа''' — множество рёбер, удаление которых делит граф на два изолированных подграфа, один из которых, в частности, может быть тривиальным графом.
* {{якорь|сеть
}}'''Сеть''' — в принципе, то же, что и ''[[#граф|граф]]'', хотя сетями обычно называют графы, ''[[#вершина|вершины]]'' которых определённым образом помечены.<!-- по мотивам [[Обсуждение:Теория графов]] -->
** '''Ориентированная сеть''' — ориентированный граф, не содержащий контуров.
* {{якорь|сильная связность
}}'''Сильная связность'''. Две вершины в ''[[#орграф|ориентированном графе]]'' '''сильно связаны''', если существует путь из первой во вторую и из второй в первую.
** {{якорь|сильно связный орграф
}}'''Сильно связный орграф''' — ''[[#орграф|орграф]]'', в котором все вершины сильно связаны.
* {{якорь|смежность
}}'''Смежность''' — понятие, используемое в отношении только двух ''[[#ребро|рёбер]]'' либо только двух ''[[#вершина|вершин]]'': Два ребра, ''[[#инцидентность|инцидентные]]'' одной вершине, называются '''смежными'''; две вершины, ''[[#инцидентность|инцидентные]]'' одному ребру, также называются '''смежными'''. (ср. ''[[#инцидентность|Инцидентность]]''.)
* {{якорь|смешанный граф
}}'''Смешанный граф''' — граф, содержащий как ориентированные, так и неориентированные ''[[#ребро|рёбра]]''.
* {{якорь|совершенное паросочетание
}}'''Совершенное паросочетание''' — паросочетание, содержащее все вершины графа.
* {{якорь|Соединение графов
}}'''Соединением двух графов''' <math>G_1=(V_1,E_1)</math> и <math>G_2=(V_2,E_2)</math>, не имеющих общих вершин, называется граф <math>G_1+G_2=(V_1 \cup V_2,E_1 \cup E_2 \cup V_1 \times V_2 \cup V_2 \times V_1)</math>.<ref>
{{статья 
 | автор=М. Б. Абросимов
 | заглавие=О минимальных вершинных 1-расширениях соединений графов специального вида. 
 | издание=Прикладная теория графов. 
 | год=2011
 | выпуск=4
}}</ref>
Из определения видно, что соединение графов обладает свойствами коммутативности и ассоциативности
* {{якорь|спектр графа 
}}'''Спектр графа''' — множество всех собственных значений матрицы смежности с учётом кратных рёбер.
* {{якорь|степень вершины
}}'''[[Степень вершины (теория графов)|Степень вершины]]''' — количество рёбер графа ''G'', ''[[#инцидентность|инцидентных]]'' вершине ''x''. Обозначается <math>d(x)</math>. ''Минимальная'' степень вершины графа ''G'' обозначается <math>\delta(G)</math>. а ''максимальная'' — <math>\Delta(G)</math>.
* {{якорь|стягивание
}}'''[[Стягивание ребра|Стягивание ребра графа]]''' — замена концов ребра одной вершиной, соседями новой вершины становятся соседи этих концов. Граф <math>G_1</math> '''стягиваем''' к <math>G_2</math>, если второй можно получить из первого последовательностью стягиваний рёбер.
* {{якорь|суграф
}}'''Суграф''' ('''частичный граф''') исходного графа — граф, содержащий все вершины исходного графа и подмножество его ''[[#ребро|рёбер]]''. (ср. ''[[#подграф|Подграф]]''.)
* {{якорь|суперграф
}}'''Суперграф''' — любой граф, содержащий исходный граф (то есть для которого исходный граф является ''[[#подграф|подграфом]]'')

== Т ==
* {{якорь|тета-граф}}'''Тета-граф''' — граф, состоящий из объединения трёх путей, не имеющих внутри общих вершин, у которых конечные вершины одни и те же<ref>
{{книга
|автор=J. A. Bondy
|вклад=The "graph theory" of the Greek alphabet
|doi = 10.1007/BFb0067356
|mr = 0335362
|страницы= 43–54
|издательство=Springer
|серия=Lecture Notes in Mathematics
|заголовок=Graph theory and applications (Proc. Conf., Western Michigan Univ., Kalamazoo, Mich., 1972; dedicated to the memory of J. W. T. Youngs)
|том=303
|год=1972
}}</ref>
* '''Тета-граф''' множества точек евклидовой плоскости строится как система конусов, окружающих каждую вершину с добавлением ребра для каждого конуса к точке множества, проекция которой на центральную ось конуса минимальна.

* {{якорь|тождественный граф
}}'''[[Тождественный граф]]''' — граф, у которого возможен один-единственный ''[[#автоморфизм|автоморфизм]]'' — тождественный. Образно говоря, тождественный граф — «абсолютно несимметричный» граф.
* {{якорь|точка сочленения
}}'''Точка сочленения''' — то же, что и ''[[#шарнир|шарнир]]'' и ''[[#разделяющая вершина|разделяющая вершина]]''.
* {{якорь|триангуляция поверхности
}}'''Триангуляция поверхности''' — ''[[#укладка|укладка]]'' графа на [[поверхность]], разбивающая её на треугольные области; частный случай [[триангуляция (топология)|топологической триангуляции]].
* {{якорь|тривиальный граф
}}'''Тривиальный граф''' — граф, состоящий из одной ''[[#вершина|вершины]]''.
* {{якорь|турнирная таблица
}}'''[[Турнир (теория графов)|Турнир]]''' — ''[[#орграф|ориентированный граф]]'', в котором каждая пара вершин соединена одной дугой.

== У ==
* {{якорь|узел
}}'''Узел''' — то же, что и ''[[#вершина|Вершина]]''.
* {{якорь|укладка
}}'''Укладка''', или [[вложение графа]]: граф укладывается на некоторой поверхности, если его можно нарисовать на этой поверхности так, чтобы ''[[#ребро|рёбра]]'' графа при этом не пересекались. (См. ''[[#планарный граф|Планарный граф]]'', ''[[#плоский граф|Плоский граф]]''.)
* {{якорь|укрытие
}}'''[[Укрытие (теория графов)|Укрытие]]''' — определённый тип функции на множествах вершин неориентированного графа. Если укрытие существует, его может использовать беглец чтобы выиграть игру преследования-уклонения на графе путём использования этой функции на каждом шаге игры для определения безопасных множеств вершин, куда можно перейти.
* {{якорь|упорядоченный граф
}}'''[[Упорядоченный граф]]''' — граф, в котором рёбра, выходящие из каждой вершины, однозначно пронумерованы, начиная с 1. Рёбра считаются упорядоченными в порядке возрастания номеров. При графическом представлении часто рёбра считаются упорядоченными в порядке некоторого стандартного обхода (например, [[против часовой стрелки]]).

== Ф ==
* {{якорь|n-фактор
}}'''n-фактор''' графа — регулярный ''[[#остовный подграф|остовный подграф]]'' [[степень графа|степени]] <math>n</math>.
* {{якорь|n-факторизация
}}'''n-факторизация''' графа — разбиение графа на независимые ''[[#n-фактор|n-факторы]]''.

== Х ==
* {{якорь|хроматическое число
}}'''[[Хроматическое число]]''' графа — минимальное количество цветов, требуемое для [[раскраска графа|раскраски]] вершин графа, при которой любые вершины, соединенные ребром, раскрашены в разные цвета.
* {{якорь|характеристический многочлен
}}'''Характеристический многочлен''' графа — характеристический многочлен его [[Матрица смежности|матрицы смежности]].

== Ц ==
* {{якорь|центр графа
}}'''[[Центр графа]]''' — множество вершин <math>W = \left\{u_1,u_2,...,u_n\right\}</math>, для которых справедливо равенство: <math>\forall i=1,...,n : \varepsilon(u_i) = r(G)</math>, где <math>\varepsilon</math> — [[Глоссарий теории графов#эксцентриситет|эксцентриситет вершины]], а <math>r</math> — радиус графа.
* {{якорь|цепь
}}'''Цепь''' в графе — ''[[#маршрут|маршрут]]'', все рёбра которого различны. Если все ''[[#вершина|вершины]]'' (а тем самым и рёбра) различны, то такая цепь называется '''простой''' ('''элементарной'''). В цепи <math>v_0, e_1, ... , e_k, v_k</math> вершины <math>v_0</math> и <math>v_k</math> называются '''концами''' цепи. Цепь с концами ''u'' и ''v'' '''соединяет''' вершины ''u'' и ''v''. Цепь, соединяющая вершины ''u'' и ''v'', обозначается <math>\left\langle u,v\right\rangle</math>. Для ''[[#орграф|орграфов]]'' цепь называется орцепью.
*: <small> В некоторых источниках '''простая цепь''' — цепь, ''[[#ребро|рёбра]]'' которой различны, что является более слабым условием.</small>
* {{якорь|цикл в орграфе}}{{якорь|цикл
}}'''[[Цикл (теория графов)|Цикл]]''' — замкнутая ''[[#цепь|цепь]]''. Для ''[[#орграф|орграфов]]'' цикл называется ''[[#контур|контуром]]''.
** {{якорь|простой цикл в орграфе
}} '''Цикл''' ('''простой цикл''') в ''[[#орграф|орграфе]]'' — ''[[#простой путь|простой путь]]'' ''[[#длина пути|длины]]'' не менее 1, который начинается и заканчивается в одной и той же вершине.<!-- а чем это отличается от контура? --Incnis Mrsi -->
** {{якорь|цикл гамильтона
}} '''Цикл Гамильтона''' — то же, что и ''[[#гамильтонов цикл|Гамильтонов цикл]]''.
* {{якорь|цикломатическое число
}}'''[[Цикломатическое число графа]]''' — минимальное число рёбер, которые надо удалить, чтобы граф стал [[#ациклический граф|ациклическим]]. Для связного графа существует соотношение: <math>p_1(G) = p_0(G) + |E(G)| - |V(G)|,</math> где <math>p_1(G)</math> — цикломатическое число, <math>p_0</math> — число ''[[#компонента связности|компонент связности]]'' графа, <math>|E(G)|</math> — число ''[[#ребро|рёбер]]'', а <math>|V(G)|</math> — число ''[[#вершина|вершин]]''.

== Ч ==
* {{якорь|частичный граф
}}'''Частичный граф''' — то же, что и ''[[#суграф|суграф]]''.
* {{якорь|чётный граф
}}'''Чётный граф''' — то же, что и ''[[#двудольный граф|двудольный граф]]''.
*{{якорь|число вершинного покрытия
}}'''[[Число вершинного покрытия]]''' — размер наименьшего вершинного покрытия в графе.
*{{якорь|число независимости
}}'''[[Число независимости]]''' — размер наибольшего независимого множества вершин в графе.
*{{якорь|число паросочетания
}}'''[[Число паросочетания]]'''  — размер наибольшего паросочетания в графе.
*{{якорь|число рёберного покрытия
}}'''[[Число рёберного покрытия]]''' — размер наименьшего рёберного покрытия в графе.

== Ш ==
* {{якорь|шарнир
}}'''[[Шарнир (теория графов)|Шарнир]]''' — ''[[#вершина|вершина]] графа'', в результате удаления которой вместе со всеми ''[[#инцидентность|инцидентными]]'' ей ''[[#ребро|рёбрами]]'' количество ''[[#компонента связности|компонент связности]]'' в графе возрастает.
* {{якорь|шестерёнка
}}'''Шестерёнка''' (обозначается <math>G_n</math>) — граф, получаемый из [[#колесо|колеса]] путём размещения дополнительных вершин между каждой парой смежных вершин [[#периметр|периметра]]. Шестерёнки принадлежат семейству [[#рамочный граф|рамочных графов]] и играют важную роль при описании запрещённых подграфов рамочных графов<ref>{{статья
|заглавие=Combinatorics and geometry of finite and infinite squaregraphs
|автор=H.-J. Bandelt, V. Chepoi, D. Eppstein
|arxiv=0905.4537
|издание=[[SIAM Journal on Discrete Mathematics]]
|том=24
|выпуск=4
|страницы=1399–1440
|год=2010
|doi=10.1137/090760301}}.</ref>

== Э ==
* [[Эйлеров граф|{{якорь|эйлеров граф }}'''Эйлеров граф''']] — граф, в котором существует ''[[#цикл|цикл]]'', содержащий все рёбра графа по одному разу (вершины могут повторяться).
* {{якорь|эйлеров цикл
}}'''[[Эйлеров цикл|Эйлерова цепь]]''' (или '''[[эйлеров цикл]]''') — ''[[#цепь|цепь]]'' (''[[#цикл|цикл]]''), которая содержит все рёбра графа (вершины могут повторяться).
* {{якорь|эксцентриситет
}}'''Эксцентриситет''' вершины — максимальное из всех минимальных расстояний от других вершин до данной вершины.
* {{якорь|элементарный путь
}}'''Элементарный путь''' — ''[[#путь|путь]]'', вершины которого, за исключением, быть может, первой и последней, различны. Другими словами, простой путь не проходит дважды через одну вершину, но может начаться и закончиться в одной и той же вершине, в таком случае он называется ''[[#цикл|циклом]]'' (элементарным циклом).
* {{якорь|элементарное стягивание
}}'''Элементарным стягиванием''' называется такая процедура: берём ''[[#ребро|ребро]]'' (вместе с инцидентными ему ''[[#вершина|вершинами]]'', например, u и v) и «стягиваем» его, то есть удаляем ребро и отождествляем вершины u и v. Полученная при этом вершина инцидентна тем рёбрам (отличным от удалённого и друг друга), которым первоначально были инцидентны u или v.
* {{якорь|Энергия графа
}}'''[[Энергия графа]]''' — сумма абсолютных величин собственных значений матрицы смежности графа.

== Ссылки ==
* [http://pco.iis.nsk.su/grapp/ Толковый словарь по теории графов]
* [http://vuz.exponenta.ru/PDF/teogr.html Теория графов]
{{примечания}}

== Литература ==
* ''Дистель Р.'' Теория графов Пер. с англ. − Новосибирск: Изд-во Ин-та математики, 2002. − 336 c.
* {{книга
|автор         = Харари Ф.
|заглавие      = Теория графов
|ответственный =
|ссылка        =
|место         = {{М}}
|издательство = [[УРСС]]
|год = 2003
|том =
|страниц = 300
|страницы =
|isbn = 5-354-00301-6
}}

{{DEFAULTSORT:Графов теории глоссарий}}
[[Категория:Теория графов]]
[[Категория:Математические глоссарии]]