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

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

{{#if:

{{#if: | }}{{#if:

| Шаблон:АБВ/Цвет1 | Шаблон:АБВ/Цвет2 }}

А

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

Б

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

В

• Шаблон:ЯкорьВалентность вершины — см. степень вершины.
• Шаблон:ЯкорьВершина, узел — базовое понятие: точка, где могут сходиться/выходить рёбра и/или дуги. Множество вершин графа G обозначается V(G).
• Шаблон:ЯкорьВершинное покрытие — множество вершин графа такое, что каждое ребро инцидентно хотя бы одной вершине из этого множества.
• Шаблон:ЯкорьВес ребра — значение, поставленное в соответствие данному ребру взвешенного графа. Обычно вес — вещественное число, в таком случае его можно интерпретировать как «длину» ребра.
• Шаблон:ЯкорьВзвешенный граф — граф, каждому ребру которого поставлено в соответствие некое значение (вес ребра). См. Размеченный граф.
• Шаблон:ЯкорьВисячая вершина — вершина, степень которой равна 1 (то есть <math>d(v)=1</math>).

• Вполне несвязный граф — регулярный граф степени 0, то есть граф без рёбер.
• Шаблон:ЯкорьВысота дерева — наибольшая длина пути от корня к листу.

Г

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

Д

• Шаблон:ЯкорьДвойственный граф. Граф А называется двойственным к планарному графу В, если вершины графа А соответствуют граням графа В, и две вершины графа A соединены ребром тогда и только тогда, когда соответствующие грани графа B имеют хотя бы одно общее ребро.
• Шаблон:ЯкорьДвудольный граф (или биграф, или чётный граф) — такой граф <math>G(V,E)</math>, что множество вершин V разбито на два непересекающихся подмножества <math>V_1</math> и <math>V_2</math>, причём всякое ребро E инцидентно вершине из <math>V_1</math> и вершине из <math>V_2</math> (то есть соединяет вершину из <math>V_1</math> с вершиной из <math>V_2</math>). То есть правильная раскраска графа осуществляется двумя цветами. Множества <math>V_1</math> и <math>V_2</math> называются «долями» двудольного графа. Двудольный граф называется «полным», если любые две вершины из <math>V_1</math> и <math>V_2</math> являются смежными. Если <math>\left|V_1\right| = a</math>, <math>\left|V_2\right| = b</math>, то полный двудольный граф обозначается <math>K_{a,b}</math>.
• Шаблон:ЯкорьДвусвязный граф — связный граф, в котором нет шарниров.
• Шаблон:ЯкорьДерево — связный граф, не содержащий циклов.
• Шаблон:ЯкорьДиаметр графа <math>\mathrm{diam}(G)</math> — максимум расстояния между вершинами для всех пар вершин. Расстояние между вершинами — наименьшее число рёбер пути, соединяющего две вершины.
• Шаблон:ЯкорьДлина маршрута — количество рёбер в маршруте (с повторениями). Если маршрут <math>M=v_0,e_1,v_1,e_2,v_2,...,e_k,v_k</math>, то длина M равна k (обозначается <math>\left|M\right|=k</math>).
• Шаблон:ЯкорьДлина пути — число дуг пути (или сумма длин его дуг, если последние заданы). Так для пути v₁, v₂, …, v_n длина равна n-1.
• Шаблон:ЯкорьДуга — ориентированное ребро.
• Шаблон:ЯкорьДополнение графа — граф над тем же множеством вершин, что и исходный, но вершины соединены ребром тогда и только тогда, когда в исходном графе ребра нет.

Е

• Шаблон:ЯкорьЕжевика неориентированного графа G — семейство связных подграфов графа G, касающихся друг друга.

З

• Шаблон:ЯкорьГраф-звезда — полный двудольный граф <math>K_{1,b}</math>.

И

• Шаблон:ЯкорьИзолированная вершина — вершина, степень которой равна 0 (то есть нет рёбер, инцидентных ей).
• Шаблон:ЯкорьИзоморфизм. Два графа называются изоморфными, если существует перестановка вершин, при которой они совпадают. Иначе говоря, два графа называются изоморфными, если существует взаимно-однозначное соответствие между их вершинами и рёбрами, которое сохраняет смежность и инцидентность (графы отличаются только названиями своих вершин).
• Шаблон:ЯкорьИнвариант графа — числовая характеристика графа или их упорядоченный вектор, характеризующая структуру графа инвариантно относительно перенумерации вершин.
• Шаблон:ЯкорьИнтервальный граф — граф, вершины которого могут быть взаимно однозначно поставлены в соответствие отрезкам на действительной оси таким образом, что две вершины инцидентны одному ребру тогда и только тогда, когда отрезки, соответствующие этим вершинам, пересекаются.
• Шаблон:ЯкорьИнцидентность — понятие, используемое только в отношении ребра или дуги и вершины: если <math>v_1, v_2</math> — вершины, а <math>e=(v_1,v_2)</math> — соединяющее их ребро, тогда вершина <math>v_1</math> и ребро <math>e</math> инцидентны, вершина <math>v_2</math> и ребро <math>e</math> тоже инцидентны. Две вершины (или два ребра) инцидентными быть не могут. Для обозначения ближайших вершин (рёбер) используется понятие смежности.

К

• Шаблон:ЯкорьКлетка — регулярный граф наименьшего обхвата для заданной степени вершин.
• Шаблон:ЯкорьКлика — подмножество вершин графа, полностью соединённых друг с другом, то есть подграф, являющийся полным графом.
  • Шаблон:ЯкорьКликовое число (англ. Шаблон:Lang-en2) — число (G) вершин в наибольшей клике. Другие названия — густота, плотность.
  • Шаблон:ЯкорьМаксимальная клика — клика с максимально возможным числом вершин среди клик графа.
• Шаблон:ЯкорьКолесо (обозначается W_n) — граф с n вершинами (n ≥ 4), образованный соединением единственной вершины со всеми вершинами (n-1)-цикла.
• Шаблон:ЯкорьКолчан — просто ориентированный граф.
• Шаблон:ЯкорьКонечный граф — граф, содержащий конечное число вершин и рёбер.
• Шаблон:ЯкорьКонструктивное перечисление графов — получение полного списка графов в заданном классе.
• Шаблон:ЯкорьКомпонента связности графа — такое подмножество вершин графа, для любых двух вершин которого существует путь из одной в другую, и не существует пути из вершины этого подмножества в вершину не из этого подмножества.
• Шаблон:ЯкорьКомпонента сильной связности графа, слой — максимальное множество вершин ориентированного графа, такое, что для любых двух вершин из этого множества существует путь как из первой во вторую, так и из второй в первую.
• Шаблон:ЯкорьКонтур — замкнутый путь в орграфе.
• Шаблон:ЯкорьКорень дерева — выбранная вершина дерева; в орграфе — вершина с нулевой степенью захода.
• Шаблон:ЯкорьКоцикл — минимальный разрез, минимальное множество рёбер, удаление которого делает граф несвязным.
• Шаблон:ЯкорьКратные рёбра — несколько рёбер, инцидентных одной и той же паре вершин. Встречаются в мультиграфах.
• Шаблон:ЯкорьКубический граф — регулярный граф степени 3, то есть граф, в котором каждой вершине инцидентно ровно три ребра.
• Шаблон:Якорьk-дольный граф — граф G, у которого хроматическое число c(G)=k
• Шаблон:Якорьk-связный граф — связный граф, в котором не существует набора <math>V'</math> из <math>k-1</math> или менее вершин, такого, что удаление всех вершин <math>V'</math> и инцидентных им рёбер нарушает связность графа. В частности, связный граф является 1-связным, а двусвязный — 2-связным.

Л

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

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

М

• Шаблон:ЯкорьМакси-код <math>\mu_{max}</math> — трудновычислимый полный инвариант графа, получаемый путём выписывания двоичных значений матрицы смежности в строчку с последующим переводом полученного двоичного числа в десятичную форму. Макси-коду соответствует такой порядок следования строк и столбцов, при котором полученное значение является максимально возможным.
• Шаблон:ЯкорьМаксимальное паросочетание в графе. Паросочетание называется максимальным, если любое другое паросочетание содержит меньшее число рёбер.
• Шаблон:ЯкорьМаршрут в графе — чередующаяся последовательность вершин и рёбер <math>v_0, e_1, v_1, e_2, v_2, ... , e_k, v_k</math>, в которой любые два соседних элемента инцидентны. Если <math>v_0=v_k</math>, то маршрут замкнут, иначе открыт.
• Шаблон:ЯкорьМатрица достижимости орграфа — матрица, содержащая информацию о существовании путей между вершинами в орграфе.
• Шаблон:ЯкорьМатрица инцидентности графа — матрица, значения элементов которой характеризуется инцидентностью соответствующих вершин графа (по вертикали) и его рёбер (по горизонтали). Для неориентированного графа элемент принимает значение 1, если соответствующие ему вершина и ребро инцидентны. Для ориентированного графа элемент принимает значение 1, если инцидентная вершина является началом ребра, значение -1, если инцидентная вершина является концом ребра; в остальных случаях (в том числе и для петель) значению элемента присваивается 0.
• Шаблон:ЯкорьМатрица смежности графа — матрица, значения элементов которой характеризуются смежностью вершин графа. При этом значению элемента матрицы присваивается количество рёбер, которые соединяют соответствующие вершины (то есть которые инцидентны обеим вершинам).
• Шаблон:ЯкорьМини-код <math>\mu_{min}</math> — трудновычислимый полный инвариант графа, получаемый путём выписывания двоичных значений матрицы смежности в строчку с последующим переводом полученного двоичного числа в десятичную форму. Мини-коду соответствует такой порядок следования строк и столбцов, при котором полученное значение является минимально возможным.
• Шаблон:ЯкорьМинимальный каркас (или каркас минимального веса, минимальное остовное дерево) графа — ациклическое (не имеющее циклов) множество рёбер в связном, взвешенном и неориентированном графе, соединяющих между собой все вершины данного графа, при этом сумма весов всех рёбер в нём минимальна.
• Шаблон:ЯкорьМножество смежности вершины v — множество вершин, смежных с вершиной v. Обозначается <math>\Gamma^+(v)</math>.
• Шаблон:ЯкорьМинором графа называется граф, который можно получить из исходного путём удаления и стягивания дуг.
• Шаблон:ЯкорьМост — ребро, удаление которого увеличивает количество компонент связности в графе.
• Шаблон:ЯкорьМультиграф — граф, в котором может быть пара вершин, которая соединена более чем одним ребром (ненаправленным), либо более чем двумя дугами противоположных направлений.

Н

• Шаблон:ЯкорьНаправленный граф — ориентированный граф, в котором две вершины соединяются не более чем одной дугой.
  • Шаблон:ЯкорьНаправленный ациклический граф — ориентированный граф без контуров.
• Шаблон:ЯкорьНезависимое множество вершин (известное также как внутренне устойчивое множество) — множество вершин графа G, в котором любые две вершины несмежны (никакая пара вершин не соединена ребром).
  • Независимое множество называется максимальным, когда нет другого независимого множества, в которое оно бы входило. Дополнение наибольшего независимого множества называется минимальным вершинным покрытием графа.
  • Наибольшим независимым множеством называется независимое множество наибольшего размера.
• Шаблон:ЯкорьНезависимые вершины — попарно несмежные вершины графа.<ref> Дистель Р. Теория графов Пер. с англ. — Новосибирск: Изд-во Ин-та математики, 2002. — С. 17.</ref>
• Шаблон:ЯкорьНеразделимый граф — связный, непустой, не имеющий точек сочленения граф.<ref>Харари Ф. Теория графов. — М.: Мир, 1972. — С. 41.</ref>.
• Шаблон:ЯкорьНормированный граф — ориентированный граф без циклов.

• Нуль-граф (пустой граф) — граф без вершин.

О

• Шаблон:ЯкорьОбхват — длина наименьшего цикла в графе.
• Шаблон:ЯкорьОбъединение графов (помеченных графов <math>G_1=(X_1, U_1)</math> и <math>G_2=(X_2, U_2)</math>) — граф <math>G_1 \cup G_2</math>, множеством вершин которого является <math>X_1 \cup X_2</math>, а множеством рёбер — <math>U=U_1 \cup U_2</math>.
• Шаблон:ЯкорьОкрестность порядка k — множество вершин на расстоянии k от заданной вершины v; иногда толкуется расширительно как множество вершин, отстоящих от v на расстоянии не больше k.
• Шаблон:ЯкорьОкружение — множество вершин, смежных с заданной.
• Шаблон:ЯкорьОрграф, ориентированный граф G = (V,E) есть пара множеств, где V — множество вершин (узлов), E — множество дуг (ориентированных рёбер). Дуга — упорядоченная пара вершин (v, w), где вершину v называют началом, а w — концом дуги. Можно сказать, что дуга v → w ведёт от вершины v к вершине w, при этом вершина w смежная с вершиной v.
• Шаблон:ЯкорьОстовное дерево (остов) (неориентированного) связного графа <math>G = (V,E)</math> — всякий частичный граф <math>S=(V,T)</math>, являющийся деревом.
• Шаблон:ЯкорьОстовный подграф — подграф, содержащий все вершины.

П

• Шаблон:ЯкорьПаросочетание — набор попарно несмежных рёбер.
• Шаблон:ЯкорьПетля — ребро, начало и конец которого находятся в одной и той же вершине.
• Шаблон:ЯкорьПересечение графов (помеченных графов <math>G_1=(X_1, U_1)</math> и <math>G_2=(X_2, U_2)</math>) — граф <math>G_1 \cap G_2</math>, множеством вершин которого является <math>X_1 \cap X_2</math>, а множеством рёбер — <math>U=U_1 \cap U_2</math>.
• Шаблон:ЯкорьПеречисление графов — подсчёт числа неизоморфных графов в заданном классе (с заданными характеристиками).
• Шаблон:ЯкорьПериферийная вершина — вершина, эксцентриситет которой равен диаметру графа.
• Шаблон:ЯкорьПланарный граф — граф, который может быть изображён (уложен) на плоскости без пересечения рёбер. Изоморфен плоскому графу, то есть является графом с пересечениями, но допускающий его плоскую укладку, поэтому может отличаться от плоского графа изображением на плоскости. Таким образом, может быть разница между плоским графом и планарным графом при изображении на плоскости.
• Шаблон:ЯкорьПлоский граф — геометрический граф, в котором никакие два ребра не имеют общих точек, кроме инцидентной им обоим вершины (не пересекаются). Является уложенным графом на плоскости.
• Шаблон:ЯкорьПодграф исходного графа — граф, содержащий некое подмножество вершин данного графа и некое подмножество инцидентных им рёбер. (ср. Суграф.) По отношению к подграфу исходный граф называется суперграфом
• Шаблон:ЯкорьПолный граф — граф, в котором для каждой пары вершин <math>v_1, v_2</math>, существует ребро, инцидентное <math>v_1</math> и инцидентное <math>v_2</math> (каждая вершина соединена ребром с любой другой вершиной).
• Шаблон:ЯкорьПолный инвариант графа — числовая характеристика графа или их упорядоченный вектор, значения которой необходимо и достаточно для установления изоморфизма графов.
• Шаблон:ЯкорьПолным двудольным называется двудольный граф, в котором каждая вершина одного подмножества соединена ребром с каждой вершиной другого подмножества
• Шаблон:ЯкорьПолустепень захода в орграфе для вершины <math>v</math> — число дуг, входящих в вершину. Обозначается <math>d^+(v)</math>, <math>\mathrm{deg}^+(v)</math>, <math>\mathrm{indeg}(v)</math> или <math>d_t(v)</math>.
• Шаблон:ЯкорьПолустепень исхода в орграфе для вершины <math>v</math> — число дуг, исходящих из вершины. Обозначается <math>d^-(v)</math>, <math>\mathrm{deg}^-(v)</math>, <math>\mathrm{outdeg}(v)</math> или <math>d_o(v)</math>.
• Шаблон:ЯкорьПомеченный граф — граф, вершинам или дугам которого присвоены какие-либо метки, например, натуральные числа или символы какого-нибудь алфавита.
• Шаблон:ЯкорьПорождённый подграф — подграф, порождённый подмножеством вершин и множеством всех рёбер исходного графа, которые соединяют вершины из заданного подмножества. Содержит не обязательно все вершины графа, но эти вершины соединены такими же рёбрами, как в графе.
• Шаблон:ЯкорьПорядок графа — количество вершин графа.<ref> Дистель Р. Теория графов Пер. с англ. — Новосибирск: Изд-во Ин-та математики, 2002. — С. 16.</ref>
• Шаблон:ЯкорьПравильная раскраска графа — раскраска, при которой каждый цветной класс является независимым множеством. Иначе говоря, в правильной раскраске любые две смежные вершины должны иметь разные цвета.
• Шаблон:ЯкорьПроизведение графов — для данных графов <math>G_1=(V_1,E_1)</math> и <math>G_2=(V_2,E_2)</math> произведением называется граф <math>G = (V,E)</math>, вершины которого <math>V(G) = V_1 \times V_2</math> — декартово произведение множеств вершин исходных графов.
• Шаблон:ЯкорьПростая цепь — маршрут, в котором все вершины различны.
• Шаблон:ЯкорьПростой граф — граф, в котором нет кратных рёбер и петель.
• Шаблон:ЯкорьПростой путь — путь, все вершины которого попарно различны<ref name="Кузнецов">Кузнецов О. П., Адельсон-Вельский Г. М. / Дискретная математика для инженера. / М.: Энергия, 1980—344 с., ил. Стр. 120—122</ref>. Другими словами, простой путь не проходит дважды через одну вершину.
  • Шаблон:ЯкорьПростой цикл — цикл, не проходящий дважды через одну вершину.
• Шаблон:ЯкорьПсевдограф — граф, который может содержать петли и/или кратные рёбра.

• Пустой граф (нуль-граф) — граф без рёбер.
• Шаблон:ЯкорьПуть — последовательность рёбер (в неориентированном графе) и/или дуг (в ориентированном графе), такая, что конец одной дуги (ребра) является началом другой дуги (ребра). Или последовательность вершин и дуг (рёбер), в которой каждый элемент инцидентен предыдущему и последующему<ref name="Кузнецов" />. Может рассматриваться как частный случай маршрута.
• Шаблон:ЯкорьПуть в орграфе — последовательность вершин 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. Графически эти функции представляются надписыванием меток на вершинах и дугах. Множество меток может разделяться на два непересекающихся подмножества меток вершин и меток дуг.
• Шаблон:ЯкорьРазрез — множество рёбер, удаление которого делает граф несвязным.
• Шаблон:ЯкорьРамочный граф — граф, который можно нарисовать на плоскости таким способом, что любая ограниченная грань является четырёхугольником и любая вершина с тремя и менее соседями инцидентна неограниченной грани.<ref>Шаблон:Статья</ref>
• Шаблон:ЯкорьРаскраска графа — разбиение вершин на множества (называемые цветами). Если при этом нет двух смежных вершин, принадлежащих одному и тому же множеству (то есть две смежные вершины всегда разного цвета), то такая раскраска называется правильной.
• Расстояние между вершинами — длина кратчайшей цепи (в орграфе пути), соединяющей заданные вершины. Если такой цепи (пути) не существует, расстояние полагается равным бесконечности.
• Шаблон:ЯкорьРёберное покрытие — множество рёбер графа такое, что каждая вершина инцидентна хотя бы одному ребру из этого множества.
• Шаблон:ЯкорьРёберный граф неориентированного графа — это граф, представляющий соседство рёбер графа.
• Шаблон:ЯкорьРебро — базовое понятие. Ребро соединяет две вершины графа.
• Шаблон:ЯкорьРегулярный граф — граф, степени всех вершин которого равны. Степень регулярности является инвариантом графа и обозначается <math>r(G)</math>. Для нерегулярных графов <math>r(G)</math> не определено. Регулярные графы представляют особую сложность для многих алгоритмов.
  • Регулярный граф степени 0 (вполне несвязный граф, пустой граф, нуль-граф) — граф без рёбер.

С

• Шаблон:ЯкорьСамодвойственный граф — граф, изоморфный своему двойственному графу.
• Шаблон:ЯкорьСверхстройное (звездообразное) дерево — дерево, в котором имеется единственная вершина степени больше 2.
• Шаблон:ЯкорьСвязность. Две вершины в графе связаны, если существует соединяющая их (простая) цепь.
• Шаблон:ЯкорьСвязный граф — граф, в котором все вершины связаны.
• Шаблон:ЯкорьСечение графа — множество рёбер, удаление которых делит граф на два изолированных подграфа, один из которых, в частности, может быть тривиальным графом.
• Шаблон:ЯкорьСеть — в принципе, то же, что и граф, хотя сетями обычно называют графы, вершины которых определённым образом помечены.
  • Ориентированная сеть — ориентированный граф, не содержащий контуров.
• Шаблон:ЯкорьСильная связность. Две вершины в ориентированном графе сильно связаны, если существует путь из первой во вторую и из второй в первую.
  • Шаблон:ЯкорьСильно связный орграф — орграф, в котором все вершины сильно связаны.
• Шаблон:ЯкорьСмежность — понятие, используемое в отношении только двух рёбер либо только двух вершин: Два ребра, инцидентные одной вершине, называются смежными; две вершины, инцидентные одному ребру, также называются смежными. (ср. Инцидентность.)
• Шаблон:ЯкорьСмешанный граф — граф, содержащий как ориентированные, так и неориентированные рёбра.
• Шаблон:ЯкорьСовершенное паросочетание — паросочетание, содержащее все вершины графа.
• Шаблон:ЯкорьСоединением двух графов <math>G_1=(V_1,E_1)</math> и <math>G_2=(V_2,E_2)</math>, не имеющих общих вершин, называется граф <math>G_1+G_2=(V_1 \cup V_2,E_1 \cup E_2 \cup V_1 \times V_2 \cup V_2 \times V_1)</math>.<ref>

Шаблон:Статья</ref> Из определения видно, что соединение графов обладает свойствами коммутативности и ассоциативности

• Шаблон:ЯкорьСпектр графа — множество всех собственных значений матрицы смежности с учётом кратных рёбер.
• Шаблон:ЯкорьСтепень вершины — количество рёбер графа G, инцидентных вершине x. Обозначается <math>d(x)</math>. Минимальная степень вершины графа G обозначается <math>\delta(G)</math>. а максимальная — <math>\Delta(G)</math>.
• Шаблон:ЯкорьСтягивание ребра графа — замена концов ребра одной вершиной, соседями новой вершины становятся соседи этих концов. Граф <math>G_1</math> стягиваем к <math>G_2</math>, если второй можно получить из первого последовательностью стягиваний рёбер.
• Шаблон:ЯкорьСуграф (частичный граф) исходного графа — граф, содержащий все вершины исходного графа и подмножество его рёбер. (ср. Подграф.)
• Шаблон:ЯкорьСуперграф — любой граф, содержащий исходный граф (то есть для которого исходный граф является подграфом)

Т

• Шаблон:ЯкорьТета-граф — граф, состоящий из объединения трёх путей, не имеющих внутри общих вершин, у которых конечные вершины одни и те же<ref>

Шаблон:Книга</ref>

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

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

У

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

Ф

• Шаблон:Якорьn-фактор графа — регулярный остовный подграф степени <math>n</math>.
• Шаблон:Якорьn-факторизация графа — разбиение графа на независимые n-факторы.

Х

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

Ц

• Шаблон:ЯкорьЦентр графа — множество вершин <math>W = \left\{u_1,u_2,...,u_n\right\}</math>, для которых справедливо равенство: <math>\forall i=1,...,n : \varepsilon(u_i) = r(G)</math>, где <math>\varepsilon</math> — эксцентриситет вершины, а <math>r</math> — радиус графа.
• Шаблон:ЯкорьЦепь в графе — маршрут, все рёбра которого различны. Если все вершины (а тем самым и рёбра) различны, то такая цепь называется простой (элементарной). В цепи <math>v_0, e_1, ... , e_k, v_k</math> вершины <math>v_0</math> и <math>v_k</math> называются концами цепи. Цепь с концами u и v соединяет вершины u и v. Цепь, соединяющая вершины u и v, обозначается <math>\left\langle u,v\right\rangle</math>. Для орграфов цепь называется орцепью.

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

• Шаблон:ЯкорьШаблон:ЯкорьЦикл — замкнутая цепь. Для орграфов цикл называется контуром.
  • Шаблон:Якорь Цикл (простой цикл) в орграфе — простой путь длины не менее 1, который начинается и заканчивается в одной и той же вершине.
  • Шаблон:Якорь Цикл Гамильтона — то же, что и Гамильтонов цикл.
• Шаблон:ЯкорьЦикломатическое число графа — минимальное число рёбер, которые надо удалить, чтобы граф стал ациклическим. Для связного графа существует соотношение: <math>p_1(G) = p_0(G) + |E(G)| - |V(G)|,</math> где <math>p_1(G)</math> — цикломатическое число, <math>p_0</math> — число компонент связности графа, <math>|E(G)|</math> — число рёбер, а <math>|V(G)|</math> — число вершин.

Ч

• Шаблон:ЯкорьЧастичный граф — то же, что и суграф.
• Шаблон:ЯкорьЧётный граф — то же, что и двудольный граф.
• Шаблон:ЯкорьЧисло вершинного покрытия — размер наименьшего вершинного покрытия в графе.
• Шаблон:ЯкорьЧисло независимости — размер наибольшего независимого множества вершин в графе.
• Шаблон:ЯкорьЧисло паросочетания  — размер наибольшего паросочетания в графе.
• Шаблон:ЯкорьЧисло рёберного покрытия — размер наименьшего рёберного покрытия в графе.

Ш

• Шаблон:ЯкорьШарнир — вершина графа, в результате удаления которой вместе со всеми инцидентными ей рёбрами количество компонент связности в графе возрастает.
• Шаблон:ЯкорьШестерёнка (обозначается <math>G_n</math>) — граф, получаемый из колеса путём размещения дополнительных вершин между каждой парой смежных вершин периметра. Шестерёнки принадлежат семейству рамочных графов и играют важную роль при описании запрещённых подграфов рамочных графов<ref>Шаблон:Статья.</ref>

Э

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

Ссылки

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

Литература

• Дистель Р. Теория графов Пер. с англ. − Новосибирск: Изд-во Ин-та математики, 2002. − 336 c.
• Шаблон:Книга