Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице).
- База графа — минимальное подмножество множества вершин графа, из которых достижима любая вершина графа.
- Бесконечный граф — граф, имеющий бесконечно много вершин и/или рёбер.
- Биграф — см. двудольный граф.
- Блок — граф без шарниров.
- Блок-дизайн с параметрами (v, k, λ) — покрытие с кратностью λ полного графа на v вершинах полными графами на k вершинах.
- Гамильтонов граф — граф, в котором есть гамильтонов цикл.
- Гамильтонов путь — простой путь в графе, содержащий все вершины графа ровно по одному разу.
- Гамильтонов цикл — простой цикл в графе, содержащий все вершины графа ровно по одному разу.
- Геометрическая реализация — фигура, вершинам которой соответствуют вершины графа, рёбрам — рёбра графа и рёбра в фигуре соединяют вершины, соответствующие вершинам в графе.
- Геометрический граф — плоская фигура из вершин — точек плоскости и рёбер — линий, соединяющих некоторые пары вершин. Может представлять многими способами всякий граф.
- Гиперграф — совокупность из множества вершин и множества гиперрёбер (подмножество n-й евклидовой степени множества вершин, то есть гиперрёбра соединяют произвольное количество вершин).
- Гомеоморфные графы — графы, получаемые из одного графа с помощью последовательности подразбиений рёбер.
- Грань — область, ограниченная рёбрами в плоском графе и не содержащая внутри себя вершин и рёбер графа. Внешняя часть плоскости тоже образует грань.
- Граф — базовое понятие. Включает множество вершин и множество рёбер, являющееся подмножеством декартова квадрата множества вершин (то есть каждое ребро соединяет ровно две вершины).
- Граф рода g — граф, который можно изобразить без пересечений на поверхности рода g и нельзя изобразить без пересечений ни на одной поверхности рода g-1. В частности, планарные графы имеют род 0.
- Двойственный граф. Граф А называется двойственным к планарному графу В, если вершины графа А соответствуют граням графа В, и две вершины графа A соединены ребром тогда и только тогда, когда соответствующие грани графа B имеют хотя бы одно общее ребро.
- Двудольный граф (или биграф, или чётный граф) — такой граф
, что множество вершин V разбито на два непересекающихся подмножества
и
, причём всякое ребро E инцидентно вершине из
и вершине из
(то есть соединяет вершину из
с вершиной из
). То есть правильная раскраска графа осуществляется двумя цветами. Множества
и
называются «долями» двудольного графа. Двудольный граф называется «полным», если любые две вершины из
и
являются смежными. Если
,
, то полный двудольный граф обозначается
.
- Двусвязный граф — связный граф, в котором нет шарниров.
- Дерево — связный граф, не содержащий циклов.
- Диаметр графа
— максимум расстояния между вершинами для всех пар вершин. Расстояние между вершинами — наименьшее число рёбер пути, соединяющего две вершины.
- Длина маршрута — количество рёбер в маршруте (с повторениями). Если маршрут
, то длина M равна k (обозначается
).
- Длина пути — число дуг пути (или сумма длин его дуг, если последние заданы). Так для пути v1, v2, …, vn длина равна n-1.
- Дуга — ориентированное ребро.
- Дополнение графа — граф над тем же множеством вершин, что и исходный, но вершины соединены ребром тогда и только тогда, когда в исходном графе ребра нет.
- Ежевика неориентированного графа G — семейство связных подграфов графа G, касающихся друг друга.
- Граф-звезда — полный двудольный граф
.
- Изолированная вершина — вершина, степень которой равна 0 (то есть нет рёбер, инцидентных ей).
- Изоморфизм. Два графа называются изоморфными, если существует перестановка вершин, при которой они совпадают. Иначе говоря, два графа называются изоморфными, если существует взаимно-однозначное соответствие между их вершинами и рёбрами, которое сохраняет смежность и инцидентность (графы отличаются только названиями своих вершин).
- Инвариант графа — числовая характеристика графа или их упорядоченный вектор, характеризующая структуру графа инвариантно относительно перенумерации вершин.
- Интервальный граф — граф, вершины которого могут быть взаимно однозначно поставлены в соответствие отрезкам на действительной оси таким образом, что две вершины инцидентны одному ребру тогда и только тогда, когда отрезки, соответствующие этим вершинам, пересекаются.
- Инцидентность — понятие, используемое только в отношении ребра или дуги и вершины: если
— вершины, а
— соединяющее их ребро, тогда вершина
и ребро
инцидентны, вершина
и ребро
тоже инцидентны. Две вершины (или два ребра) инцидентными быть не могут. Для обозначения ближайших вершин (рёбер) используется понятие смежности.
- Клетка — регулярный граф наименьшего обхвата для заданной степени вершин.
- Клика — подмножество вершин графа, полностью соединённых друг с другом, то есть подграф, являющийся полным графом.
- Кликовое число (англ. clique number) — число (G) вершин в наибольшей клике. Другие названия — густота, плотность.
- Максимальная клика — клика с максимально возможным числом вершин среди клик графа.
- Колесо (обозначается Wn) — граф с n вершинами (n ≥ 4), образованный соединением единственной вершины со всеми вершинами (n-1)-цикла.
- Колчан — просто ориентированный граф.
- Конечный граф — граф, содержащий конечное число вершин и рёбер.
- Конструктивное перечисление графов — получение полного списка графов в заданном классе.
- Компонента связности графа — такое подмножество вершин графа, для любых двух вершин которого существует путь из одной в другую, и не существует пути из вершины этого подмножества в вершину не из этого подмножества.
- Компонента сильной связности графа, слой — максимальное множество вершин ориентированного графа, такое, что для любых двух вершин из этого множества существует путь как из первой во вторую, так и из второй в первую.
- Контур — замкнутый путь в орграфе.
- Корень дерева — выбранная вершина дерева; в орграфе — вершина с нулевой степенью захода.
- Коцикл — минимальный разрез, минимальное множество рёбер, удаление которого делает граф несвязным.
- Кратные рёбра — несколько рёбер, инцидентных одной и той же паре вершин. Встречаются в мультиграфах.
- Кубический граф — регулярный граф степени 3, то есть граф, в котором каждой вершине инцидентно ровно три ребра.
- k-дольный граф — граф G, у которого хроматическое число c(G)=k
- k-связный граф — связный граф, в котором не существует набора
из
или менее вершин, такого, что удаление всех вершин
и инцидентных им рёбер нарушает связность графа. В частности, связный граф является 1-связным, а двусвязный — 2-связным.
- Лама́нов граф с n вершинами — такой граф G, что, во-первых, для каждого k любой подграф графа G, содержащий k вершин, имеет не более, чем 2k −3 ребра и, во-вторых, граф G имеет ровно 2n −3 ребра.
- Макси-код
— трудновычислимый полный инвариант графа, получаемый путём выписывания двоичных значений матрицы смежности в строчку с последующим переводом полученного двоичного числа в десятичную форму. Макси-коду соответствует такой порядок следования строк и столбцов, при котором полученное значение является максимально возможным.
- Максимальное паросочетание в графе. Паросочетание называется максимальным, если любое другое паросочетание содержит меньшее число рёбер.
- Маршрут в графе — чередующаяся последовательность вершин и рёбер
, в которой любые два соседних элемента инцидентны. Если
, то маршрут замкнут, иначе открыт.
- Матрица достижимости орграфа — матрица, содержащая информацию о существовании путей между вершинами в орграфе.
- Матрица инцидентности графа — матрица, значения элементов которой характеризуется инцидентностью соответствующих вершин графа (по вертикали) и его рёбер (по горизонтали). Для неориентированного графа элемент принимает значение 1, если соответствующие ему вершина и ребро инцидентны. Для ориентированного графа элемент принимает значение 1, если инцидентная вершина является началом ребра, значение -1, если инцидентная вершина является концом ребра; в остальных случаях (в том числе и для петель) значению элемента присваивается 0.
- Матрица смежности графа — матрица, значения элементов которой характеризуются смежностью вершин графа. При этом значению элемента матрицы присваивается количество рёбер, которые соединяют соответствующие вершины (то есть которые инцидентны обеим вершинам).
- Мини-код
— трудновычислимый полный инвариант графа, получаемый путём выписывания двоичных значений матрицы смежности в строчку с последующим переводом полученного двоичного числа в десятичную форму. Мини-коду соответствует такой порядок следования строк и столбцов, при котором полученное значение является минимально возможным.
- Минимальный каркас (или каркас минимального веса, минимальное остовное дерево) графа — ациклическое (не имеющее циклов) множество рёбер в связном, взвешенном и неориентированном графе, соединяющих между собой все вершины данного графа, при этом сумма весов всех рёбер в нём минимальна.
- Множество смежности вершины v — множество вершин, смежных с вершиной v. Обозначается
.
- Минором графа называется граф, который можно получить из исходного путём удаления и стягивания дуг.
- Мост — ребро, удаление которого увеличивает количество компонент связности в графе.
- Мультиграф — граф, в котором может быть пара вершин, которая соединена более чем одним ребром (ненаправленным), либо более чем двумя дугами противоположных направлений.
- Направленный граф — ориентированный граф, в котором две вершины соединяются не более чем одной дугой.
- Независимое множество вершин (известное также как внутренне устойчивое множество) — множество вершин графа G, в котором любые две вершины несмежны (никакая пара вершин не соединена ребром).
- Независимое множество называется максимальным, когда нет другого независимого множества, в которое оно бы входило. Дополнение наибольшего независимого множества называется минимальным вершинным покрытием графа.
- Наибольшим независимым множеством называется независимое множество наибольшего размера.
- Независимые вершины — попарно несмежные вершины графа.[1]
- Неразделимый граф — связный, непустой, не имеющий точек сочленения граф.[2].
- Нормированный граф — ориентированный граф без циклов.
- Нуль-граф (пустой граф) — граф без вершин.
- Обхват — длина наименьшего цикла в графе.
- Объединение графов (помеченных графов
и
) — граф
, множеством вершин которого является
, а множеством рёбер —
.
- Окрестность порядка k — множество вершин на расстоянии k от заданной вершины v; иногда толкуется расширительно как множество вершин, отстоящих от v на расстоянии не больше k.
- Окружение — множество вершин, смежных с заданной.
- Орграф, ориентированный граф G = (V,E) есть пара множеств, где V — множество вершин (узлов), E — множество дуг (ориентированных рёбер). Дуга — упорядоченная пара вершин (v, w), где вершину v называют началом, а w — концом дуги. Можно сказать, что дуга v → w ведёт от вершины v к вершине w, при этом вершина w смежная с вершиной v.
- Остовное дерево (остов) (неориентированного) связного графа
— всякий частичный граф
, являющийся деревом.
- Остовный подграф — подграф, содержащий все вершины.
- Паросочетание — набор попарно несмежных рёбер.
- Петля — ребро, начало и конец которого находятся в одной и той же вершине.
- Пересечение графов (помеченных графов
и
) — граф
, множеством вершин которого является
, а множеством рёбер —
.
- Перечисление графов — подсчёт числа неизоморфных графов в заданном классе (с заданными характеристиками).
- Периферийная вершина — вершина, эксцентриситет которой равен диаметру графа.
- Планарный граф — граф, который может быть изображён (уложен) на плоскости без пересечения рёбер. Изоморфен плоскому графу, то есть является графом с пересечениями, но допускающий его плоскую укладку, поэтому может отличаться от плоского графа изображением на плоскости. Таким образом, может быть разница между плоским графом и планарным графом при изображении на плоскости.
- Плоский граф — геометрический граф, в котором никакие два ребра не имеют общих точек, кроме инцидентной им обоим вершины (не пересекаются). Является уложенным графом на плоскости.
- Подграф исходного графа — граф, содержащий некое подмножество вершин данного графа и некое подмножество инцидентных им рёбер. (ср. Суграф.) По отношению к подграфу исходный граф называется суперграфом
- Полный граф — граф, в котором для каждой пары вершин
, существует ребро, инцидентное
и инцидентное
(каждая вершина соединена ребром с любой другой вершиной).
- Полный инвариант графа — числовая характеристика графа или их упорядоченный вектор, значения которой необходимо и достаточно для установления изоморфизма графов.
- Полным двудольным называется двудольный граф, в котором каждая вершина одного подмножества соединена ребром с каждой вершиной другого подмножества
- Полустепень захода в орграфе для вершины
— число дуг, входящих в вершину. Обозначается
,
,
или
.
- Полустепень исхода в орграфе для вершины
— число дуг, исходящих из вершины. Обозначается
,
,
или
.
- Помеченный граф — граф, вершинам или дугам которого присвоены какие-либо метки, например, натуральные числа или символы какого-нибудь алфавита.
- Порождённый подграф — подграф, порождённый множеством рёбер исходного графа. Содержит не обязательно все вершины графа, но эти вершины соединены такими же рёбрами, как в графе.
- Порядок графа — количество вершин графа.[3]
- Правильная раскраска графа — раскраска, при которой каждый цветной класс является независимым множеством. Иначе говоря, в правильной раскраске любые две смежные вершины должны иметь разные цвета.
- Произведение графов — для данных графов
и
произведением называется граф
, вершины которого
— декартово произведение множеств вершин исходных графов.
- Простая цепь — маршрут, в котором все вершины различны.
- Простой граф — граф, в котором нет кратных рёбер и петель.
- Простой путь — путь, все вершины которого попарно различны[4]. Другими словами, простой путь не проходит дважды через одну вершину.
- Простой цикл — цикл, не проходящий дважды через одну вершину.
- Псевдограф — граф, который может содержать петли и/или кратные рёбра.
- Пустой граф (нуль-граф) — граф без рёбер.
- Путь — последовательность рёбер (в неориентированном графе) и/или дуг (в ориентированном графе), такая, что конец одной дуги (ребра) является началом другой дуги (ребра). Или последовательность вершин и дуг (рёбер), в которой каждый элемент инцидентен предыдущему и последующему[4]. Может рассматриваться как частный случай маршрута.
- Путь в орграфе — последовательность вершин v1, v2, …, vn, для которой существуют дуги v1 → v2, v2 → v3, …, vn-1 → vn. Говорят, что этот путь начинается в вершине v1, проходит через вершины v2, v3, …, vn-1, и заканчивается в вершине vn.
- Радиус графа — минимальный из эксцентриситетов вершин связного графа; вершина, на которой достигается этот минимум, называется центральной вершиной.
- Разбиение графа — представление исходного графа в виде множества подмножеств вершин по определённым правилам.
- Разделяющая вершина — то же, что и шарнир и точка сочленения.
- Развёртка графа — функция, заданная на вершинах ориентированного графа.
- Размер графа — количество рёбер графа.
- Размеченный граф — граф, для которого задано множество меток S, функция разметки вершин f : A → S и функция разметки дуг g : R → S. Графически эти функции представляются надписыванием меток на вершинах и дугах. Множество меток может разделяться на два непересекающихся подмножества меток вершин и меток дуг.
- Разрез — множество рёбер, удаление которого делает граф несвязным.
- Рамочный граф — граф, который можно нарисовать на плоскости таким способом, что любая ограниченная грань является четырёхугольником и любая вершина с тремя и менее соседями инцидентна неограниченной грани.[5]
- Раскраска графа — разбиение вершин на множества (называемые цветами). Если при этом нет двух смежных вершин, принадлежащих одному и тому же множеству (то есть две смежные вершины всегда разного цвета), то такая раскраска называется правильной.
- Расстояние между вершинами — длина кратчайшей цепи (в орграфе пути), соединяющей заданные вершины. Если такой цепи (пути) не существует, расстояние полагается равным бесконечности.
- Рёберное покрытие — множество рёбер графа такое, что каждая вершина инцидентна хотя бы одному ребру из этого множества.
- Рёберный граф неориентированного графа — это граф, представляющий соседство рёбер графа.
- Ребро — базовое понятие. Ребро соединяет две вершины графа.
- Регулярный граф — граф, степени всех вершин которого равны. Степень регулярности является инвариантом графа и обозначается
. Для нерегулярных графов
не определено. Регулярные графы представляют особую сложность для многих алгоритмов.
- Регулярный граф степени 0 (вполне несвязный граф, пустой граф, нуль-граф) — граф без рёбер.
- Самодвойственный граф — граф, изоморфный своему двойственному графу.
- Сверхстройное (звездообразное) дерево — дерево, в котором имеется единственная вершина степени больше 2.
- Связность. Две вершины в графе связаны, если существует соединяющая их (простая) цепь.
- Связный граф — граф, в котором все вершины связаны.
- Сечение графа — множество рёбер, удаление которых делит граф на два изолированных подграфа, один из которых, в частности, может быть тривиальным графом.
- Сеть — в принципе, то же, что и граф, хотя сетями обычно называют графы, вершины которых определённым образом помечены.
- Ориентированная сеть — ориентированный граф, не содержащий контуров.
- Сильная связность. Две вершины в ориентированном графе сильно связаны, если существует путь из первой во вторую и из второй в первую.
- Сильно связный орграф — орграф, в котором все вершины сильно связаны.
- Смежность — понятие, используемое в отношении только двух рёбер либо только двух вершин: Два ребра, инцидентные одной вершине, называются смежными; две вершины, инцидентные одному ребру, также называются смежными. (ср. Инцидентность.)
- Смешанный граф — граф, содержащий как ориентированные, так и неориентированные рёбра.
- Совершенное паросочетание — паросочетание, содержащее все вершины графа.
- Соединением двух графов
и
, не имеющих общих вершин, называется граф
.[6]
Из определения видно, что соединение графов обладает свойствами коммутативности и ассоциативности
- Спектр графа — множество всех собственных значений матрицы смежности с учётом кратных рёбер.
- Степень вершины — количество рёбер графа G, инцидентных вершине x. Обозначается
. Минимальная степень вершины графа G обозначается
. а максимальная —
.
- Стягивание ребра графа — замена концов ребра одной вершиной, соседями новой вершины становятся соседи этих концов. Граф
стягиваем к
, если второй можно получить из первого последовательностью стягиваний рёбер.
- Суграф (частичный граф) исходного графа — граф, содержащий все вершины исходного графа и подмножество его рёбер. (ср. Подграф.)
- Суперграф — любой граф, содержащий исходный граф (то есть для которого исходный граф является подграфом)
- Тета-граф — граф, состоящий из объединения трёх путей, не имеющих внутри общих вершин, у которых конечные вершины одни и те же[7]
- Тета-граф множества точек евклидовой плоскости строится как система конусов, окружающих каждую вершину с добавлением ребра для каждого конуса к точке множества, проекция которой на центральную ось конуса минимальна.
- Узел — то же, что и Вершина.
- Укладка, или вложение графа: граф укладывается на некоторой поверхности, если его можно нарисовать на этой поверхности так, чтобы рёбра графа при этом не пересекались. (См. Планарный граф, Плоский граф.)
- Укрытие — определённый тип функции на множествах вершин неориентированного графа. Если укрытие существует, его может использовать беглец чтобы выиграть игру преследования-уклонения на графе путём использования этой функции на каждом шаге игры для определения безопасных множеств вершин, куда можно перейти.
- Упорядоченный граф — граф, в котором рёбра, выходящие из каждой вершины, однозначно пронумерованы, начиная с 1. Рёбра считаются упорядоченными в порядке возрастания номеров. При графическом представлении часто рёбра считаются упорядоченными в порядке некоторого стандартного обхода (например, против часовой стрелки).
- Хроматическое число графа — минимальное количество цветов, требуемое для раскраски вершин графа, при которой любые вершины, соединенные ребром, раскрашены в разные цвета.
- Характеристический многочлен графа — характеристический многочлен его матрицы смежности.
- Центр графа — множество вершин
, для которых справедливо равенство:
, где
— эксцентриситет вершины, а
— радиус графа.
- Цепь в графе — маршрут, все рёбра которого различны. Если все вершины (а тем самым и рёбра) различны, то такая цепь называется простой (элементарной). В цепи
вершины
и
называются концами цепи. Цепь с концами u и v соединяет вершины u и v. Цепь, соединяющая вершины u и v, обозначается
. Для орграфов цепь называется орцепью.
- В некоторых источниках простая цепь — цепь, рёбра которой различны, что является более слабым условием.
- Цикл — замкнутая цепь. Для орграфов цикл называется контуром.
- Цикломатическое число графа — минимальное число рёбер, которые надо удалить, чтобы граф стал ациклическим. Для связного графа существует соотношение:
где
— цикломатическое число,
— число компонент связности графа,
— число рёбер, а
— число вершин.
- Шарнир — вершина графа, в результате удаления которой вместе со всеми инцидентными ей рёбрами количество компонент связности в графе возрастает.
- Шестерёнка (обозначается
) — граф, получаемый из колеса путём размещения дополнительных вершин между каждой парой смежных вершин периметра. Шестерёнки принадлежат семейству рамочных графов и играют важную роль при описании запрещённых подграфов рамочных графов[8]
- Эйлеров граф — граф, в котором существует цикл, содержащий все рёбра графа по одному разу (вершины могут повторяться).
- Эйлерова цепь (или эйлеров цикл) — цепь (цикл), которая содержит все рёбра графа (вершины могут повторяться).
- Эксцентриситет вершины — максимальное из всех минимальных расстояний от других вершин до данной вершины.
- Элементарный путь — путь, вершины которого, за исключением, быть может, первой и последней, различны. Другими словами, простой путь не проходит дважды через одну вершину, но может начаться и закончиться в одной и той же вершине, в таком случае он называется циклом (элементарным циклом).
- Элементарным стягиванием называется такая процедура: берём ребро (вместе с инцидентными ему вершинами, например, u и v) и «стягиваем» его, то есть удаляем ребро и отождествляем вершины u и v. Полученная при этом вершина инцидентна тем рёбрам (отличным от удалённого и друг друга), которым первоначально были инцидентны u или v.
- Энергия графа — сумма абсолютных величин собственных значений матрицы смежности графа.
Дистель Р. Теория графов Пер. с англ. — Новосибирск: Изд-во Ин-та математики, 2002. — С. 17.
Харари Ф. Теория графов. — М.: Мир, 1972. — С. 41.
Дистель Р. Теория графов Пер. с англ. — Новосибирск: Изд-во Ин-та математики, 2002. — С. 16.
Кузнецов О. П., Адельсон-Вельский Г. М. / Дискретная математика для инженера. / М.: Энергия, 1980—344 с., ил. Стр. 120—122
А. В. Карзанов. Расширения конечных метрик и задача о размещении оборудования // Труды ИСА РАН. — 2007. — Т. 29. — С. 225—244 (241).
М. Б. Абросимов. О минимальных вершинных 1-расширениях соединений графов специального вида. // Прикладная теория графов.. — 2011. — Вып. 4.
J. A. Bondy. . — Springer, 1972. — Т. 303. — С. 43–54. — (Lecture Notes in Mathematics). — doi:10.1007/BFb0067356. H.-J. Bandelt, V. Chepoi, D. Eppstein. Combinatorics and geometry of finite and infinite squaregraphs // SIAM Journal on Discrete Mathematics. — 2010. — Т. 24, вып. 4. — С. 1399–1440. — doi:10.1137/090760301. — arXiv:0905.4537..
- Дистель Р. Теория графов Пер. с англ. − Новосибирск: Изд-во Ин-та математики, 2002. − 336 c.
- Харари Ф. Теория графов. — М.: УРСС, 2003. — 300 с. — ISBN 5-354-00301-6.