Гамильтонов путь
—
в графе, содержащий все
графа ровно по одному разу.
Гамильтонов цикл
—
в графе, содержащий все вершины графа ровно по одному разу.
Геометрическая реализация
— фигура, вершинам которой соответствуют вершины графа, рёбрам — рёбра графа и рёбра в фигуре соединяют вершины, соответствующие вершинам в графе.
Геометрический граф
— плоская фигура из вершин — точек плоскости и рёбер — линий, соединяющих некоторые пары вершин. Может представлять многими способами всякий граф.
Гиперграф
— совокупность из множества вершин и множества гиперрёбер (подмножество n-й евклидовой степени множества вершин, то есть гиперрёбра соединяют произвольное количество вершин).
Гомеоморфные графы
— графы, получаемые из одного графа с помощью последовательности подразбиений рёбер.
Грань
— область, ограниченная рёбрами в
и не содержащая внутри себя вершин и рёбер графа. Внешняя часть плоскости тоже образует грань.
Граф
— базовое понятие. Включает множество
и множество
, являющееся
подмножеством
декартова квадрата
множества вершин (то есть каждое ребро соединяет ровно две вершины).
Граф рода
g
— граф, который можно изобразить без пересечений на
поверхности рода
g
и нельзя изобразить без пересечений ни на одной поверхности рода
g
-1. В частности,
имеют род 0.
Д
Двойственный граф
. Граф
А
называется двойственным к планарному графу
В
, если вершины графа
А
соответствуют
графа
В
, и две вершины графа
A
соединены ребром тогда и только тогда, когда соответствующие грани графа
B
имеют хотя бы одно общее ребро.
Двудольный граф
(или
биграф
, или
чётный граф
) — такой граф
, что множество вершин
V
разбито на два непересекающихся подмножества
и
, причём всякое ребро
E
инцидентно вершине из
и вершине из
(то есть соединяет вершину из
с вершиной из
). То есть
осуществляется двумя цветами. Множества
и
называются «долями» двудольного графа. Двудольный граф называется «полным», если любые две вершины из
и
являются смежными. Если
,
, то полный двудольный граф обозначается
.
Диаметр графа
— максимум расстояния между вершинами для всех пар вершин. Расстояние между вершинами — наименьшее число рёбер
, соединяющего две вершины.
Длина
— количество рёбер в маршруте (с повторениями). Если маршрут
, то длина
M
равна
k
(обозначается
).
Длина
— число дуг пути (или сумма длин его дуг, если последние заданы). Так для пути v
1
, v
2
, …, v
n
длина равна n-1.
Дуга
— ориентированное
.
Дополнение графа
— граф над тем же множеством вершин, что и исходный, но вершины соединены ребром тогда и только тогда, когда в исходном графе ребра нет.
Е
Ежевика
неориентированного графа
G
— семейство связных подграфов графа
G
, касающихся друг друга.
Изолированная вершина
— вершина,
которой равна 0 (то есть нет рёбер,
ей).
Изоморфизм
. Два графа называются
изоморфными
, если существует перестановка вершин, при которой они совпадают. Иначе говоря, два графа называются
изоморфными
, если существует взаимно-однозначное соответствие между их вершинами и рёбрами, которое сохраняет
и
(графы отличаются только названиями своих вершин).
Инвариант графа
— числовая характеристика графа или их упорядоченный вектор, характеризующая структуру графа инвариантно относительно перенумерации вершин.
Интервальный граф
— граф, вершины которого могут быть взаимно однозначно поставлены в соответствие отрезкам на действительной оси таким образом, что две вершины
одному ребру тогда и только тогда, когда отрезки, соответствующие этим вершинам, пересекаются.
Инцидентность
— понятие, используемое только в отношении ребра или дуги и вершины: если
— вершины, а
— соединяющее их ребро, тогда вершина
и ребро
инцидентны, вершина
и ребро
тоже инцидентны. Две вершины (или два ребра) инцидентными быть не могут. Для обозначения ближайших вершин (рёбер) используется понятие
.
Клика
— подмножество вершин графа, полностью соединённых друг с другом, то есть подграф, являющийся
.
Кликовое число
(
англ.
clique number
) — число (G) вершин в наибольшей клике.
Другие названия — густота, плотность.
Максимальная клика
— клика с максимально возможным числом вершин среди клик графа.
Колесо
(обозначается
W
n
) — граф с
n
вершинами (n ≥ 4), образованный соединением единственной вершины со всеми вершинами (
n
-1)-цикла.
— просто ориентированный граф.
Конечный граф
— граф, содержащий конечное число вершин и рёбер.
Конструктивное перечисление графов
— получение полного списка графов в заданном классе.
Компонента связности графа
— такое
подмножество
, для любых двух вершин которого существует
из одной в другую, и не существует пути из вершины этого подмножества в вершину не из этого подмножества.
Компонента сильной связности графа
,
слой
— максимальное множество вершин
, такое, что для любых двух вершин из этого множества существует
как из первой во вторую, так и из второй в первую.
Контур
— замкнутый
.
Корень дерева
— выбранная
; в
— вершина с нулевой степенью захода.
Коцикл
— минимальный
, минимальное множество рёбер, удаление которого делает граф несвязным.
Кратные рёбра
— несколько
,
одной и той же паре вершин. Встречаются в
.
Кубический граф
— регулярный граф степени 3, то есть граф, в котором каждой вершине инцидентно ровно три ребра.
—
, в котором не существует набора
из
или менее
, такого, что удаление всех вершин
и инцидентных им
нарушает связность графа. В частности,
является 1-связным, а
— 2-связным.
Л
Лама́нов граф
с
n
вершинами — такой граф
G
, что, во-первых, для каждого
k
любой подграф графа
G
, содержащий
k
вершин, имеет не более, чем 2
k
−3 ребра и, во-вторых, граф
G
имеет ровно 2
n
−3 ребра.
Лес
— неориентированный граф без циклов.
леса являются
.
Лист дерева
—
с единственным
или входящей
.
Локальная степень вершины
— число рёбер, ей инцидентных. Петля даёт вклад, равный «2», в степень вершины.
М
Макси-код
— трудновычислимый
полный инвариант графа
, получаемый путём выписывания двоичных значений
матрицы смежности
в строчку с последующим переводом полученного
двоичного числа
в десятичную форму. Макси-коду соответствует такой порядок следования строк и столбцов, при котором полученное значение является максимально возможным.
Максимальное паросочетание
в графе. Паросочетание называется максимальным, если любое другое паросочетание содержит меньшее число рёбер.
Маршрут
в графе — чередующаяся последовательность вершин и рёбер
, в которой любые два соседних элемента
. Если
, то маршрут
замкнут
, иначе
открыт
.
Матрица достижимости
орграфа — матрица, содержащая информацию о существовании путей между вершинами в орграфе.
Матрица инцидентности
графа — матрица, значения элементов которой характеризуется инцидентностью соответствующих вершин графа (по вертикали) и его рёбер (по горизонтали). Для неориентированного графа элемент принимает значение
1
, если соответствующие ему вершина и ребро инцидентны. Для
графа элемент принимает значение
1
, если инцидентная вершина является началом ребра, значение
-1
, если инцидентная вершина является концом ребра; в остальных случаях (в том числе и для
) значению элемента присваивается
0
.
Матрица смежности
графа — матрица, значения элементов которой характеризуются смежностью вершин графа. При этом значению элемента матрицы присваивается количество рёбер, которые соединяют соответствующие вершины (то есть которые
обеим вершинам).
Мини-код
— трудновычислимый
полный инвариант графа
, получаемый путём выписывания двоичных значений
матрицы смежности
в строчку с последующим переводом полученного
двоичного числа
в десятичную форму. Мини-коду соответствует такой порядок следования строк и столбцов, при котором полученное значение является минимально возможным.
Минимальный каркас
(или
каркас минимального веса
,
минимальное остовное дерево
) графа — ациклическое (не имеющее циклов) множество рёбер в связном, взвешенном и неориентированном графе, соединяющих между собой все вершины данного графа, при этом сумма весов всех рёбер в нём минимальна.
Множество смежности
вершины
v
— множество вершин, смежных с вершиной
v
. Обозначается
.
Минором графа
называется граф, который можно получить из исходного путём удаления и стягивания дуг.
Мост
—
, удаление которого увеличивает количество
в графе.
Мультиграф
— граф, в котором может быть пара вершин, которая соединена более чем одним ребром (ненаправленным), либо более чем двумя дугами противоположных направлений.
Н
Направленный граф
—
, в котором две вершины соединяются не более чем одной дугой.
Независимое множество вершин
(известное также как
внутренне устойчивое множество
) — множество вершин графа G, в котором любые две вершины несмежны (никакая пара вершин не соединена ребром).
Независимое множество называется
максимальным
, когда нет другого независимого множества, в которое оно бы входило. Дополнение наибольшего независимого множества называется
минимальным вершинным покрытием
графа.
Наибольшим независимым множеством
называется независимое множество наибольшего размера.
Объединение графов
(помеченных графов
и
) — граф
, множеством вершин которого является
, а множеством рёбер —
.
Окрестность порядка
k
— множество вершин на расстоянии
k
от заданной вершины
v
; иногда толкуется расширительно как множество вершин, отстоящих от
v
на расстоянии не больше
k
.
Окружение
— множество вершин, смежных с заданной.
Орграф
,
ориентированный граф
G = (V,E) есть пара множеств, где V — множество вершин (узлов), E — множество дуг (ориентированных рёбер). Дуга — упорядоченная пара вершин (v, w), где вершину v называют началом, а w — концом дуги. Можно сказать, что дуга v → w ведёт от вершины v к вершине w, при этом вершина w смежная с вершиной v.
Петля
— ребро, начало и конец которого находятся в одной и той же вершине.
Пересечение графов
(помеченных графов
и
) — граф
, множеством вершин которого является
, а множеством рёбер —
.
Перечисление графов
— подсчёт числа неизоморфных графов в заданном классе (с заданными характеристиками).
— вершина,
которой равен диаметру графа.
Планарный граф
— граф, который может быть изображён (
) на плоскости без пересечения рёбер.
плоскому графу, то есть является графом с пересечениями, но допускающий его плоскую укладку, поэтому может отличаться от
изображением на плоскости. Таким образом, может быть разница между плоским графом и планарным графом при изображении на плоскости.
Плоский граф
—
, в котором никакие два ребра не имеют общих точек, кроме инцидентной им обоим вершины (не пересекаются). Является
графом на плоскости.
Подграф
исходного графа — граф, содержащий некое подмножество вершин данного графа и некое подмножество
им рёбер. (ср.
.) По отношению к подграфу исходный граф называется
Полный граф
— граф, в котором для каждой пары вершин
, существует ребро, инцидентное
и инцидентное
(каждая вершина соединена ребром с любой другой вершиной).
Полным двудольным
называется
, в котором каждая вершина одного подмножества соединена ребром с каждой вершиной другого подмножества
Полустепень захода
в
для вершины
— число дуг, входящих в вершину. Обозначается
,
,
или
.
Полустепень исхода
в
для вершины
— число дуг, исходящих из вершины. Обозначается
,
,
или
.
Помеченный граф
— граф, вершинам или дугам которого присвоены какие-либо метки, например, натуральные числа или символы какого-нибудь алфавита.
Порождённый подграф
— подграф, порождённый множеством рёбер исходного графа. Содержит не обязательно все вершины графа, но эти вершины соединены такими же рёбрами, как в графе.
Порядок графа
— количество вершин графа.
—
раскраска
, при которой каждый цветной класс является независимым множеством. Иначе говоря, в правильной раскраске любые две смежные вершины должны иметь разные цвета.
Произведение графов
— для данных графов
и
произведением называется граф
, вершины которого
— декартово произведение множеств вершин исходных графов.
—
, все вершины которого попарно различны
. Другими словами, простой путь не проходит дважды через одну вершину.
Простой цикл
—
, не проходящий дважды через одну вершину.
Псевдограф
— граф, который может содержать
и/или кратные рёбра.
Пустой граф
(
нуль-граф
) — граф без
.
Путь
— последовательность
(в неориентированном графе) и/или дуг (в ориентированном графе), такая, что конец одной дуги (ребра) является началом другой дуги (ребра). Или последовательность вершин и дуг (рёбер), в которой каждый элемент инцидентен предыдущему и последующему
. Может рассматриваться как частный случай
.
Путь в орграфе
— последовательность вершин v
1
, v
2
, …, v
n
, для которой существуют дуги v
1
→ v
2
, v
2
→ v
3
, …, v
n-1
→ v
n
. Говорят, что этот путь начинается в вершине v
1
, проходит через вершины v
2
, v
3
, …, v
n-1
, и заканчивается в вершине v
n
.
Р
Радиус графа
— минимальный из
вершин связного графа; вершина, на которой достигается этот минимум, называется центральной вершиной.
Развёртка графа
— функция, заданная на вершинах ориентированного графа.
Размеченный граф
— граф, для которого задано множество меток S, функция разметки вершин f : A → S и функция разметки дуг g : R → S. Графически эти функции представляются надписыванием меток на вершинах и дугах. Множество меток может разделяться на два непересекающихся подмножества меток вершин и меток дуг.
Разрез
— множество
, удаление которого делает граф
.
Рамочный граф
— граф, который можно нарисовать на плоскости таким способом, что любая ограниченная грань является четырёхугольником и любая вершина с тремя и менее соседями инцидентна неограниченной грани.
Раскраска графа
— разбиение вершин на множества (называемые цветами). Если при этом нет двух смежных вершин, принадлежащих одному и тому же множеству (то есть две смежные вершины всегда разного цвета), то такая раскраска называется правильной.
Расстояние
между вершинами
— длина кратчайшей цепи (в орграфе пути), соединяющей заданные вершины. Если такой цепи (пути) не существует, расстояние полагается равным бесконечности.
Рёберное покрытие
— множество рёбер графа такое, что каждая вершина инцидентна хотя бы одному ребру из этого множества.
Рёберный граф
неориентированного графа — это граф, представляющий соседство рёбер графа.
Ребро
— базовое понятие. Ребро соединяет две
графа.
Регулярный граф
— граф,
всех вершин которого равны. Степень регулярности является
инвариантом
графа и обозначается
. Для нерегулярных графов
не определено. Регулярные графы представляют особую сложность для многих алгоритмов.
Регулярный граф степени 0
(
вполне несвязный граф
,
пустой граф
,
нуль-граф
) — граф без
.
С
Самодвойственный граф
— граф,
своему
.
Сверхстройное (звездообразное) дерево
— дерево, в котором имеется единственная вершина степени больше 2.
Связность
. Две вершины в графе
связаны
, если существует соединяющая их (простая)
.
Сечение графа
— множество рёбер, удаление которых делит граф на два изолированных подграфа, один из которых, в частности, может быть тривиальным графом.
Сеть
— в принципе, то же, что и
, хотя сетями обычно называют графы,
которых определённым образом помечены.
Ориентированная сеть
— ориентированный граф, не содержащий контуров.
Сильная связность
. Две вершины в
сильно связаны
, если существует путь из первой во вторую и из второй в первую.
Сильно связный орграф
—
, в котором все вершины сильно связаны.
Смежность
— понятие, используемое в отношении только двух
либо только двух
: Два ребра,
одной вершине, называются
смежными
; две вершины,
одному ребру, также называются
смежными
. (ср.
.)
Смешанный граф
— граф, содержащий как ориентированные, так и неориентированные
.
Совершенное паросочетание
— паросочетание, содержащее все вершины графа.
Соединением двух графов
и
, не имеющих общих вершин, называется граф
.
Из определения видно, что соединение графов обладает свойствами коммутативности и ассоциативности
Спектр графа
— множество всех собственных значений матрицы смежности с учётом кратных рёбер.
Степень вершины
— количество рёбер графа
G
,
вершине
x
. Обозначается
.
Минимальная
степень вершины графа
G
обозначается
. а
максимальная
—
.
Стягивание ребра графа
— замена концов ребра одной вершиной, соседями новой вершины становятся соседи этих концов. Граф
стягиваем
к
, если второй можно получить из первого последовательностью стягиваний рёбер.
Суграф
(
частичный граф
) исходного графа — граф, содержащий все вершины исходного графа и подмножество его
. (ср.
.)
Суперграф
— любой граф, содержащий исходный граф (то есть для которого исходный граф является
)
Т
Тета-граф
— граф, состоящий из объединения трёх путей, не имеющих внутри общих вершин, у которых конечные вершины одни и те же
Тета-граф
множества точек евклидовой плоскости строится как система конусов, окружающих каждую вершину с добавлением ребра для каждого конуса к точке множества, проекция которой на центральную ось конуса минимальна.
Тождественный граф
— граф, у которого возможен один-единственный
— тождественный. Образно говоря, тождественный граф — «абсолютно несимметричный» граф.
Тривиальный граф
— граф, состоящий не более чем из одной
.
Турнир
—
, в котором каждая пара вершин соединена одним ребром.
У
Узел
— то же, что и
.
Укладка
, или
вложение графа
: граф укладывается на некоторой поверхности, если его можно нарисовать на этой поверхности так, чтобы
графа при этом не пересекались. (См.
,
.)
Укрытие
— определённый тип функции на множествах вершин неориентированного графа. Если укрытие существует, его может использовать беглец чтобы выиграть игру преследования-уклонения на графе путём использования этой функции на каждом шаге игры для определения безопасных множеств вершин, куда можно перейти.
— граф, в котором рёбра, выходящие из каждой вершины, однозначно пронумерованы, начиная с 1. Рёбра считаются упорядоченными в порядке возрастания номеров. При графическом представлении часто рёбра считаются упорядоченными в порядке некоторого стандартного обхода (например,
против часовой стрелки
).
n-факторизация
графа — разбиение графа на независимые
.
Х
Хроматическое число
графа — минимальное количество цветов, требуемое для
раскраски
вершин графа, при которой любые вершины, соединенные ребром, раскрашены в разные цвета.
Характеристический многочлен
графа — характеристический многочлен его
матрицы смежности
.
Ц
Центр графа
— множество вершин
, для которых справедливо равенство:
, где
—
, а
— радиус графа.
Цепь
в графе —
, все рёбра которого различны. Если все
(а тем самым и рёбра) различны, то такая цепь называется
простой
(
элементарной
). В цепи
вершины
и
называются
концами
цепи. Цепь с концами
u
и
v
соединяет
вершины
u
и
v
. Цепь, соединяющая вершины
u
и
v
, обозначается
. Для
цепь называется орцепью.
В некоторых источниках
простая цепь
— цепь,
которой различны, что является более слабым условием.
Цикл
(
простой цикл
) в
—
не менее 1, который начинается и заканчивается в одной и той же вершине.
Цикл Гамильтона
— то же, что и
.
Цикломатическое число графа
— минимальное число рёбер, которые надо удалить, чтобы граф стал
. Для связного графа существует соотношение:
где
— цикломатическое число,
— число
графа,
— число
, а
— число
.
Шарнир
—
графа
, в результате удаления которой вместе со всеми
ей
количество
в графе возрастает.
Шестерёнка
(обозначается
) — граф, получаемый из
путём размещения дополнительных вершин между каждой парой смежных вершин
. Шестерёнки принадлежат семейству
и играют важную роль при описании запрещённых подграфов рамочных графов
Э
Эйлеров граф
— граф, в котором существует
, содержащий все рёбра графа по одному разу (вершины могут повторяться).
Эксцентриситет
вершины — максимальное из всех минимальных расстояний от других вершин до данной вершины.
Элементарный путь
—
, вершины которого, за исключением, быть может, первой и последней, различны. Другими словами, простой путь не проходит дважды через одну вершину, но может начаться и закончиться в одной и той же вершине, в таком случае он называется
(элементарным циклом).
Элементарным стягиванием
называется такая процедура: берём
(вместе с инцидентными ему
, например, 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
:
.
H.-J. Bandelt, V. Chepoi, D. Eppstein.
Combinatorics and geometry of finite and infinite squaregraphs //
. — 2010. —
Т. 24
,
вып. 4
. —
С. 1399–1440
. —
doi
:
. —
arXiv
:
.
.
Литература
Дистель Р.
Теория графов Пер. с англ. − Новосибирск: Изд-во Ин-та математики, 2002. − 336 c.