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

Привет, сегодня поговорим про глоссарий теории графов, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое глоссарий теории графов , настоятельно рекомендую прочитать все из категории Дискретная математика. Теория множеств . Теория графов . Комбинаторика..

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

А

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

Б

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

В

• Валентность вершины — см. степень вершины.
• Вершина, Узел — базовое понятие: точка, где могут сходиться/выходить ребра и/или дуги. Множество вершин графа G обозначается V(G).
• Вес ребра — значение, поставленное в соответствие данному ребру взвешенного графа. Обычно, вес — вещественное число, в таком случае его можно интерпретировать как «длину» ребра.
• Взвешенный граф — граф, каждому ребру которого поставлено в соответствие некое значение (вес ребра).
• Висячая вершина — вершина, степень которой равна 1 (то есть ).
• Вполне несвязный граф (пустой граф, нуль-граф) — регулярный граф степени 0, то есть граф без ребер.
• Высота дерева — наибольшая длина пути от корня к листу.

Г

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

Д

• Двойственный граф. Граф А называется двойственным к планарному графу В, если вершины графа А соответствуют граням графа В, и две вершины графа Aсоединены ребром тогда и только тогда, когда соответствующие грани графа B имеют хотя бы одно общее ребро.
• Двудольный граф (или биграф, или четный граф) — это граф , такой что множество вершин V разбито на два непересекающихся подмножества  и , причем всякое ребро E инцидентно вершине из  и вершине из  (то есть соединяет вершину из  с вершиной из ). То есть, правильная раскраска графа двумя цветами. Множества  и  называются «долями» двудольного графа. Двудольный граф называется «полным», если любые две вершины из  и  являются смежными. Если , , то полный двудольный граф обозначается .
• Двусвязный граф — связный граф, в котором нет шарниров.
• Дерево — связный граф, не содержащий циклов.
• Диаметр графа  — это максимум расстояния между вершинами для всех пар вершин. Расстояние между вершинами — наименьшее число ребер пути, соединяющего две вершины.
• Длина маршрута — количество ребер в маршруте (с повторениями). Если маршрут , то длина M равна k (обозначается ).
• Длина пути — число дуг пути (или сумма длин его дуг, если последние заданы). Так для пути v₁, v₂, …, v_n длина равна n-1.
• Дуга — это ориентированное ребро.
• Дополнение графа — граф над тем же множеством вершин, что и исходный, но вершины соединены ребром тогда и только тогда, когда в исходном графе ребра нет.

З

• Граф-звезда — полный двудольный граф .

И

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

К

• Клетка — регулярный граф наименьшего обхвата для заданной степени вершин.
• Клика — подмножество вершин графа, полностью соединенных друг с другом, то есть подграф, являющийся полным графом.
  • Кликовое число (англ. Clique number) — число (G) вершин в наибольшей клике. Другие названия — густота, плотность.
  • Максимальная клика — клика с максимально возможным числом вершин среди клик графа.
•  Колесо — (обозначается W_n) это граф с n вершинами (n ≥ 4), образованный соединением единственной вершины со всеми вершинами (n-1)-цикла.

• Конструктивное перечисление графов — получение полного списка графов в заданном классе.
• Компонента связности графа — некоторое подмножество вершин графа такое, что для любых двух вершин из этого множества существует путь из одной в другую, и не существует пути из вершины этого множества в вершину не из этого множества.
• Компонента сильной связности графа, слой — максимальное множество вершин ориентированного графа такое, что для любых двух вершин из этого множества существует путь как из первой во вторую, так и из второй в первую.
• Контур — замкнутый путь в орграфе.
• Корень дерева — выбранная вершина дерева; в орграфе — вершина с нулевой степенью захода.
• Коцикл — минимальный разрез, минимальное множество ребер, удаление которого делает граф несвязным.
• Кратные ребра — несколько ребер, инцидентных одной и той же паре вершин. Встречаются в мультиграфах.
• Кубический граф — регулярный граф степени 3, то есть граф в котором каждой вершине инцидентно ровно три ребра.
• k-дольный граф — граф G, у которого хроматическое число c(G)=k
• k-связный граф — связный граф, в котором не существует набора  из  или менее вершин, такого, что удаление всех вершин  и инцидентных им ребернарушает связность графа. В частности, связный граф является 1-связным, а двусвязный — 2-связным.

Л

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

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

М

• Макси-код  — трудновычислимый полный инвариант графа, получаемый путем выписывания двоичных значений матрицы смежности в строчку с последующим переводом полученного двоичного числа в десятичную форму. Макси-коду соответствует такой порядок следования строк и столбцов, при котором полученное значение является максимально возможным.
• Максимальное паросочетание в графе. Паросочетание называется максимальным, если любое другое паросочетание содержит меньшее число ребер.
• Маршрут в графе — это чередующаяся последовательность вершин и ребер , в которой любые два соседних элемента инцидентны. Если , то маршрут замкнут, иначе открыт.
• Матрица достижимости орграфа — это матрица, содержащая информацию о существовании путей между вершинами в орграфе.
• Матрица инцидентности графа — это матрица, значения элементов которой характеризуется инцидентностью соответствующих вершин графа (по вертикали) и его ребер (по горизонтали). Для неориентированного графа элемент принимает значение 1, если соответствующие ему вершина и ребро инцидентны. Дляориентированного графа элемент принимает значение 1, если инцидентная вершина является началом ребра, значение -1, если инцидентная вершина является концом ребра; в остальных случаях (в том числе и для петель) значению элемента присваивается 0.
• Матрица смежности графа — это матрица, значения элементов которой характеризуются смежностью вершин графа. При этом значению элемента матрицы присваивается количество ребер, которые соединяют соответствующие вершины (то есть которые инцидентны обоим вершинам). Петля считается сразу двумя соединениями для вершины, то есть к значению элемента матрицы в таком случае следует прибавлять 2.
• Мини-код  — трудновычислимый полный инвариант графа, получаемый путем выписывания двоичных значений матрицы смежности в строчку с последующим переводом полученного двоичного числа в десятичную форму. Мини-коду соответствует такой порядок следования строк и столбцов, при котором полученное значение является минимально возможным.
• Минимальный каркас (или Каркас минимального веса, Минимальное остовное дерево) графа — ациклическое (не имеющее циклов) множество ребер в связном, взвешенном и неориентированном графе, соединяющих между собой все вершины данного графа, при этом сумма весов всех ребер в нем минимальна.
• Множество смежности вершины v — множество вершин, смежных с вершиной v. Обозначается 
• Минором графа называется граф, который можно получить из исходного путем удаления и стягивания дуг
• Мост — ребро, удаление которого увеличивает количество компонент связности в графе.
• Мультиграф — граф, в котором может быть пара вершин, которая соединена более чем одним ребром (ненаправленным), либо более чем двумя дугами противоположных направлений.

Н

• Направленный граф — ориентированный граф, в котором две вершины соединяются не более чем одной дугой.
  • Направленный ациклический граф — ориентированный граф без контуров.
• Независимое множество вершин (известное также как внутренне устойчивое множество) — есть множество вершин графа G, такое, что любые две вершины в нем несмежны (никакая пара вершин не соединена ребром).
  • Независимое множество называется максимальным, когда нет другого независимого множества, в которое оно бы входило.
  • Если Q является семейством всех независимых множеств графа G, то число a(G) = max |S| (где S принадлежит Q) называется числом независимости графа G, а множество S*, на котором этот максимум достигается, называется наибольшим независимым множеством.
• Независимые вершины — попарно несмежные вершины графа.^[1]
• Неразделимым графом — называется, связный, непустой, не имеющий точек сочленения граф.^[2].
• Нормированный граф — ориентированный граф без циклов.
• Нуль-граф (вполне несвязный граф, пустой граф) — регулярный граф степени 0, то есть граф, не содержащий ребер.

О

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

П

• Паросочетание — это набор попарно несмежных ребер.
• Петля — ребро, начало и конец которого находятся в одной и той же вершине.
• Пересечение графов (помеченных графов  и ) — граф , множеством вершин которого является , а множеством ребер — .
• Перечисление графов — подсчет числа неизоморфных графов в заданном классе (с заданными характеристиками).
• Периферийная вершина — вершина, эксцентриситет которой равен диаметру графа.
• Планарный граф — граф, который может быть изображен (уложен) на плоскости без пересечения ребер. Изоморфен плоскому графу, то есть, является графом с пересечениями, но допускающий его плоскую укладку, поэтому может отличаться от плоского графа изображением на плоскости . Таким образом, может быть разница между плоским графом и планарным графом при изображении на плоскости.
• Плоский граф — геометрический граф, в котором никакие два ребра не имеют общих точек, кроме инцидентной им обоим вершины (не пересекаются). Являетсяуложенным графом на плоскости.
• Подграф исходного графа — граф, содержащий некое подмножество вершин данного графа и некое подмножество инцидентных им ребер. (ср. Суграф.) По отношению к подграфу исходный граф называется суперграфом
• Полный граф — граф, в котором для каждой пары вершин , существует ребро, инцидентное  и инцидентное  (каждая вершина соединена ребром с любой другой вершиной).
• Полный инвариант графа — числовая характеристика графа или их упорядоченный вектор, значения которой необходимо и достаточно для установленияизоморфизма графов.
• Полным двудольным называется двудольный граф, в котором каждая вершина одного подмножества соединена ребром с каждой вершиной другого подмножества
• Полустепень захода в орграфе для вершины  — число дуг, входящих в вершину. Обозначается , ,  или .
• Полустепень исхода в орграфе для вершины  — число дуг, исходящих из вершины. Обозначается , ,  или .
• Помеченный граф — граф, вершинам или дугам которого присвоены какие-либо метки, например, натуральные числа или символы какого-нибудь алфавита.
• Порожденный подграф — подграф, порожденный множеством ребер исходного графа. Содержит не обязательно все вершины графа, но эти вершины соединены такими же ребрами как в графе.
• Порядок графа — количество вершин графа.^[3]
• Правильная раскраска графа — раскраска, при которой каждый цветной класс является независимым множеством. Иначе говоря, в правильной раскраске любые две смежные вершины должны иметь разные цвета.
• Произведение графов — для данных графов  и  произведением называется граф , вершины которого  — декартово произведение множеств вершин исходных графов.
• Простая цепь — маршрут, в котором все вершины различны.
• Простой граф — граф, в котором нет кратных ребер и петель.
• Простой путь — путь, все ребра которого попарно различны^[4]. Другими словами, простой путь не проходит дважды через одно ребро.
  • Простой цикл — цикл, не проходящий дважды через одну вершину.
• Псевдограф — граф, который может содержать петли и/или кратные ребра.
• Пустой граф (вполне несвязный граф, нуль-граф) — регулярный граф степени 0, то есть граф, не содержащий ребер.
• Путь — последовательность ребер (в неориентированном графе) и/или дуг (в ориентированном графе), такая, что конец одной дуги (ребра) является началом другой дуги (ребра). Или последовательность вершин и дуг (ребер) в которой каждый элемент инцидентен предыдущему и последующему^[4]. Может рассматриваться как частный случай маршрута.
• Путь в орграфе — это последовательность вершин v₁, v₂, …, v_n, для которой существуют дуги v₁ → v₂, v₂ → v₃, …, v_n-1 → v_n. Говорят, что этот путь начинается в вершине v₁, проходит через вершины v₂, v₃, …, v_n-1, и заканчивается в вершине v_n.

Р

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

С

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

Из определения видно, что соединение графов обладает свойствами коммутативности и ассоциативности

• Спектр графа — множество всех собственных значений матрицы смежности с учетом кратных ребер.
• Степень вершины — количество ребер графа G, инцидентных вершине x. Обозначается . Минимальная степень вершины графа G обозначается . амаксимальная — .
• Стягивание ребра графа — замена концов ребра одной вершиной, соседями новой вершины становятся соседи этих концов. Граф  стягиваем к , если второй можно получить из первого последовательностью стягиваний ребер.
• Суграф (частичный граф) исходного графа — граф, содержащий все вершины исходного графа и подмножество его ребер. (ср. Подграф.)
•  Суперграф — это любой граф, содержащий исходный граф (то есть, для которого исходный граф является подграфом)

Т

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

У

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

Ф

• n-Фактор графа — регулярный остовный подграф степени .
• n-Факторизация графа — разбиение графа на независимые n-факторы.

Х

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

Ц

• Центр графа — множество вершин , для которых справедливо равенство: , где  — это эксцентриситет вершины, а  — радиус графа.
• Цепь в графе — маршрут, все ребра которого различны. Если все вершины (а тем самым и ребра) различны, то такая цепь называется простой (элементарной). В цепи  вершины  и  называются концами цепи. Цепь с концами u и v соединяет вершины u и v. Цепь, соединяющая вершины u и vобозначается . Для орграфов цепь называется орцепью.

  В некоторых источниках простая цепь — цепь, ребра которой различны, что является более слабым условием.

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

Ч

• Частичный граф — то же, что и суграф.
• Четный граф — то же, что и двудольный граф.

Ш

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

Э

• Эйлеров граф — это граф, в котором существует цикл, содержащий все ребра графа по одному разу (вершины могут повторяться).
• Эйлерова цепь (или Эйлеров цикл) — это цепь (цикл), которая содержит все ребра графа (вершины могут повторяться).
• Эксцентриситет вершины — максимальное расстояние из всех минимальных расстояний от других вершин до данной вершины.
• Элементарный путь — путь, вершины которого, за исключением, быть может, первой и последней, различны. Другими словами, простой путь не проходит дважды через одну вершину, но может начаться и закончиться в одной и той же вершине, в таком случае он называется циклом (элементарным циклом).
• Элементарным стягиванием называется такая процедура: берем ребро (вместе с инцидентными ему вершинами, например, u и v) и «стягиваем» его, то есть удаляем ребро и отождествляем вершины u и v. Полученная при этом вершина инцидентна тем ребрам (отличным от), которым первоначально были инцидентны u или v.

Ссылки

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

Литература

• Дистель Р. Теория графов Пер. с англ. - Новосибирск: Изд-во Ин-та математики, 2002.- 336c.
• Харари Ф. Теория графов. — М.: УРСС, 2003. — 300 с. — ISBN 5-354-00301-6.

На этом все! Теперь вы знаете все про глоссарий теории графов, Помните, что это теперь будет проще использовать на практике. Надеюсь, что теперь ты понял что такое глоссарий теории графов и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Дискретная математика. Теория множеств . Теория графов . Комбинаторика.