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

Эта страница — глоссарий . См. также основную статью : Теория графов

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

А

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

Б

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

В

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

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

Г

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

Д

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

Е

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

З

Граф-звезда — полный двудольный граф $K_{1,b}$ $K_{{1,b}}$ .

И

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

К

Клетка — наименьшего для заданной степени вершин.
Клика — подмножество вершин графа, полностью соединённых друг с другом, то есть подграф, являющийся .
- Кликовое число ( англ. clique number) — число (G) вершин в наибольшей клике. Другие названия — густота, плотность.
- Максимальная клика — клика с максимально возможным числом вершин среди клик графа.
Колесо (обозначается W _n ) — граф с n вершинами (n ≥ 4), образованный соединением единственной вершины со всеми вершинами ( n -1)-цикла.
— просто ориентированный граф.
Конечный граф — граф, содержащий конечное число вершин и рёбер.
Конструктивное перечисление графов — получение полного списка графов в заданном классе.
Компонента связности графа — такое подмножество , для любых двух вершин которого существует из одной в другую, и не существует пути из вершины этого подмножества в вершину не из этого подмножества.
Компонента сильной связности графа , слой — максимальное множество вершин , такое, что для любых двух вершин из этого множества существует как из первой во вторую, так и из второй в первую.
Контур — замкнутый .
Корень дерева — выбранная ; в — вершина с нулевой степенью захода.
Коцикл — минимальный , минимальное множество рёбер, удаление которого делает граф несвязным.
Кратные рёбра — несколько , одной и той же паре вершин. Встречаются в .
Кубический граф — регулярный граф степени 3, то есть граф, в котором каждой вершине инцидентно ровно три ребра.
k-дольный граф — граф G, у которого c(G)=k
— , в котором не существует набора $V'$ $V'$ из $k-1$ $k-1$ или менее , такого, что удаление всех вершин $V'$ $V'$ и инцидентных им нарушает связность графа. В частности, является 1-связным, а — 2-связным.

Л

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

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

М

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

Н

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

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

О

Обхват — длина наименьшего в графе.
Объединение графов (помеченных графов $G_{1}=(X_{1},U_{1})$ $G_{1}=(X_{1},U_{1})$ и $G_{2}=(X_{2},U_{2})$ $G_{2}=(X_{2},U_{2})$ ) — граф $G_{1}\cup G_{2}$ $G_{1}\cup G_{2}$ , множеством вершин которого является $X_{1}\cup X_{2}$ $X_{1}\cup X_{2}$ , а множеством рёбер — $U=U_{1}\cup U_{2}$ $U=U_{1}\cup U_{2}$ .
Окрестность порядка k — множество вершин на расстоянии k от заданной вершины v ; иногда толкуется расширительно как множество вершин, отстоящих от v на расстоянии не больше k .
Окружение — множество вершин, смежных с заданной.
Орграф , ориентированный граф G = (V,E) есть пара множеств, где V — множество вершин (узлов), E — множество дуг (ориентированных рёбер). Дуга — упорядоченная пара вершин (v, w), где вершину v называют началом, а w — концом дуги. Можно сказать, что дуга v → w ведёт от вершины v к вершине w, при этом вершина w смежная с вершиной v.
Остовное дерево ( остов ) (неориентированного) связного графа $G=(V,E)$ $G=(V,E)$ — всякий $S=(V,T)$ $S=(V,T)$ , являющийся .
Остовный подграф — подграф, содержащий все вершины.

П

Паросочетание — набор попарно несмежных рёбер.
Петля — ребро, начало и конец которого находятся в одной и той же вершине.
Пересечение графов (помеченных графов $G_{1}=(X_{1},U_{1})$ $G_{1}=(X_{1},U_{1})$ и $G_{2}=(X_{2},U_{2})$ $G_{2}=(X_{2},U_{2})$ ) — граф $G_{1}\cap G_{2}$ $G_{1}\cap G_{2}$ , множеством вершин которого является $X_{1}\cap X_{2}$ $X_{1}\cap X_{2}$ , а множеством рёбер — $U=U_{1}\cap U_{2}$ $U=U_{1}\cap U_{2}$ .
Перечисление графов — подсчёт числа неизоморфных графов в заданном классе (с заданными характеристиками).
— вершина, которой равен диаметру графа.
Планарный граф — граф, который может быть изображён ( ) на плоскости без пересечения рёбер. плоскому графу, то есть является графом с пересечениями, но допускающий его плоскую укладку, поэтому может отличаться от изображением на плоскости. Таким образом, может быть разница между плоским графом и планарным графом при изображении на плоскости.
Плоский граф — , в котором никакие два ребра не имеют общих точек, кроме инцидентной им обоим вершины (не пересекаются). Является графом на плоскости.
Подграф исходного графа — граф, содержащий некое подмножество вершин данного графа и некое подмножество им рёбер. (ср. .) По отношению к подграфу исходный граф называется
Полный граф — граф, в котором для каждой пары вершин $v_{1},v_{2}$ $v_{1},v_{2}$ , существует ребро, инцидентное $v_{1}$ $v_{1}$ и инцидентное $v_{2}$ $v_{2}$ (каждая вершина соединена ребром с любой другой вершиной).
Полный инвариант графа — числовая характеристика графа или их упорядоченный вектор, значения которой необходимо и достаточно для установления графов.
Полным двудольным называется , в котором каждая вершина одного подмножества соединена ребром с каждой вершиной другого подмножества
Полустепень захода в для вершины $v$ $v$ — число дуг, входящих в вершину. Обозначается $d^{+}(v)$ $d^{+}(v)$ , $\mathrm {deg} ^{+}(v)$ $\mathrm {deg} ^{+}(v)$ , $\mathrm {indeg} (v)$ $\mathrm {indeg} (v)$ или $d_{t}(v)$ $d_{t}(v)$ .
Полустепень исхода в для вершины $v$ $v$ — число дуг, исходящих из вершины. Обозначается $d^{-}(v)$ $d^{-}(v)$ , $\mathrm {deg} ^{-}(v)$ $\mathrm {deg} ^{-}(v)$ , $\mathrm {outdeg} (v)$ $\mathrm {outdeg} (v)$ или $d_{o}(v)$ $d_{o}(v)$ .
Помеченный граф — граф, вершинам или дугам которого присвоены какие-либо метки, например, натуральные числа или символы какого-нибудь алфавита.
Порождённый подграф — подграф, порождённый множеством рёбер исходного графа. Содержит не обязательно все вершины графа, но эти вершины соединены такими же рёбрами, как в графе.
Порядок графа — количество вершин графа.
— раскраска , при которой каждый цветной класс является независимым множеством. Иначе говоря, в правильной раскраске любые две смежные вершины должны иметь разные цвета.
Произведение графов — для данных графов $G_{1}=(V_{1},E_{1})$ $G_{1}=(V_{1},E_{1})$ и $G_{2}=(V_{2},E_{2})$ $G_{2}=(V_{2},E_{2})$ произведением называется граф $G=(V,E)$ $G=(V,E)$ , вершины которого $V(G)=V_{1}\times V_{2}$ $V(G)=V_{1}\times V_{2}$ — декартово произведение множеств вершин исходных графов.
Простая цепь — , в котором все вершины различны.
Простой граф — , в котором нет и .
— , все вершины которого попарно различны . Другими словами, простой путь не проходит дважды через одну вершину.
- Простой цикл — , не проходящий дважды через одну вершину.
Псевдограф — граф, который может содержать и/или кратные рёбра.

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

С

Самодвойственный граф — граф, своему .
Сверхстройное (звездообразное) дерево — дерево, в котором имеется единственная вершина степени больше 2.
Связность . Две вершины в графе связаны , если существует соединяющая их (простая) .
Связный граф — граф, в котором все вершины связаны.
Сечение графа — множество рёбер, удаление которых делит граф на два изолированных подграфа, один из которых, в частности, может быть тривиальным графом.
Сеть — в принципе, то же, что и , хотя сетями обычно называют графы, которых определённым образом помечены.
- Ориентированная сеть — ориентированный граф, не содержащий контуров.
Сильная связность . Две вершины в сильно связаны , если существует путь из первой во вторую и из второй в первую.
- Сильно связный орграф — , в котором все вершины сильно связаны.
Смежность — понятие, используемое в отношении только двух либо только двух : Два ребра, одной вершине, называются смежными ; две вершины, одному ребру, также называются смежными . (ср. .)
Смешанный граф — граф, содержащий как ориентированные, так и неориентированные .
Совершенное паросочетание — паросочетание, содержащее все вершины графа.
Соединением двух графов $G_{1}=(V_{1},E_{1})$ $G_{1}=(V_{1},E_{1})$ и $G_{2}=(V_{2},E_{2})$ $G_{2}=(V_{2},E_{2})$ , не имеющих общих вершин, называется граф $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})$ $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})$ .

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

Спектр графа — множество всех собственных значений матрицы смежности с учётом кратных рёбер.
Степень вершины — количество рёбер графа G , вершине x . Обозначается $d(x)$ $d(x)$ . Минимальная степень вершины графа G обозначается $\delta (G)$ $\delta (G)$ . а максимальная — $\Delta (G)$ $\Delta (G)$ .
Стягивание ребра графа — замена концов ребра одной вершиной, соседями новой вершины становятся соседи этих концов. Граф $G_{1}$ $G_{1}$ стягиваем к $G_{2}$ $G_{2}$ , если второй можно получить из первого последовательностью стягиваний рёбер.
Суграф ( частичный граф ) исходного графа — граф, содержащий все вершины исходного графа и подмножество его . (ср. .)
Суперграф — любой граф, содержащий исходный граф (то есть для которого исходный граф является )

Т

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

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

У

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

Ф

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

Х

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

Ц

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

В некоторых источниках простая цепь — цепь, которой различны, что является более слабым условием.
Цикл — замкнутая . Для цикл называется .
- Цикл ( простой цикл ) в — не менее 1, который начинается и заканчивается в одной и той же вершине.
- Цикл Гамильтона — то же, что и .
Цикломатическое число графа — минимальное число рёбер, которые надо удалить, чтобы граф стал . Для связного графа существует соотношение: $p_{1}(G)=p_{0}(G)+|E(G)|-|V(G)|,$ $p_{1}(G)=p_{0}(G)+|E(G)|-|V(G)|,$ где $p_{1}(G)$ $p_{1}(G)$ — цикломатическое число, $p_{0}$ $p_{0}$ — число графа, $|E(G)|$ $|E(G)|$ — число , а $|V(G)|$ $|V(G)|$ — число .

Ч

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

Ш

Шарнир — графа , в результате удаления которой вместе со всеми ей количество в графе возрастает.
Шестерёнка (обозначается $G_{n}$ $G_{n}$ ) — граф, получаемый из путём размещения дополнительных вершин между каждой парой смежных вершин . Шестерёнки принадлежат семейству и играют важную роль при описании запрещённых подграфов рамочных графов

Э

Эйлеров граф — граф, в котором существует , содержащий все рёбра графа по одному разу (вершины могут повторяться).
Эйлерова цепь (или эйлеров цикл ) — ( ), которая содержит все рёбра графа (вершины могут повторяться).
Эксцентриситет вершины — максимальное из всех минимальных расстояний от других вершин до данной вершины.
Элементарный путь — , вершины которого, за исключением, быть может, первой и последней, различны. Другими словами, простой путь не проходит дважды через одну вершину, но может начаться и закончиться в одной и той же вершине, в таком случае он называется (элементарным циклом).
Элементарным стягиванием называется такая процедура: берём (вместе с инцидентными ему , например, 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.
Харари Ф. Теория графов. — М. : УРСС , 2003. — 300 с. — ISBN 5-354-00301-6 .