КРАТКИЙ ТЕРМИНОЛОГИЧЕСКИЙ СЛОВАРЬ

Ациклический граф. Ориентированный граф без контуров.

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

Ветвь. Ребро графа которое содержится в дереве являющемся подграфом термин ветвь используется по отношению к определенному дереву

Вершина. См. граф и ориентированный граф.

Граничные точки. Вершины, которым инцидентны ребра или дуги.

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

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

Граф. Математическая система, состоящая из двух множеств и отображения множества в (множество неупорядоченных пар элементов V). Элементы называются соответственно вершинами и ребрами графа, а называется отображением инцидентности. Если то вершины называются граничными точками .

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

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

Граф без сочленений. Связный граф без точек сочленения.

Дуга. См. ориентированный граф.

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

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

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

Дерево, растущее из корня (прадерево). Ориентированный граф, который является деревом и имеет вершину такую, что для любой другой вершины дерева единственная цепь соединяет и является фактически путем, ориентированным от и к В этом случае говорят, что дерево растет из корня

Дерево. Связный граф без циклов.

Инцидентное отображение. См. граф.

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

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

Источник. Вершина сети, в которой выходной поток больше входного.

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

Контур. Замкнутый ориентированный маршрут без повторяющихся вершин.

Контурный граф. Ориентированный граф, содержащий, по крайней мере, один контур.

Конечный граф. Граф, имеющий конечное число вершин и ребер (или дуг в случае ориентированного графа).

Конечная вершина. См. ориентированный граф.

Лес. Граф без циклов, каждая компонента которого является деревом.

Матрица смежности. То же, что и матрица смежности вершин.

Матрица циклов. Матрица, чьи строки и столбцы соответствуют простым циклам и ребрам графа, а каждый из ее элементов равен 1 или 0 в зависимости от того, содержится или нет в соответствующем цикле соответствующее ребро.

Матрица разрезов. Матрица, аналогичная матрице циклов, в которой простые циклы заменены простыми разрезами.

Маршрут. Конечная последовательность (ие обязательно различных) ребер таких, что одна из граничных точек первого ребра является также граничной точкой второго, оставшаяся граничная точка второго ребра является также граннчной точкой третьего и т. д. Маршрут является замкнутым, если свободная граничная точка первого ребра совпадает со «свободной» граничной точкой последнего. Маршрут называется незамкнутым в противном случае.

Матрица инциденций. Матрица, строка и столбцы которой соответствуют вершинам и ребрам графа. Каждый элемент матрицы равен 1 или в зависимости от того, инцидентны или нет соответствующие ему вершина и ребро.

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

Неупорядоченная цепь. Множество ребер, которые, будучи соответственно упорядоченными, образуют Цепь. В геометрическом графе это множество ребер, которые образуют незамкнутую кривую.

Неупорядоченный цикл. Множество ребер, которые, будучи соответственно упорядоченными, образуют цикл. В геометрическом графе это множество ребер, которые образуют замкнутую кривую.

Неупорядоченный контур. Множество дуг, которые будучи соответственно упорядоченными, образуют контур. В геометрическом графе это замкнутая кривая, образованная соответственно ориентированными дугами.

Независимое множество вершин (внутреннее устойчивое множество). Множество вершин, в котором нет двух смежных вершин.

Неупорядоченный путь. Множество дуг, которые будучи соответственно упорядоченными, образуют путь.

Неориентированный граф. То же самое, что граф.

Начальная вершина. См. ориентированный граф.

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

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

Ориентированный граф. Математическая система, состоящая из двух множеств и отображения множества А на VX. Элементы называются соответственно вершинами и дугами ориентированного графа, а называется отображением ориентированной инцидентности. Если то называется начальной вершиной дуги а, в конечной вершиной.

Отрицательная степень вершины. Число дуг, с которыми вершина отрицательно инцидентна.

Отрицательная инцидентность. Отношение между дугой и ее конечной вершиной (дуга входит в вершину).

Однородный граф. Граф, все вершины которого имеют одну и ту же степень.

Обыкновенный граф. Неориентированный граф, который не содержит параллельных ребер и петель; ориентированный граф, который не содержит строго параллельных дуг и петель.

Полный граф. Граф, в котором каждые две различные вершины смежны.

Поток. Целые числа, назначенные дугам сети, которые интерпретируются как скорости потока вещества но дугам.

Петля. Ребро (или дуга), инцидентное только одной вершине.

Паросочетание. Множество ребер графа, в котором нет двух смежных ребер.

Параллельные ребра или дуги. Ребра или дуги, имеющие общие граничные точки.

Путь. Незамкнутый ориентированный маршрут без повторяющихся дуг.

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

Плоский граф. Граф, изоморфным геометрическому графу на плоскости.

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

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

Положительная степень вершины. Число дуг, которые положительно инцидентны вершине.

Положительная инциденция. Связь между дугой и ее начальной вершиной (дуга выходит из вершины).

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

Простой разрез. Разделяющее множество, которое не содержит собственного подмножества разделяющего граф.

Простая цепь. Цепь, не содержащая повторяющихся вершин.

Простой цикл. Цикл, не содержащий повторяющихся вершин.

Простой контур. Контур, не содержащий повторяющихся вершнн.

Простой путь. Путь, не содержащий повторяющихся вершнн.

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

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

Ребро. См. граф.

Рефлексивный граф. Ориентированный граф, каждой вершине которого инцидентна петля.

Смежные ребра или дуги. Два ребра или дуги, имеющие, по крайней мере, одну общую граничную точку.

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

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

Степень вершины. Число ребер (или дуг), ннцидентиых вершине. Петли считаются дважды.

Сеть. Связный ориентированный граф без петель. Этот термин используется в теории потоков.

Сток. Вершина сети, в которой входной поток больше выходного.

Строго параллельные дуги. Дуги, имеющие одинаковые начальную и конечную вершины.

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

Симметрический граф. Ориентированный граф, дуги которого могут быть сгруппированы в пары параллельных, но противоположно направленных дуг.

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

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

Транзитивный граф. Ориентированный граф, который содержит дугу из всякий раз, когда существует дуга из дуга

Уникурсальный граф. Граф (ориентированный граф), совокупность ребер (дуг) которого образует цикл (контур) или цепь (путь).

Хорда. Ребро графа которое не содержится в дереве являющемся подграфом термин хорда употребляется по отношению к определенному дереву

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

Цепь. Незамкнутый маршрут, не содержащий повторяющихся ребер.

Цикл. Замкнутый маршрут, не содержащий повторяющихся ребер.

Эйлеров граф. Граф, не содержащий вершин нечетной степени.