инцидентность
Отношение типа "лежит на..." или "проходит через..." между двумя объектами
граф
Совокупность множества вершин и множества ребер, причем каждое ребро связано отношением инцидентности с двумя вершинами; другими словами, каждое ребро является связью двух вершин
ориентированный граф
направленный граф
орграф
Граф, в котором ребра имеют направление
дуга
Ребро орграфа
смешанный граф
Граф, содержащий как ориентированные, так и неориентированные рёбра
суграф
частичный граф
Граф, полученный из исходного графа исключением некоторых ребер
степень вершины
Число рёбер, инцидентных вершине
полустепень
Число дуг, входящих в вершину, есть полустепень захода, а число исходящих дуг — полустепень исхода вершины
часть графа
Граф, полученный из исходного графа исключением некоторых вершин и некоторых ребер
подграф
Граф, полученный из исходного графа исключением некоторых вершин и всех инцидентных им ребер
кусок графа
Граф Q(X,Y), являющийся частью исходного графа G(Z,U) такой, что X — подмножество Z, а в Y входят все ребра из U, инцидентные X
дополнение подграфа
Граф, состоящий из вершин и ребер, которыми исходный граф отличается от подграфа
клика
Подмножество вершин в неориентированном графе такое, что каждые две из них соединены ребром графа. Иными словами, это полный подграф первоначального графа.
надграф
Исходный граф, из которого получен подграф
сверхграф
Исходный граф, из которого получен суграф
двудольный граф
граф Кёнига
Граф, в котором множество вершин состоит из двух подмножеств и ребер, соединяющих вершины разных подмножеств
матрица инцидентности
Матрица, в которой число столбцов равно числу вершин графа, число строк — числу ребер графа, элемент матрицы на пересечении p-го столбца и q-й строки равен единице, если p-я вершина и q-е ребро находятся в отношении инцидентности, иначе элемент равен нулю
матрица смежности
Квадратная матрица n×n, где n — число вершин графа, у которой элемент на пересечении p-го столбца и q-й строки равен числу ребер, соединяющих вершины p и q
маршрут
Последовательность ребер графа, в которой любая пара соседних ребер имеет общую инцидентную им вершину
цепь
Маршрут, в котором все ребра различны
простая цепь
Цепь, в которой все вершины различны
путь
Последовательность дугориентированном графе), такая, что конец одной дуги является началом другой дуги
простой путь
Путь, вершины которого, за исключением быть может, первой и последней, различны. Иногда путь называют простым , если в нём не повторяются ребра; тогда элементарный путь — простой путь с неповторяющимися вершинами
цикл
Замкнутая цепь
простой цикл
Замкнутая простая цепь
контур
эйлеров цикл
Цикл, в котором содержатся все ребра графа
гамильтонов цикл
Простой цикл, который проходит через все вершины графа
связность
Свойство, которым обладают вершины графа, для которых существует соединяющая их простая цепь
связный граф
Граф, в котором, перемещаясь от вершины к вершине, можно попасть в каждую вершину
дерево графа
Неориентированный связный граф без циклов
покрывающее дерево
Дерево графа, состоящее из b-1 ребер, где b — число вершин в графе
мультиграф
Граф без -петель, имеющий кратные ребра
псевдограф
Мультиграф, допускающий наличие петель
простой граф
Граф, не имеющий петель и кратных рёбер
гиперграф
Совокупность множества вершин и множества ребер, ребра выражают n-арные отношения между вершинами, в отличие от графа n может быть более двух. Другими словами, ребро может быть инцидентным более чем двум вершинам
ультраграф
уграф
Обобщение понятий гиперграфа и орграфа — граф, задаваемый множествами вершин X и ребер U и отображениями X в U и U в X. Уграф может быть представлен в виде двудольного графа с подмножествами вершин X и U и дугами, связывающими элементы этих подмножеств
цикломатическое число
Наименьшее число ребер, которое необходимо удалить из графа, чтобы получить дерево (для связного графа) или лес (для несвязного графа)
число внутренней устойчивости
Величина, равная наибольшему числу несмежных между собой вершин графа
плоский граф
Граф, рёбра которого не пересекаются
планарный граф
Граф, изоморфный плоскому графу. Планарный граф, который может быть изображен на плоскости без пересечения рёбер
число планарности
Минимальное число ребер, которое необходимо удалить из графа для получения его плоского изображения
грань
Простой цикл в планарном графе, который при укладке графа на плоскость будет ограничивать часть плоскости, не содержащую других элементов графа
толщина графа
Минимальное число плоских суграфов, на которые разбивается исходный граф
изоморфные графы
Графы, имеющие одинаковое число вершин, причем каждой паре вершин, соединенных ребром (дугой) в одном графе, соответствует такая же пара вершин, соединенных ребром (дугой) в другом графе
грань графа
В планарном графе простой цикл, который при укладке графа на плоскость будет ограничивать часть плоскости, не содержащую других элементов графа
раскраска графа
Разбиение вершин графа на множества ( называемые цветами ), при котором нет двух смежных вершин принадлежащих одному и тому же множеству
хроматическое число
Наименьшее число непересекающихся подмножеств вершин графа, на которые можно разделить вершины таким образом, чтобы ребра графа соединяли только вершины разных подмножеств. Другими словами, хроматическое число есть минимальное число цветов, требуемое для раскраски графа, при которой любые вершины, соединенные ребром, раскрашены в разные цвета