Терминология теории графов

Графы

Граф (или неориентированный граф) — упорядоченная пара [math](V, E)[/math] из непустого множества [math]V[/math] вершин и множества [math]E \subseteq V^{(2)}[/math] рёбер, где через [math]V^{(2)}[/math] обозначается множество всех двухэлементных подмножеств (2-сочетаний) множества [math]V[/math].

Граф называется пустым (или нуль-графом), если его множество рёбер пусто. Граф называется полным, если он содержит все возможные рёбра.

Множество вершин графа [math]G[/math] обозначается через [math]V(G)[/math] или [math]VG[/math], множество рёбер — через [math]E(G)[/math] или [math]EG[/math]. Число [math]|V(G)|[/math] вершин графа [math]G[/math] называется его порядком и обозначается через [math]|G|[/math].

Граф порядка [math]n[/math] называется помеченным, если его вершинам присвоены некоторые метки, например, номера [math]1, 2, \ldots, n[/math].

Мультиграф — упорядоченная пара [math](V, E)[/math] из непустого множества [math]V[/math] вершин и семейства (мультимножества) [math]E \subseteq V^{(2)}[/math] рёбер. Одинаковые рёбра мультиграфа называются кратными. Другими словами, мультиграф — это обобщение графа на случай кратных рёбер.

Псевдограф — упорядоченная пара [math](V, E)[/math] из непустого множества [math]V[/math] вершин и семейства [math]E[/math] неупорядоченных пар (2-сочетаний с повторениями) вершин. Термин псевдограф обобщает понятие мультиграфа, допуская наличие петель — рёбер, соединяющих вершину саму с собой.

Ориентированный граф (или орграф) — упорядоченная пара [math](V, A)[/math] из непустого множества [math]V[/math] вершин и множества [math]A \subseteq V^2[/math] ориентированных рёбер (или дуг), где через [math]V^2[/math] обозначается множество всех упорядоченных пар (2-размещений), состоящих из двух различных элементов [math]V[/math].

Множество дуг орграфа [math]G[/math] обозначается через [math]A(G)[/math] или [math]AG[/math]. Аналогично определяются ориентированный мультиграф, с той лишь разницей, что совпадающие дуги ориентированного мультиграфа называются параллельными.

Основание орграфа [math]G[/math] — неориентированный мультиграф, получающийся в результате снятия ориентации с дуг орграфа [math]G[/math].

Смешанный граф — граф, в котором могут быть как дуги, так и неориентированные рёбра.

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

Деревья

Дерево — связный граф, не содержащий циклов.

Ориентированный граф [math]D = (V, A)[/math] называется ориентированным деревом с корнем [math]r \in V[/math], если каждая его вершина достижима из [math]r[/math] и основание [math]D_b[/math] графа [math]D[/math] является деревом.

Лес (или ациклический граф) — граф без циклов. Каждая компонента леса является деревом. Заметим, что речь здесь идёт только о неориентированном простом графе.

Ациклический орграф — орграф без циклов. Стоит отметить, что основание ациклического орграфа может не являться ациклическим графом (лесом).

Подграфы

Граф [math]H[/math] называется подграфом (или частью) графа [math]G[/math], если [math]V(H) \subseteq V(G)[/math] и [math]E(H) \subseteq E(G)[/math].

Остовный подграф (или фактор) — подграф, содержащий все вершины исходного графа.

Остов (или каркас) графа [math]G[/math] — максимальный по включению лес, являющийся подграфом графа [math]G[/math]. Другими словами, остов — это подграф графа [math]G[/math], состоящий из одного остовного дерева для каждой компоненты связности графа [math]G[/math]. Стоит отметить, что не всякий остовный лес является остовом, поскольку, к примеру, пустой остовный подграф является лесом, но не является остовом, если граф содержит хотя бы одно ребро.

Если множество вершин подграфа [math]H[/math] графа [math]G[/math] есть [math]S[/math], а сам подграф [math]H[/math] максимальный (по включению) среди всех таких подграфов, то подграфа [math]H[/math] называется подграфом, порождённым множеством [math]S[/math], или просто порождённым подграфом. Другими словами, подграф [math]H[/math] графа [math]G[/math] называется порождённым, если он содержит все возможные (для своего множества вершин) рёбра графа [math]G[/math].

Цепи, циклы, пути

В неориентированном графе

Маршрут — чередующаяся последовательность [math]v_0, e_1, v_1, e_2, \ldots, e_{\ell}, v_{\ell} \tag{1}[/math] вершин и рёбер, в которой [math]e_i = \{\,v_{i-1}, v_i\,\}\label{route}[/math] ([math]i = \overline{1, \ell}[/math]). Вершины [math]v_0[/math] и [math]v_{\ell}[/math] называются крайними, а все остальные — промежуточными (или внутренними). Маршрут, содержащий вершины [math]v_0[/math] и [math]v_{\ell}[/math] в качестве крайних, называется [math](v_0, v_{\ell})[/math]-маршрутом.

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

Цепь — маршрут, все рёбра которого попарно различны.

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

Цепь в графе также можно рассматривать как подграф этого графа. Тем не менее подграф, соответствующий цепи, однозначно (с точностью до направления) задаёт эту цепь, если и только если она является простой.

Циклический маршрут — маршрут, крайние вершины которого совпадают.

Цикл (или циклическая цепь) — циклический маршрут, являющийся цепью.

Простой цикл — простая циклическая цепь.

Гамильтонов цикл — простой цикл, содержащий все вершины графа.

Эйлеров цикл — цикл, содержащий все рёбра графа.

В ориентированном графе

Ориентированный маршрут (или просто маршрут) — последовательность вида (1) для ориентированного графа, в которой [math]e_i = (v_{i - 1}, v_i)[/math]. Понятия цепи, циклического маршрута и цикла переносятся на случай ориентированного графа без изменений.

Путь — ориентированный маршрут, все вершины которого, кроме, возможно, крайних, различны.

Контур — циклический путь.

Полумаршрут — последовательность вида (1), в которой [math]e_i = (v_{i-1}, v_i)[/math] или [math]e_i = (v_i, v_{i-1})[/math]. Аналогично определяются полуцепь, полупуть и полуконтур.

Если в орграфе существует [math](u, v)[/math]-маршрут, то говорят, что вершина [math]v[/math] достижима из вершины [math]u[/math]. Любая вершина считается достижимой из самой себя.

Связность

В неориентированном графе

Связный граф — граф, любые две несовпадающие вершины которого соединены маршрутом.

Связная компонента (или компонента связности, или просто компонента) графа [math]G[/math] — максимальный (по включению) связный подграф графа [math]G[/math].

Область связности графа — множество всех вершин одной компоненты связности этого графа.

Точкой сочленения называется вершина, при удалении которой число компонент графа увеличивается.

Связный граф, не содержащий точек сочленения, называется двусвязным или вершинно двусвязным.

Мостом называется ребро, при удалении которого число компонент графа увеличивается.

Связный граф, не содержащий мостов, называется рёберно двусвязным.

В ориентированном графе

Орграф называется сильным (или сильносвязным), если любые две его вершины достижимы друг из друга.

Орграф называется односторонним (или односторонне связным), если для любой пары его вершин по меньшей мере одна достижима из другой.

Орграф называется слабым (или слабосвязным, или просто связным), если любые две его вершины соединены полупутём.

Сильная и слабая компоненты определяются аналогично компоненте в неориентированном графе.