Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). __NOTOC__
А Автоморфизм — Изоморфизм графа с самим собой. Ациклический граф — граф без циклов.
Б База графа — минимальное подмножество множества вершин графа, из которых достижима любая вершина графа. Бесконечный граф — граф, имеющий бесконечно много вершин и/или рёбер. Биграф — см. двудольный граф. Блок — граф без шарниров. Блок-дизайн с параметрами (v, k, λ) — покрытие с кратностью λ полного графа на v вершинах полными графами на k вершинах.
В Валентность вершины — см. степень вершины. Вершина, узел — базовое понятие: точка, где могут сходиться/выходить рёбра и/или дуги. Множество вершин графа G обозначается V(G). Вершинное покрытие — множество вершин графа такое, что каждое ребро инцидентно хотя бы одной вершине из этого множества. Вес ребра — значение, поставленное в соответствие данному ребру взвешенного графа. Обычно вес — вещественное число, в таком случае его можно интерпретировать как «длину» ребра. Взвешенный граф — граф, каждому ребру которого поставлено в соответствие некое значение (вес ребра). См. Размеченный граф. Висячая вершина — вершина, степень которой равна 1 (то есть ).
Вполне несвязный граф — регулярный граф степени 0, то есть граф без рёбер. Высота дерева — наибольшая длина пути от корня к листу.
Г Гамильтонов граф — граф, в котором есть гамильтонов цикл. Гамильтонов путь — простой путь в графе, содержащий все вершины графа ровно по одному разу. Гамильтонов цикл — простой цикл в графе, содержащий все вершины графа ровно по одному разу. Геометрическая реализация — фигура, вершинам которой соответствуют вершины графа, рёбрам — рёбра графа и рёбра в фигуре соединяют вершины, соответствующие вершинам в графе. Геометрический граф — плоская фигура из вершин — точек плоскости и рёбер — линий, соединяющих некоторые пары вершин. Может представлять многими способами всякий граф. Гиперграф — совокупность из множества вершин и множества гиперрёбер (подмножество n-й евклидовой степени множества вершин, то есть гиперрёбра соединяют произвольное количество вершин). Гомеоморфные графы — графы, получаемые из одного графа с помощью последовательности подразбиений рёбер. Грань — область, ограниченная рёбрами в плоском графе и не содержащая внутри себя вершин и рёбер графа. Внешняя часть плоскости тоже образует грань. Граф — базовое понятие. Включает множество вершин и множество рёбер, являющееся подмножеством декартова квадрата множества вершин (то есть каждое ребро соединяет ровно две вершины). Граф рода g — граф, который можно изобразить без пересечений на поверхности рода g и нельзя изобразить без пересечений ни на одной поверхности рода g-1. В частности, планарные графы имеют род 0.
Д Двойственный граф. Граф А называется двойственным к планарному графу В, если вершины графа А соответствуют граням графа В, и две вершины графа A соединены ребром тогда и только тогда, когда соответствующие грани графа B имеют хотя бы одно общее ребро. Двудольный граф (или биграф, или чётный граф) — такой граф , что множество вершин V разбито на два непересекающихся подмножества и , причём всякое ребро E инцидентно вершине из и вершине из (то есть соединяет вершину из с вершиной из ). То есть правильная раскраска графа осуществляется двумя цветами. Множества и называются «долями» двудольного графа. Двудольный граф называется «полным», если любые две вершины из и являются смежными. Если , , то полный двудольный граф обозначается . Двусвязный граф — связный граф, в котором нет шарниров. Дерево — связный граф, не содержащий циклов. Диаметр графа — максимум расстояния между вершинами для всех пар вершин. Расстояние между вершинами — наименьшее число рёбер пути, соединяющего две вершины. Длина маршрута — количество рёбер в маршруте (с повторениями). Если маршрут , то длина M равна k (обозначается ). Длина пути — число дуг пути (или сумма длин его дуг, если последние заданы). Так для пути v1, v2, …, vn длина равна n-1. Дуга — ориентированное ребро. Дополнение графа — граф над тем же множеством вершин, что и исходный, но вершины соединены ребром тогда и только тогда, когда в исходном графе ребра нет.
Е Ежевика неориентированного графа G — семейство связных подграфов графа G, касающихся друг друга.
З Граф-звезда — полный двудольный граф .
И Изолированная вершина — вершина, степень которой равна 0 (то есть нет рёбер, инцидентных ей). Изоморфизм. Два графа называются изоморфными, если существует перестановка вершин, при которой они совпадают. Иначе говоря, два графа называются изоморфными, если существует взаимно-однозначное соответствие между их вершинами и рёбрами, которое сохраняет смежность и инцидентность (графы отличаются только названиями своих вершин). Инвариант графа — числовая характеристика графа или их упорядоченный вектор, характеризующая структуру графа инвариантно относительно перенумерации вершин. Интервальный граф — граф, вершины которого могут быть взаимно однозначно поставлены в соответствие отрезкам на действительной оси таким образом, что две вершины инцидентны одному ребру тогда и только тогда, когда отрезки, соответствующие этим вершинам, пересекаются. Инцидентность — понятие, используемое только в отношении ребра или дуги и вершины: если — вершины, а — соединяющее их ребро, тогда вершина и ребро инцидентны, вершина и ребро тоже инцидентны. Две вершины (или два ребра) инцидентными быть не могут. Для обозначения ближайших вершин (рёбер) используется понятие смежности.
К Клетка — регулярный граф наименьшего обхвата для заданной степени вершин. Клика — подмножество вершин графа, полностью соединённых друг с другом, то есть подграф, являющийся полным графом. Кликовое число () — число (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 ребра.
Лес — неориентированный граф без циклов. Компонентами связности леса являются деревья. Лист дерева — вершина дерева с единственным ребром или входящей дугой. Локальная степень вершины — число рёбер, ей инцидентных. Петля даёт вклад, равный «2», в степень вершины.
М Макси-код — трудновычислимый полный инвариант графа, получаемый путём выписывания двоичных значений матрицы смежности в строчку с последующим переводом полученного двоичного числа в десятичную форму. Макси-коду соответствует такой порядок следования строк и столбцов, при котором полученное значение является максимально возможным. Максимальное паросочетание в графе. Паросочетание называется максимальным, если любое другое паросочетание содержит меньшее число рёбер. Маршрут в графе — чередующаяся последовательность вершин и рёбер , в которой любые два соседних элемента инцидентны. Если , то маршрут замкнут, иначе открыт. Матрица достижимости орграфа — матрица, содержащая информацию о существовании путей между вершинами в орграфе. Матрица инцидентности графа — матрица, значения элементов которой характеризуется инцидентностью соответствующих вершин графа (по вертикали) и его рёбер (по горизонтали). Для неориентированного графа элемент принимает значение 1, если соответствующие ему вершина и ребро инцидентны. Для ориентированного графа элемент принимает значение 1, если инцидентная вершина является началом ребра, значение -1, если инцидентная вершина является концом ребра; в остальных случаях (в том числе и для петель) значению элемента присваивается 0. Матрица смежности графа — матрица, значения элементов которой характеризуются смежностью вершин графа. При этом значению элемента матрицы присваивается количество рёбер, которые соединяют соответствующие вершины (то есть которые инцидентны обеим вершинам). Мини-код — трудновычислимый полный инвариант графа, получаемый путём выписывания двоичных значений матрицы смежности в строчку с последующим переводом полученного двоичного числа в десятичную форму. Мини-коду соответствует такой порядок следования строк и столбцов, при котором полученное значение является минимально возможным. Минимальный каркас (или каркас минимального веса, минимальное остовное дерево) графа — ациклическое (не имеющее циклов) множество рёбер в связном, взвешенном и неориентированном графе, соединяющих между собой все вершины данного графа, при этом сумма весов всех рёбер в нём минимальна. Множество смежности вершины v — множество вершин, смежных с вершиной v. Обозначается . Минором графа называется граф, который можно получить из исходного путём удаления и стягивания дуг. Мост — ребро, удаление которого увеличивает количество компонент связности в графе. Мультиграф — граф, в котором может быть пара вершин, которая соединена более чем одним ребром (ненаправленным), либо более чем двумя дугами противоположных направлений.
Н Направленный граф — ориентированный граф, в котором две вершины соединяются не более чем одной дугой. Направленный ациклический граф — ориентированный граф без контуров. Независимое множество вершин (известное также как внутренне устойчивое множество) — множество вершин графа G, в котором любые две вершины несмежны (никакая пара вершин не соединена ребром). Независимое множество называется максимальным, когда нет другого независимого множества, в которое оно бы входило. Дополнение наибольшего независимого множества называется минимальным вершинным покрытием графа. Наибольшим независимым множеством называется независимое множество наибольшего размера. Независимые вершины — попарно несмежные вершины графа. Дистель Р. Теория графов Пер. с англ. — Новосибирск: Изд-во Ин-та математики, 2002. — С. 17. Неразделимый граф — связный, непустой, не имеющий точек сочленения граф.Харари Ф. Теория графов. — М.: Мир, 1972. — С. 41.. Нормированный граф — ориентированный граф без циклов.
Нуль-граф (пустой граф) — граф без вершин.
О Обхват — длина наименьшего цикла в графе.
Объединение графов (помеченных графов и ) — граф , множеством вершин которого является , а множеством рёбер — . Окрестность порядка k — множество вершин на расстоянии k от заданной вершины v; иногда толкуется расширительно как множество вершин, отстоящих от v на расстоянии не больше k. Окружение — множество вершин, смежных с заданной.