v.990916

Основой для составления указателя послужил словарь терминов и определений, включенный в монографию: М.И.Нечепуренко, В.К.Попков, С.М.Майнагашев и др. Алгоритмы и программы решения задач на графах и сетях. - Новосибирск, Наука (сибирское отделение), 1990.

Рекомендация: указатель имеет относительно большой размер - для ускорения доступа сохраните этот файл на своей машине и работайте с локальной копией.

Содержание

От редактора

В указатель были добавлены некоторые новые определения. Повторявшиеся в разных частях оригинального указателя определения оставлены в единственном экземляре; взаимное расположение статей частично изменено. Изменения и дополнения по сравнению с оригиналом заключены в квадратные скобки; вновь добавленные определения помечены моими инициалами.

Редактор: А.Чернобаев.

1. Элементы

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

1.1. Типы элементов

Вершина (узел, точка, 0-симплекс) (vertex, node) [ - элемент множества вершин графа - А.Ч.]

Ребро (дуга, линия, ветвь, 1-симплекс) (edge, link) [ - элемент множества ребер графа - А.Ч.]

Дуга (arc) - ориентированное ребро [ребро ориентированного графа - А.Ч.]

Инцидентность вершины и ребра (incident vertex and edge) - вершина графа v и некоторое его ребро e называются инцидентными, если e=(v,w) или e=(w,v), где w - некоторая вершина графа. - А.Ч.

Инцидентность вершин (incident vertices) - две вершины графа называются инцидентными (смежными), если существует ребро, инцидентное обеим этим вершинам (т.е. существует ребро, которое соединяет эти вершины). - А.Ч.

Петля (loop) - ребро графа, инцидентное единственной вершине.

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

Исток (source) - вершина, являющаяся одним из полюсов двухполюсного ориентированного графа, которой инцидентны только исходящие дуги.

Сток (sink) - один из полюсов графа, которому инцидентны только заходящие дуги.

Корень (root) - специально выделенная вершина дерева.

Антитупик (антитупиковая вершина) - вершина орграфа, которой инцидентны только исходящие дуги.

Тупик (тупиковая вершина) - вершина орграфа, которой инцидентны только заходящие дуги.

Висячая вершина - вершина, инцидентная единственному ребру.

Голая вершина - вершина, которая не имеет инцидентных ребер.

Центр (центральная вершина) - вершина, эксцентриситет которой равен радиусу.

Периферийная вершина - вершина, эксцентриситет которой равен диаметру.

Полюс - выделенная вершина графа. Обычно эти вершины являются истоками и стоками в двухполюсных и многополюсных сетях.

Псевдовершина - вершина, образующаяся при стягивании некоторого множества вершин.

Хорда - ребро графа, не принадлежащее остову.

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

Висячее ребро - ребро, инцидентное висячей вершине.

Гиперребро - ребро гиперграфа.

Мультиребро - множество ребер, инцидентных одной и той же паре вершин.

Кратные ребра (duplicate, or parallel, or multiple edges) ребра, инцидентные одной и той же паре вершин; . - А.Ч.

1.2. Свойства элементов.

Степень вершины (degree) - число инцидентных [этой вершине - А.Ч.] ребер, S(х).

Валентность вершины - число инцидентных ребер плюс число инцидентных петель, Y(х).

Полустепень исхода вершины (outdegree) - число инцидентных исходящих дуг, S^-(х).

Полустепень захода вершины (indegree) - число инцидентных заходящих дуг, S⁺(х).

Вес вершины - число (действительное, целое или рациональное), поставленное в соответствие данной вершине (интерпретируется как стоимость, пропускная способность и т. д.).

Эксцентриситет вершины (eccentricity) х - максимальное расстояние от х до других вершин графа.

Надежность вершины - вероятность существования вершины в графе.

Инвариант вершины графа (l-вариант) - характеристика вершины, инвариантная относительно автоморфизмов вершины.

Степень ребра - сумма степеней вершин, инцидентных данному ребру минус два, или число смежных ребер.

Вес, длина ребра - число или несколько чисел, которые интерпретируются как длина, пропускная способность и т. д.

Мощность мультиребра - число ребер в мультиребре.

Надежность ребра - вероятность существования ребра в графе.

1.3. Отношения элементов.

Смежность вершин. Две вершины смежны в графе тогда и только тогда, когда существует ребро графа, инцидентное им обоим.

Удаление вершины. Из графа удаляется вершина вместе с инцидентными ребрами.

Добавление вершины. К заданному множеству вершин (х₁, x₂, ... , x_k) добавляется новая вершина y, смежная с х₁, x₂, ... , x_k.

Разбиение (расщепление) вершины орграфа. Вместо вершины х, в которую входят дуги u₁¹, u₂¹, ..., u_k¹ и выходят дуги u₁⁰, u₂⁰, ... , u_n⁰, в граф добавляется упорядоченная пара смежных вершин (х', х''), таких, что в х' входят дуги u_i¹, а из х'' выходят дуги u_j⁰.

Достижимость (соединимость, связность) вершин. Вершина х достижима из у, если существует маршрут из х в у.

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

Сильная связность вершин. Вершины х и у сильно связны в орграфе G, если они взаимно достижимы.

Стягивание вершин. Заданное множество вершин объединяется в одну вершину, а полученные петли удаляются.

Две вершины s и t k-соединимы, если существует k независимых (s, t)-цепей.

Смежность ребер. Два ребра r₁ и r₂ смежны тогда и только тогда, когда существует по крайней мере одна вершина, инцидентная r₁ и r₂.

Удаление (ребра) дуги. В графе удаляется ребро без инцидентных вершин.

Ориентация ребра. Пара вершин, инцидентная ребру, упорядочивается.

Добавление ребра (дуги). Для заданной пары вершин х, у добавляется ребро (х, у).

Стягивание ребра (дуги) - вершины х и у, инцидентные заданному ребру, стягиваются.

Подразбиение [или подразделение - А.Ч.] ребра (дуги). Удаляется заданное ребро u=(х, у) и добавляется цепь (x₁, u₁, z, u₂, у).

2. Структуры.

Раздел содержит определение структур (графы, гиперграфы, матрицы, массивы, файлы и т. д.). В подразделах приводятся морфологическое описание структур, их свойства и отношения.

2.1. Определение типов структур.

Граф (graph) - пара G=(V, E), где V - множество объектов произвольной природы, называемых вершинами (vertices), а E - семейство пар e_i=(v_i1, v_i2), v_ijОV, называемых ребрами (edges). Соответственно, V называется множеством вершин (vertex set), а E - множеством ребер (edge set). Если порядок элементов, входящих в e_i, имеет значение, то граф называется ориентированным (directed graph), сокращенно - орграф (digraph), иначе - неориентированным (undirected graph). В дальнейшем будем считать, что термин "граф", применяемый без уточнений "ориентированный" или "неориентированный", обозначает неориентированный граф. - А.Ч.

Граф обыкновенный (simple graph) - граф, не содержащий петель и кратных ребер. Обыкновенные графы нередко называют просто графами; для того, чтобы отличить их от графов, содержащих кратные ребра, последние иногда называют мультиграфами. - А.Ч.

Мультиграф - граф, в котором имеются кратные ребра.

Граф полный (complete graph) - граф G=(X, R), в котором любая пара вершин инцидентна единственному ребру [т.е. это обыкновенный граф, в котором любая пара вершин смежна - А.Ч.]. Обозначается K_p, где р=|Х|, при этом |R|=p(p-1)/2.

Граф пустой (null graph) - граф G=(X, R), в котором R=Ж [обозначение - N_m].

Граф тривиальный - пустой граф, у которого |Х|=1.

Лес (ациклический граф) (forest, acyclic graph) - обыкновенный граф без циклов.

Дерево (tree) - связный ациклический граф // теоремы.

Треугольник - полный граф K₃.

Помеченный граф - граф с заданной нумерацией вершин и ребер.

n-раскрашиваемый граф - граф G, у которого хроматическое число c(G)Јn.

n-хроматический (n-дольный) граф (n-chromatic graph) - граф G, у которого хроматическое число c(G)=n.

Граф однозначно раскрашиваемый - граф G, у которого c(G)=n и любая n-раскраска графа G порождает одно и то же разбиение множества вершин Х.

Граф бихроматический (двудольный граф, граф Кенига) (bipartite graph) - 2-хроматический граф или граф, не содержащий нечетных циклов.

Граф двудольный полный (complete bipartite graph) - двудольный граф G=(X₁, X₂, R), у которого любая пара вершин хОX₁ и уОX₂ смежна. Обозначается K_m,n, где m=|X₁|, n=|X₂|, |R|=mЧn.

Веер (звезда) - двудольный полный граф K_1,n.

Многополюсная сеть (многополюсник) - сеть с выделенными вершинами.

Двуполюсная сеть - сеть с двумя выделенными вершинами.

Граф планарный (planar graph) - граф, укладываемый па плоскость без пересечения ребер // теоремы.

Граф плоский (flat graph) - планарный граф, уложенный на плоскость.

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

Сильносвязный орграф (сильный орграф) (strongly connected graph) - орграф, у которого любые две вершины взаимодостижимы.

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

Слабосвязный орграф (слабый орграф) - орграф, который после дезориентации дуг будет связным.

Транзитивное замыкание орграфа - орграф G'= (X, RИR'), полученный добавлением дуг R' к орграфу G=(X, R) так, что G' становится транзитивным.

Транзитивный орграф - орграф G=(X, R), у которого из существования дуг (х_i, x_j) и (x_j, x_k) следует существование дуги (x_i, x_k).

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

Антисимметричный граф - орграф, у которого отсутствует дуга из х_i в x_j, если существует дуга из x_j в х_i.

k-связный граф (k-вершинно-связный граф) - граф G, который при удалении любых k-1 вершин остается связным. Обозначается w(G) = k.

k-реберно-связный граф - граф G, который при удалении любых k-1 ребер остается связным. Обозначается l(G)=k.

Случайный граф - случайная величина, значениями которой являются графы.

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

Нестационарный граф - функция от времени, значениями которой являются графы.

Однородный [регулярный - А.Ч.] (k-регулярный) граф (k-regular graph) - граф, все вершины которого имеют одну и ту же степень, равную k.

Оптимальный по вероятности связности мультиграф - граф, обладающий максимальным значением вероятности связности среди всех (n, m)-графов и с одинаковыми надежностями ребер.

Эйлеров граф (Eulerian graph) - связный граф, не содержащий вершин нечетной степени.

(n, m)-граф - граф, имеющий в точности n вершин и m ребер.

Тождественный граф - граф, группа автоморфизмов которого состоит из единственного автоморфизма (тождественного).

Транзитивный граф (transitive graph) - граф, группа автоморфизмов которого транзитивна на вершинах.

Симметрический граф - граф, группа автоморфизмов которого действует транзитивно как на вершинах, так и на ребрах.

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

Сильнорегулярный граф - регулярный граф, каждая смежная (несмежная) пара вершин которого имеет одинаковое количество общих соседей m(l).

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

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

Граф с регулярной группой - транзитивный граф, удаление одной вершины из которого приводит к построению тождественного графа.

Граф с полурегулярной группой - однородный граф, удаление любой вершины из которого приводит к построению тождественного графа
 
Дополнительный граф к графу G - граф ~G называется дополнительным, если он содержит то же множество вершин, что и G, и две вершины в G смежны тогда и только тогда, когда эти вершины несмежны в G.

Реберный граф графа (line graph) G=(X, U) - граф U(G)=(U, Е) называются реберным, если каждой вершине uОU(G) сопоставлено ребро uОU и две вершины в U(G) смежны тогда и только тогда, когда соответствующие ребра смежны в графе G.

Граф инциденций обыкновенного графа G=(X, U) - двудольный граф I(G) = (X, U, Е), у которого вершины в первой доле совпадают с множеством X, а вершины второй доли соответствуют ребрам U графа G. Две вершины в I(G) смежны тогда и только тогда, когда соответствующие им элементы инцидентны в G.

Тотальный граф графа G=(X, U) - граф T(G) =(ХИU, Е) называется тотальным, если каждой вершине T(G) сопоставлен элемент (вершина или ребро) графа G и две вершины в T(G) смежны тогда и только тогда, когда соответствующие элементы графа G смежны или инцидентны.

Двойственный граф - каждой грани q_i плоского графа ставится в соответствие вершина z_i двойственного графа (мультиграфа). Две вершины z_i и z_j соединяются ребром u, если соответствующее ребро принадлежит граням q_i и q_j в исходном графе.

Матрица смежности (матрица смежности вершин, матрица смежность графа, матрица соседства) (adjacency matrix) - квадратная матрица A={a_ij} является матрицей смежности графа G, если при a_ij=l в графе G вершины x_i и x_j соединены l ребрами, при a_ij=0 вершины x_i и x_j в G несмежны.
Примечание: возможны другие варианты определения понятия матрицы смежности; во-первых, иногда считают, что матрица смежности может содержать только элементы 0 и 1 (или False и True), где a_ij=1, если вершины x_i и x_j соединены любым количеством ребер; во-вторых, диагональные элементы могут считаться равными 0 или 1. Таким образом, в каждом конкретном случае следует уточнять, какой именно вариант определения используется. - А.Ч.

Матрица междольной смежности (матрица соседства) двудольного графа G=(X, Y, R) - прямоугольная матрица B={b_ij}. Элемент b_ij=1, если вершина x_iОX смежна с вершиной у_iОY двудольного графа G и b_ij=0 в противном случае.

Матрица инциденций графа (incidence matrix) G=(X, R) - прямоугольная матрица M={m_ij}, m_ij=1, тогда и только тогда, когда вершина x_i инцидентна ребру r_j в графе G и m_ij=0 в противном случае.

Матрица расстояний (кратчайших цепей) графа (reachability matrix) G - квадратная матрица D={d_ij}, в которой элемент d_ij=r(x_i, x_j), т.е. численно равен расстоянию от вершины x_i до вершины x_j в графе G. Если из x_i недостижима вершина x_j, то d_ij=Ґ.

Матрица достижимостей орграфа G - квадратная матрица R={r_ij}, в которой элемент r_ij=1, если из вершины x_i достижима вершина x_j в орграфе G.

Массив степеней вершин - матрица стока, i-й элемент которой равен степени x_i вершины графа G.

Массив полустепени (степени (исхода) захода) вершин - матрица стока, i-й элемент которой равен полустепени исхода (захода) вершины x_i.

Массив ребер (дуг) - пара массивов IU(Q), OU(Q), задающих орграф G=(X, U), Q=|U|. Дуга u_k=(x_i, x_j), u_kОU, если IU(k)=i, OU(k)=j. Ребро графа задается парой противоположно ориентированных дуг.

Массив предшественников (для деревьев) - PR(l). В вершину с номером i входит дуга из вершины j=PR(i), l - число вершин.

Файл предшественников - совокупность двух массивов АI(Р), FI(R), задающих орграф G=(X, U), Р=|Х|, Q=|U|. Для любой вершины x_iОХ номера вершин из окрестности O^-(x_i) располагаются в массиве FI последовательно, начиная с номера AI(i) до номера AI(i+1)-1, i<P. Для i=P - до номера Q. Ребро графа задается парой противоположно ориентированных дуг.

Файл преемников - совокупность двух массивов АО(P), FO(R), задающих орграф G=(X, U), Р=|Х|, Q=|U|. Для любой вершины x_iОХ номера вершин из окрестности O⁺(x_i) располагаются в массиве FO последовательно, начиная с номера AO(i) до номера AO(i+1)-1, i<P. Для i=P - до номера Q. Ребро графа задается парой противоположно ориентированных дуг.

Полный файл преемников - совокупность двух массивов KAO(P+1), FO(R), задающих орграф G=(X, U), Р=|Х|, Q=|U|. Для любой вершины x_iОХ номера вершин из окрестности O⁺(x_i) располагаются в массиве FO последовательно, начиная с номера KAO(i) до номера KAO(i+1)-1. Ребро графа задается парой противоположно ориентированных дуг.

Файл инцидентных вершин - файл преемников или предшественников для графов.

Окрестность вершины - для графа G=(X, U) окрестностью вершины xОХ называется множество O(x) всех вершин, смежных с х. Для орграфа окрестностями O^-(x) и O⁺(x) будет множество всех вершин таких, что yОO^-(x), если (y, x)ОU, и yОO⁺(x), если (x, y)ОU.

2.2. Числовые характеристики и другие свойства графов.

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

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

Обхват графа - длина его минимального цикла.

Окружение графа - длина его самого длинного простого цикла.

Радиус графа (radius) - наименьший из эксцентриситетов его вершин.

Диаметр графа (diameter) - максимальный эксцентриситет его вершин.

Цикломатическое число n(G) неориентированного графа G=(X, U) - n(G)=|U| - |X| + k(G), где k(G) - число компонент связности графа G.

Хроматическое число (chromatic number) c(G) - наименьшее число n, для которого граф G имеет n-раскраску.

Хроматический класс c'(G) - наименьшее число n, для которого существует реберная n-раскраска.

Ахроматическое число Y(G) - наибольшее число n, для которого существует полная n-раскраска графа G.

Кликовое число (плотность) (clique number) - максимальный по числу вершин размер клики в графе G.

Число реберной независимости b(G) - наибольшее число ребер в независимых множествах ребер графа G.

Число вершинной независимости (число внутренней устойчивости, неплотность) h(G) - наибольшее число вершин в независимых множествах вершин графа G.

Доминирующее число (число внешней устойчивости) - наименьшее число вершин в доминирующем множестве.

Число вершинного покрытия (опора) - наименьшее число вершин в вершинном покрытии.

Число реберного покрытия - наименьшее число ребер в реберном покрытии графа.

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

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

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

Число тождественной стабильности - минимальная мощность экстремального подмножества тождественной стабильности графа.

Число нетождественной стабильности - максимальная мощность экстремального подмножества нетождественной стабильности графа.

Инварианты графа - характеристика, инвариантная относительно изоморфизмов графа.

Полный инвариант графа - характеристика, задающая граф с точностью до изоморфизма графов.

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

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

Квазиглобальный характеристический инвариант графа - спецификация множества всех n-ок вершин графа по характеристике, инвариантной относительно изоморфизма графов, где 2Јn<p=|X|.

Глобальный характеристический инвариант графа - спецификация множества всех n-ок вершин графа, где n=р=|X| по характеристике, инвариантной относительно изоморфизма графов.

2.3. Отношения. Функции на графах.

Изоморфизм графов. Два графа G=(X, U) и L=(X', U') изоморфны, если между парами множеств их вершин, ребер и дуг существуют взаимно однозначные соответствия, сохраняющие смежность и ориентацию для дуг.

Подразделение графа G - граф, который может быть получен из G путем конечного числа подразделений ребер. - А.Ч.

Гомеоморфизм графов. Два графа G₁ и G₂ гомеоморфны, если у них существуют изоморфные подразделения. - А.Ч.

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

Раскраска [вершинная - А.Ч.] (colouring) - приписывание цветов (натуральных чисел) вершинам графа, такое, что никакие две смежные вершины не получают одинаковые цвета (числа).

n-раскраска - раскраска, в которой используется n цветов.

Раскраска реберная (edge-colouring) - приписывание цветов ребрам графа, такое, что никакие два смежных ребра не получают одинакового цвета.

n-раскраска реберная (n-colouring) - раскраска ребер, использующая точно n цветов.

Полная раскраска - раскраска вершин графа, такая, что для любых двух цветов найдутся две смежные вершины, окрашенные в эти цвета.

Раскраска точная - раскраска с использованием минимального числа красок, т. е. число красок равно хроматическому числу графа G или хроматическому классу графа G.

Раскраска приближенная - раскраска с использованием красок, количество которых больше или равно минимально возможному числу.

Изоморфное вложение (изоморфизм подграфу). Граф G₂ изоморфно вложим в граф G₁, если в графе G₁ существует подграф, изоморфный графу G₂.

Максимальное изоморфное пересечение - максимальный по мощности вершин общий подграф, содержащийся в каждом из рассматриваемых графов.

Генерация графов - процедура построения графа.

Генерация графов с заданными свойствами. Синтезируемый (Р, Q)-граф обладает некоторыми заранее заданными характеристиками.

Систематическая генерация (конструктивное перечисление) - перебор всех графов с заданными характеристиками.

Генерация случайных графов - случайный выбор одного графа из некоторой заданной совокупности.

Объединение графов (помеченных графов) G₁=(X₁, U₁) и G₂=(X₂, U₂) - граф G₁ИG₂, множеством вершин которого является Х=X₁ИX₂, а множеством ребер U=U₁ИU₂.

Пересечение графов (помеченных графов) G₁=(X₁, U₁) и G₂=(X₂, U₂) - граф G₁ЗG₂, множеством вершин которого является Х=X₁ЗX₂, а множеством ребер U=U₁ЗU₂, где U₁ и U₂ - множество неупорядоченных пар вершин.

Соединение графов G₁=(X₁, U₁) и G₂=(X₂, U₂) таких, что X₁ЗX₂=Ж, U₁ЗU₂=Ж - граф G₁+G₂, который состоит из G₁ИG₂ИK(X₁, X₂), где K(X₁, X₂) - полный двудольный граф с множеством вершин X₁ и X₂ в долях.

Сумма графов G₁=(X₁, U₁) и G₂=(X₂, U₂) - граф G₁ґG₂, состоящий из множества вершин Х=X₁ґX₂ и две вершины s=(x₁, x₂) и t=(y₁, y₂) (s, t О X, x₁, y₁ О X₁, x₂, y₂ О X₂) смежны в G₁ґG₂ тогда и только тогда, когда x₁=y₁ и x₂ смежна с y₂ или x₂=y₂ и x₂ смежна с y₁.

Симметрическая разность графов G₁ и G₂ - граф G₁ЕG₂=G₁ИG₂ - G₁ЗG₂.

Разность графов (помеченных графов) - граф G₁-G₂, который получается из G₁ удалением элементов, соответствующих графу G₂.

Композиция графов (лексикографическое произведение графов) G₁=(X₁, U₁) и G₂=(X₂, U₂) - граф G=G₁[G₂], состоящий из множества вершин Х=X₁ґX₂, и две вершины s=(x₁, x₂) и t=(y₁, y₂) смежны в G тогда и только тогда, когда x₁ смежна с y₁ или x₁=y₁ и x₂ смежна с y₂.

Перечисление графов - подсчет числа неизоморфных графов в заданном классе (с заданными характеристиками).

Конструктивное перечисление графов - получение полного списка графов в заданном классе.

Автоморфизм графа (automorphism) - изоморфизм графа G на себя.

Группа [автоморфизмов - А.Ч.] графа (automorphism group) - совокупность всех автоморфизмов графа с композицией (умножением) в качестве групповой операции.

Вершинная группа графа - группа автоморфизмов, действующая на вершинах графа.

Реберная группа графа - группа автоморфизмов, действующая на ребрах графа.

Тождественная группа графа - группа автоморфизмов, состоящая из тождественного автоморфизма.

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

Симметрическая группа графа - группа автоморфизмов, включающая р! автоморфизмов графа G.

Регулярная группа графа - транзитивная по вершинам полурегулярная группа графа.

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

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

Изоморфные группы графов. Группы Aut(G₁) и Aut(G₂) изоморфны, если для любых автоморфизмов x₁, x₂ О Aut(G₁) выполняется равенство h(x₁, x₂) = h(x₁)h(x₂), где h: Aut(G₁)"Aut(G₂).

Комбинаторно-эквивалентные группы графов - группы графов с совпадающими цикловыми индексами.

Порядок группы графа (число симметрии графа) - число автоморфизмов в группе графа.

Орбита вершины группы графа - подмножество множества вершин X, состоящее из всех таких элементов x_i из X, что xx=x₁ для некоторого автоморфизма xОAut(G).

Цикловый индекс группы графа - многочлен от a переменных a₁, a₂, ... , a_a, задаваемый формулой 
где .

Степень группы графа - мощность множества вершин графа G₁, на котором действует группа Aut(G).

Ранг группы графа - число орбит фиксатора вершины в транзитивной группе Aut(G).

Подстепени группы графа - совокупность чисел элементов в каждой орбите фиксатора вершины для транзитивной группы графа.

Подгруппа группы графа - подмножество автоморфизмов графа, замкнутое относительно групповой операции композиции.

Порождающее множество группы графа - совокупность автоморфизмов, на основе которых можно построить все автоморфизмы графа.

Таблица композиций автоморфизмов - квадратная таблица размерности |Aut(G₁)|ґ|Aut(G₂)|, включающая результат умножения каждой пары автоморфизмов графа.

Фиксатор вершины х группы графа - подгруппа группы графа, состоящая из всех автоморфизмов, оставляющих вершину х неподвижной.

Фиксатор подмножества Х*МХ группы графа - подгруппа группы графа, состоящая из пересечения фиксаторов, принадлежащих X*.

Стабилизатор подмножества Х*МХ группы графа - подгруппа графа, состоящая из всех автоморфизмов, оставляющих подмножество X* неподвижным.

Правый смежный класс. Для заданного xОAut(G) правый смежный класс Hx обозначает множество всех элементов вида hx, где h пробегает H.

3. Части графов.

Приводятся основные понятия и определения частей графов (в смысле подмножеств их элементов с сохранением отношений инцидентности) и их характеристики.

3.1. Типы частей графов.

Подграф (часть) графа (subgraph, section graph) G=(X, R) - граф G'=(X', R'), для которого X'НX, R'НR и две несмежные вершины в G не смежны в G'.

Порожденный подграф графа (induced subgraph) G=(X, R) - граф G'=(X', R'), для которого X'НХ и две вершины в G' смежны тогда и только тогда, когда они смежны в G.

Суграф (остовный подграф) графа G=(X, R) - граф G'= (X, R'), который содержит то же множество вершин, что и сам граф G и R'НR.

Остов графа (остовное дерево, покрывающее дерево, каркас) (spanning tree) - суграф графа G, не содержащий циклов и имеющий столько же компонент [связности - А.Ч.], что и G.

Однотипный фрагмент - вершина, ребро, пара вершин, тройка вершин и т.д.

Компонента связности графа (connected component) - максимальный подграф [возможно, не единственный - А.Ч.] графа G, в котором все вершины попарно достижимы.

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

k-компонента (максимальная по включению) - часть графа, в котором любая пара вершин k-соединима.

Полный подграф (complete subgraph) - подграф, в котором каждая пара вершин смежна.

Клика (clique) - полный подграф графа G, такой, что в G не существует вершины, смежной со всеми вершинами данного подграфа [т.е. это максимальный полный подграф - А.Ч.].

Пустой подграф (внутренне-устойчивое множество вершин) - подграф графа G, в котором любая пара вершин несмежна.

Дерево Штейнера (Steiner's tree) - часть графа без циклов, связывающая заданное множество вершин.

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

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

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

Маршрут [путь - А.Ч.] (chain, walk) - чередующаяся последовательность x₁, u₁, x₂, u₂, ... , x_k вершин x_i и ребер u_i, обладающая тем свойством, что любая пара соседних элементов инцидентна.

Цепь (trail, path) - маршрут, в котором все ребра различны.

Простая цепь [простой путь - А.Ч.] (elementary path) - цепь, в которой все вершины различны.

Цикл (cycle) - цепь, у которой начальная и конечная вершины совпадают.

Простой цикл - простая цепь, у которой концевые вершины совпадают.

Ориентированная цепь - цепь орграфа G, в которой ориентация дуг (ребер) совпадает.

Контур (elementary circuit) - ориентированная цепь, у которой начальная и конечная вершины совпадают. - А.Ч.

Эйлерова цепь (Euler path) - цепь, содержащая все ребра графа в точности один раз.

Эйлеров цикл (Euler cycle) - эйлерова цепь, у которой начальная и конечная вершины совпадают.

Гамильтонова цепь (Hamilton path) - простая цепь, которая содержит все вершины графа.

Гамильтонов цикл (Hamilton cycle) - гамильтонова цепь, у которой начальная и конечная вершины совпадают.

Независимые (вершинно-непересекающиеся, вершинно-независимые) маршруты - множество маршрутов, у которых все элементы различны (быть может, кроме конечных вершин).

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

(s, t)-цепь (путь) ((s, t)-path) - цепь, у которой вершины s и t концевые.

Разрез (сечение графа) (cut-set) - множество элементов, удаление которых увеличивает число компонент (односторонних компонент, слабых компонент) связности графа.

Простой разрез - разрез, у которого любое собственное подмножество элементов не является разрезом.

Смешанный разрез - разрез, элементами которого выступают как ребра (дуги), так и вершины.

Реберный разрез - все элементы разреза ребра (дуги).

Вершинный разрез. Все элементы разреза - вершины.

(s, t)-разрез - разрез, при удалении которого вершина t не достижима из s.

Независимое множество элементов (упаковка) [независимое множество вершин или ребер - А.Ч.] (independent vertex or link set) - множество ребер (дуг) или вершин, попарно несмежных.

Покрытие (covering) - множество X' вершин (U' ребер), такое, что каждое ребро (вершина) инцидентна хотя бы одной вершине из X' (ребру U').

Максимальная упаковка - максимально возможное число элементов в соответствующей упаковке.

Минимальное покрытие - минимально возможное число элементов в соответствующем покрытии.

Независимое множество вершин (внутренне устойчивое множество, пустой подграф) (independent vertex set) - множество X' вершин, в котором никакие две вершины несмежны.

Максимальное независимое множество вершин (maximal independent vertex set) - такое независимое множество вершин, что при добавлении в него любой другой вершины графа это множество перестает быть независимым.
Примечание: "максимальность" в смысле данного определения означает не максимальную мощность, а "нерасширяемость" множества; в общем случае граф может иметь несколько максимальных независимых множества вершин разной мощности. - А.Ч.

Паросочетание (независимое множество ребер) (matching, independent link set) - множество U' ребер, в котором никакие два ребра несмежны.

Совершенное паросочетание (perfect matching) - такое паросочетание, что любая вершина графа инцидентна некоторому ребру этого паросочетания.

Доминирующее множество вершин (внешне устойчивое множество) - множество X' вершин, таких, что каждая вершина, не принадлежащая X', смежна с вершиной из X'.

Вершинное покрытие (опора) - множество X' вершин, таких, что всякое ребро инцидентно вершине из X'.

Реберное покрытие (покрывающий суграф) [доминирующее множество ребер - А.Ч.] (edge covering) - множество U' ребер, таких, что всякая вершина инцидентна ребру из U'.

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

Экстремальное подмножество тождественной стабильности - подмножество вершин графа, относительно которого фиксатор группы тождественный, но удаление любой вершины из подмножества приводит к нетождественному фиксатору.

3.2. Числовые характеристики частей.

Минимальный разрез - разрез с наименьшим числом элементов.

Минимальная цепь - (s, t)-цепь с минимальным числом ребер.

Максимальный разрез - разрез с наибольшим числом элементов среди всех простых разрезов графа.

Максимальная цепь - простая (s, t)-цепь с максимально возможным числом ребер.

Максимальная клика - клика с максимально возможным числом вершин среди клик графа.

Минимальное дерево Штейнера - дерево Штейнера с минимально возможным суммарным весом ребер.

Максимальное паросочетание - паросочетание с максимально возможным числом ребер в паросочетании данного графа (числом реберной независимости).

Фундаментальный цикл (контур) - цикл, определяемый некоторым остовом и хордой графа (орграфа).

Минимальный цикл (обхват) - цикл с минимально возможным числом ребер среди всех циклов графа.

Расстояние между вершинами s и t - равно длине минимальной (s, t)-цепи.

i-й ярус вершин - подмножество вершин, находящихся на расстоянии i от заданной вершины.

Одноцветный класс - множество всех вершин одного цвета.

Взвешенный граф - граф, вершинам и/или (обычно) ребрам которого поставлены в соответствие целые или вещественные числа (веса). - А.Ч.

Вес (длина) - денотат [значение - А.Ч.] числа, поставленного в соответствие взвешенному элементу.

Величина (разреза, цепи, цикла и т. п.) - суммарный вес элементов, входящих в данное подмножество.

Наибольшее паросочетание - паросочетание с наибольшей величиной.

Критический путь - (s, t)-путь в ациклическом орграфе наибольшей величины.

Кратчайшая цепь - (s, t)-цепь с наименьшей величиной.

Расстояние между вершинами s и t - величина кратчайшей (s, t)-цепи. Если s и t несоединимы, то расстояние между этими вершинами равно Ґ.

Вес цикла - величина цикла.

Отрицательный цикл - цикл, который имеет отрицательную величину.

Длина маршрута (цепи, пути) - величина маршрута.

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

Наибольший разрез (максимальный) - простой разрез с наиболее возможной величиной.

Наименьший разрез (минимальный) - простой разрез с минимально возможной величиной.

Минимальное (наименьшее, кратчайшее) остовное дерево - остовное дерево с минимально возможной величиной.
 
Приложение

Греческий алфавит