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

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

А

• Автоморфизм — изоморфизм графа с самим собой.

Б

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

В

• Валентность вершины — см. Степень вершины.
• Взвешенный граф — граф, каждому ребру которого поставлено в соответствие некое значение (вес ребра).
• Висячая вершина — вершина, степень которой равна 1 (то есть $d(v)=1$).
• Вполне несвязный граф (англ. Fully disconnected graph) — граф без рёбер. Другие названия — регулярный граф степени 0, пустой граф.
• Вес ребра — значение, поставленное в соответствие данному ребру взвешенного графа. Обычно вес — вещественное число, в таком случае его можно интерпретировать как «длину» ребра.

Г

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

Д

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

И

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

М

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

К

• Контур -

Контур – путь, у которого конечная вер- шина совпадает с начальной вершиной. Длиной пути (контура) называется число дуг пути (или сумма длин его дуг, если послед- ние заданы).

Л

• Лес - неориентированный граф без циклов. Компонентами связности леса являются деревья.

Н

• Нормированный граф - ориентированный граф без циклов.
• Нуль-граф - граф, не содержащий рёбер.

О

• Орграф см. ориентированный граф
• Ориентированный граф G = (V,E) есть пара множеств, где V — множество вершин (узлов), E — множество дуг (ориентированных рёбер). Дуга — это упорядоченная пара вершин (v,w), где вершину v называют началом, а w — концом дуги. Можно сказать, что дуга v -> w ведет от вершины v к вершине w, при этом вершина w смежная с вершиной v.

П

• Планарный граф - граф, который может быть изображен на плоскости без пересечения рёбер.
• Подграф исходного графа - граф, содержащий некое подмножество вершин данного графа и все рёбра, инцидентные данному подмножеству.
• Полным графом называется граф, в котором для каждой пары вершин $v_{1},v_{2}$, существует ребро, инцидентное $v_{1}$ и инцидентное $v_{2}$
• Полустепень захода в орграфе для вершины v — число дуг, входящих в вершину. Обозначается $d^{+}(v)$.
• Полустепень исхода в орграфе для вершины v — число дуг, исходящих из вершины. Обозначается $d^{-}(v)$.
• Простой путь — путь, вершины которого, за исключением быть может, первой и последней, различны. Другими словами, простой путь не проходит дважды через одну вершину, но может начаться и закончиться в одной и той же вершине, в таком случае он называется циклом (простым циклом).
• Псевдограф — граф, содержащий петли.
• Путь
• Путь в орграфе — это последовательность вершин v₁, v₂, …, v_n, для которой существуют дуги v₁ -> v₂, v₂ -> v₃, …, v_n-1 -> v_n. Говорят, что этот путь начинается в вершине v₁, проходит через вершины v₂, v₃, …, v_n-1, и заканчивается в вершине v_n.

Р

• Регулярный граф - граф, степени всех вершин которого равны. Степень регулярности является инвариантом графа и обозначается $r(G)$. Для нерегулярных графов $r(G)$ не определено.
• Раскраска графа - разбиение вершин на множества ( называемые цветами ), при котором нет двух смежных вершин принадлежащих одному и тому же множеству.
• Размеченный граф — граф, для которого задано множество меток S, функция разметки вершин f : A → S и функция разметки дуг g : R → S. Графически эти функции представляются надписыванием меток на вершинах и дугах. Множество меток может разделяться на два непересекающихся подмножества меток вершин и меток дуг.

С

• Самодвойственный граф - граф, изоморфный своему двойственному графу.
• Связность. Две вершины в графе связаны, если существует соединяющая их (простая) цепь.
• Связный граф — граф, в котором все вершины связаны.
• Смежность. Два ребра, инцидентные одной вершине, называются смежными; две вершины, инцидентные одному ребру, также называются смежными.
• Смешанный граф - граф, содержащий как ориентированные, так и неориентированные рёбра.
• Степень вершины v — количество рёбер, инцидентных вершине v. Обозначается $d(v)$. Минимальная степень вершины графа G обозначается $\delta (G)$. а максимальная — $\Delta (G)$.
• Суграф исходного графа - граф, содержащий все вершины исходного графа и подмножество его рёбер.

Т

• Тождественный граф — граф, у которого возможен один единственный автоморфизм — тождественный. Образно говоря, тождественный граф — это «абсолютно несимметричный» граф.

У

• Укладка: граф укладывается на некоторой поверхности, если его можно нарисовать на этой поверхности так, чтобы рёбра графа при этом не пересекались. Граф называется планарным, если его можно уложить на плоскости. Плоский граф - это граф, уже уложенный на плоскости.
• Упорядоченный граф - граф, в котором дуги, выходящие из каждой вершины, однозначно пронумерованы, начиная с 1. Дуги считаются упорядоченными в порядке возрастания номеров. При графическом представлении часто дуги считаются упорядоченными в порядке некоторого стандартного обхода (например, слева направо).

Х

• Хроматическое число графа - минимальное количество цветов, требуемое для раскраски вершин графа, при которой любые вершины, соединенные ребром, раскрашены в разные цвета.

Ц

• Цепь в графе — маршрут, все рёбра которого различны. Если все вершины (а тем самым и рёбра) различны, то такая цепь называется простой. В цепи $v_{0},e_{1},...,e_{k},v_{k}$ вершины $v_{0}$ и $v_{k}$ называются концами цепи. Цепь с концами u и v соединяет вершины u и v. Цепь, соединяющая вершины u и v обозначается $\left\langle u,v\right\rangle$. Для орграфов цепь называется путём.
• Цикл — замкнутая цепь. Для орграфов цикл называется контуром.
• Цикл (простой цикл) в орграфе — это простой путь, длины не менее 1, который начинается и заканчивается в одной и той же вершине.

Ч

• Чётный граф - см. двудольный граф.

Э

• Элементарный путь - см. простой путь.
• Эйлеров граф - это граф, в котором существует путь или цикл, содержащий все рёбра графа (вершины могут повторяться).

Ссылки

• Толковый словарь по теории графов