Глоссарий теории графов

Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице).

• Автоморфизм — Изоморфизм графа с самим собой.
• Ациклический граф — граф без циклов.

• База графа — минимальное подмножество множества вершин графа, из которых достижима любая вершина графа.
• Бесконечный граф — граф, имеющий бесконечно много вершин и/или рёбер.
• Биграф — см. двудольный граф.
• Блок — граф без шарниров.
• Блок-дизайн с параметрами (v, k, λ) — покрытие с кратностью λ полного графа на v вершинах полными графами на k вершинах.

• Валентность вершины — см. степень вершины.
• Вершина, узел — базовое понятие: точка, где могут сходиться/выходить рёбра и/или дуги. Множество вершин графа G обозначается V(G).
• Вершинное покрытие — множество вершин графа такое, что каждое ребро инцидентно хотя бы одной вершине из этого множества.
• Вес ребра — значение,
  поставленное в соответствие данному ребру взвешенного графа. Обычно вес — вещественное число, в таком случае его можно интерпретировать как «длину
  » ребра.
• Взвешенный граф —
  поставлено в соответствие некое значение (вес ребра). См. Размеченный граф
  .
• Висячая вершина — вершина, степень которой равна 1 (то есть ${\displaystyle d(v)=1}$).

• Вполне несвязный граф — регулярный граф степени 0, то есть граф без рёбер.
• Высота дерева — наибольшая длина пути от корня к листу.

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

• Двойственный граф. Граф А называется двойственным к планарному графу В, если вершины графа А соответствуют граням графа В, и две вершины графа A соединены ребром тогда и только тогда, когда соответствующие грани графа B имеют хотя бы одно общее ребро.
• Двудольный граф (или биграф, или чётный граф) — такой граф ${\displaystyle G(V,E)}$, что множество вершин V разбито на два непересекающихся подмножества ${\displaystyle V_{1}}$ и ${\displaystyle V_{2}}$, причём всякое ребро E инцидентно вершине из ${\displaystyle V_{1}}$ и вершине из ${\displaystyle V_{2}}$ (то есть соединяет вершину из ${\displaystyle V_{1}}$ с вершиной из ${\displaystyle V_{2}}$). То есть правильная раскраска графа осуществляется двумя цветами. Множества ${\displaystyle V_{1}}$ и ${\displaystyle V_{2}}$ называются «долями» двудольного графа. Двудольный граф называется «полным», если любые две вершины из ${\displaystyle V_{1}}$ и ${\displaystyle V_{2}}$ являются смежными. Если ${\displaystyle \left|V_{1}\right|=a}$, ${\displaystyle \left|V_{2}\right|=b}$, то полный двудольный граф обозначается ${\displaystyle K_{a,b}}$.
• Двусвязный граф — связный граф, в котором нет шарниров.
• Дерево — связный граф, не содержащий циклов.
• Диаметр графа
  ${\displaystyle \mathrm {diam} (G)}$ — максимум расстояния между вершинами для всех пар вершин. Расстояние между вершинами — наименьшее число рёбер пути, соединяющего две вершины.
• Длина маршрута — количество рёбер в маршруте (с повторениями). Если маршрут ${\displaystyle M=v_{0},e_{1},v_{1},e_{2},v_{2},...,e_{k},v_{k}}$, то длина M равна k (обозначается ${\displaystyle \left|M\right|=k}$).
• Длина пути — число дуг пути (или сумма длин его дуг, если последние заданы). Так для пути v₁, v₂, …, v_n длина равна n-1.
• Дуга — ориентированное ребро.
• Дополнение графа — граф над тем же множеством вершин, что и исходный, но вершины соединены ребром тогда и только тогда, когда в исходном графе ребра нет.

• Ежевика неориентированного графа G — семейство связных подграфов графа G, касающихся друг друга.

• Граф-звезда — полный двудольный граф ${\displaystyle K_{1,b}}$.

• Изолированная вершина — вершина, степень которой равна 0 (то есть нет рёбер, инцидентных ей).
• Изоморфизм. Два графа называются изоморфными, если существует перестановка вершин, при которой они совпадают. Иначе говоря, два графа называются изоморфными, если существует взаимно-однозначное соответствие между их вершинами и рёбрами, которое сохраняет смежность и инцидентность (графы отличаются только названиями своих вершин).
• Инвариант графа — числовая характеристика графа или их упорядоченный вектор, характеризующая структуру графа инвариантно относительно перенумерации вершин.
• Интервальный граф — граф, вершины которого могут быть взаимно однозначно поставлены в соответствие отрезкам на действительной оси таким образом, что две вершины инцидентны одному ребру тогда и только тогда, когда отрезки, соответствующие этим вершинам, пересекаются.
• Инцидентность — понятие, используемое только в отношении ребра или дуги и вершины: если ${\displaystyle v_{1},v_{2}}$ — вершины, а ${\displaystyle e=(v_{1},v_{2})}$ — соединяющее их ребро, тогда вершина ${\displaystyle v_{1}}$ и ребро ${\displaystyle e}$ инцидентны, вершина ${\displaystyle v_{2}}$ и ребро ${\displaystyle e}$ тоже инцидентны. Две вершины (или два ребра) инцидентными быть не могут. Для обозначения ближайших вершин (рёбер) используется понятие смежности.

• Клетка — регулярный граф наименьшего обхвата для заданной степени вершин.
• Клика — подмножество вершин графа, полностью соединённых друг с другом, то есть подграф, являющийся полным графом.
  • Кликовое число (англ. clique number) — число (G) вершин в наибольшей клике. Другие названия — густота, плотность.
  • Максимальная клика — клика с максимально возможным числом вершин среди клик графа.
• Колесо (обозначается W_n) — граф с n вершинами (n ≥ 4), образованный соединением единственной вершины со всеми вершинами (n-1)-цикла.
• Колчан — просто ориентированный граф.
• Конечный граф — граф, содержащий конечное число вершин и рёбер.
• Конструктивное перечисление графов — получение полного списка графов в заданном классе.
• Компонента связности графа — такое подмножество вершин графа, для любых двух вершин которого существует путь из одной в другую, и не существует пути из вершины этого подмножества в вершину не из этого подмножества.
• Компонента сильной связности графа, слой — максимальное множество вершин ориентированного графа, такое, что для любых двух вершин из этого множества существует путь
  как из первой во вторую, так и из второй в первую.
• Контур — замкнутый путь в орграфе.
• Корень дерева — выбранная вершина дерева; в орграфе — вершина с нулевой степенью захода.
• Коцикл — минимальный разрез, минимальное множество рёбер, удаление которого делает граф несвязным.
• Кратные рёбра — несколько рёбер, инцидентных одной и той же паре вершин. Встречаются в мультиграфах.
• Кубический граф — регулярный граф степени 3, то есть граф, в котором каждой вершине инцидентно ровно три ребра.
• k-дольный граф — граф G, у которого хроматическое число c(G)=k
• k-связный граф — связный граф, в котором не существует набора ${\displaystyle V'}$ из ${\displaystyle k-1}$ или менее вершин, такого, что удаление всех вершин ${\displaystyle V'}$ и инцидентных им рёбер нарушает связность графа. В частности, связный граф является 1-связным, а двусвязный — 2-связным.

• Лама́нов граф с n вершинами — такой граф G, что, во-первых, для каждого k любой подграф графа G, содержащий k вершин, имеет не более, чем 2k −3 ребра и, во-вторых, граф G имеет ровно 2n −3 ребра.

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

• Макси-код ${\displaystyle \mu _{max}}$ — трудновычислимый
  полный инвариант графа, получаемый путём выписывания двоичных значений матрицы смежности в строчку с последующим переводом полученного двоичного числа
  в десятичную форму. Макси-коду соответствует такой порядок следования строк и столбцов, при котором полученное значение является максимально возможным.
• Максимальное паросочетание в графе. Паросочетание называется максимальным, если любое другое паросочетание содержит меньшее число рёбер.
• Маршрут в графе — чередующаяся последовательность вершин и рёбер ${\displaystyle v_{0},e_{1},v_{1},e_{2},v_{2},...,e_{k},v_{k}}$, в которой любые два соседних элемента инцидентны. Если ${\displaystyle v_{0}=v_{k}}$, то маршрут замкнут, иначе открыт.
• Матрица достижимости орграфа — матрица, содержащая информацию о существовании путей между вершинами в орграфе.
• Матрица инцидентности графа — матрица, значения элементов которой характеризуется инцидентностью соответствующих вершин графа (по вертикали) и его рёбер (по горизонтали). Для неориентированного графа элемент принимает значение 1, если соответствующие ему вершина и ребро инцидентны. Для ориентированного графа элемент принимает значение 1, если инцидентная вершина является началом ребра, значение -1, если инцидентная вершина является концом ребра; в остальных случаях (в том числе и для петель) значению элемента присваивается 0.
• Матрица смежности графа — матрица, значения элементов которой характеризуются смежностью вершин графа. При этом значению элемента матрицы присваивается количество рёбер, которые соединяют соответствующие вершины (то есть которые инцидентны обеим вершинам).
• Мини-код ${\displaystyle \mu _{min}}$ — трудновычислимый
  полный инвариант графа, получаемый путём выписывания двоичных значений матрицы смежности в строчку с последующим переводом полученного двоичного числа
  в десятичную форму. Мини-коду соответствует такой порядок следования строк и столбцов, при котором полученное значение является минимально возможным.
• Минимальный каркас
  (или каркас минимального веса, минимальное остовное дерево) графа — ациклическое (не имеющее циклов) множество рёбер в связном, взвешенном и неориентированном графе, соединяющих между собой все вершины данного графа, при этом сумма весов всех рёбер в нём минимальна.
• Множество смежности вершины v — множество вершин, смежных с вершиной v. Обозначается ${\displaystyle \Gamma ^{+}(v)}$.
• Минором графа называется граф, который можно получить из исходного путём удаления и стягивания дуг.
• Мост — ребро, удаление которого увеличивает количество компонент связности в графе.
• Мультиграф — граф, в котором может быть пара вершин, которая соединена более чем одним ребром (ненаправленным), либо более чем двумя дугами противоположных направлений.

• Направленный граф — ориентированный граф, в котором две вершины соединяются не более чем одной дугой.
  • Направленный ациклический граф — ориентированный граф без контуров
    .
• Независимое множество вершин (известное также как внутренне устойчивое множество) — множество вершин графа G, в котором любые две вершины несмежны (никакая пара вершин не соединена ребром).
  • Независимое множество называется максимальным, когда нет другого независимого множества, в которое оно бы входило. Дополнение наибольшего независимого множества называется минимальным вершинным покрытием графа.
  • Наибольшим независимым множеством называется независимое множество наибольшего размера.
• Независимые вершины — попарно несмежные вершины графа.^[1]
• Неразделимый граф — связный, непустой, не имеющий точек сочленения граф.^[2].
• Нормированный граф — ориентированный граф без циклов.

• Нуль-граф (пустой граф) — граф без вершин.

• Обхват — длина наименьшего цикла в графе.
• Объединение графов (помеченных графов ${\displaystyle G_{1}=(X_{1},U_{1})}$ и ${\displaystyle G_{2}=(X_{2},U_{2})}$) — граф ${\displaystyle G_{1}\cup G_{2}}$, множеством вершин которого является ${\displaystyle X_{1}\cup X_{2}}$, а множеством рёбер — ${\displaystyle U=U_{1}\cup U_{2}}$.
• Окрестность порядка k — множество вершин на расстоянии k от заданной вершины v; иногда толкуется расширительно как множество вершин, отстоящих от v на расстоянии не больше k.
• Окружение — множество вершин, смежных с заданной.
• Орграф
  , ориентированный граф G = (V,E) есть пара множеств, где V — множество вершин (узлов), E — множество дуг (ориентированных рёбер). Дуга — упорядоченная пара вершин (v, w), где вершину v называют началом, а w — концом дуги. Можно сказать, что дуга v → w ведёт от вершины v к вершине w, при этом вершина w смежная с вершиной v.
• Остовное дерево (остов) (неориентированного) связного графа ${\displaystyle G=(V,E)}$ — всякий частичный граф ${\displaystyle S=(V,T)}$, являющийся деревом.
• Остовный подграф — подграф, содержащий все вершины.

• Паросочетание — набор попарно несмежных рёбер.
• Петля — ребро, начало и конец которого находятся в одной и той же вершине.
• Пересечение графов (помеченных графов ${\displaystyle G_{1}=(X_{1},U_{1})}$ и ${\displaystyle G_{2}=(X_{2},U_{2})}$) — граф ${\displaystyle G_{1}\cap G_{2}}$, множеством вершин которого является ${\displaystyle X_{1}\cap X_{2}}$, а множеством рёбер — ${\displaystyle U=U_{1}\cap U_{2}}$.
• Перечисление графов — подсчёт числа неизоморфных графов в заданном классе (с заданными характеристиками).
• Периферийная вершина — вершина, эксцентриситет которой равен диаметру графа.
• Планарный граф — граф, который может быть изображён (уложен) на плоскости без пересечения рёбер. Изоморфен плоскому графу, то есть является графом с пересечениями, но допускающий его плоскую укладку, поэтому может отличаться от плоского графа изображением на плоскости. Таким образом, может быть разница между плоским графом и планарным графом при изображении на плоскости.
• Плоский граф — геометрический граф, в котором никакие два ребра не имеют общих точек, кроме инцидентной им обоим вершины (не пересекаются). Является уложенным
  графом на плоскости.
• Подграф исходного графа — граф, содержащий некое подмножество вершин данного графа и некое подмножество инцидентных им рёбер. (ср. Суграф.) По отношению к подграфу исходный граф называется суперграфом
• Полный граф — граф, в котором для каждой пары вершин ${\displaystyle v_{1},v_{2}}$, существует ребро, инцидентное ${\displaystyle v_{1}}$ и инцидентное ${\displaystyle v_{2}}$ (каждая вершина соединена ребром с любой другой вершиной).
• необходимо и достаточно для установления изоморфизма
  графов.
• Полным двудольным называется двудольный граф, в котором каждая вершина одного подмножества соединена ребром с каждой вершиной другого подмножества
• Полустепень захода в орграфе для вершины ${\displaystyle v}$ — число дуг, входящих в вершину. Обозначается ${\displaystyle d^{+}(v)}$, ${\displaystyle \mathrm {deg} ^{+}(v)}$, ${\displaystyle \mathrm {indeg} (v)}$ или ${\displaystyle d_{t}(v)}$.
• Полустепень исхода в орграфе для вершины ${\displaystyle v}$ — число дуг, исходящих из вершины. Обозначается ${\displaystyle d^{-}(v)}$, ${\displaystyle \mathrm {deg} ^{-}(v)}$, ${\displaystyle \mathrm {outdeg} (v)}$ или ${\displaystyle d_{o}(v)}$.
• Помеченный граф
   — граф, вершинам или дугам которого присвоены какие-либо метки, например, натуральные числа или символы какого-нибудь алфавита.
• Порождённый подграф — подграф, порождённый подмножеством вершин и множеством всех рёбер исходного графа, которые соединяют вершины из заданного подмножества. Содержит не обязательно все вершины графа, но эти вершины соединены такими же рёбрами, как в графе.
• Порядок графа — количество вершин графа.^[3]
• раскраска
  , при которой каждый цветной класс является независимым множеством. Иначе говоря, в правильной раскраске любые две смежные вершины должны иметь разные цвета.
• Произведение графов — для данных графов ${\displaystyle G_{1}=(V_{1},E_{1})}$ и ${\displaystyle G_{2}=(V_{2},E_{2})}$ произведением называется граф ${\displaystyle G=(V,E)}$, вершины которого ${\displaystyle V(G)=V_{1}\times V_{2}}$ — декартово произведение множеств вершин исходных графов.
• Простая цепь — маршрут, в котором все вершины различны.
• Простой граф — граф, в котором нет кратных рёбер и петель
  .
• Простой путь — путь, все вершины которого попарно различны^[4]. Другими словами, простой путь не проходит дважды через одну вершину.
  • Простой цикл — цикл, не проходящий дважды через одну вершину.
• Псевдограф — граф, который может содержать петли и/или кратные рёбра.