Граф — математическая абстракция реальной системы любой природы, объекты которой обладают парными связями. Граф как математический объект есть совокупность двух множеств — множества самих объектов, называемого множеством вершин, и множества их парных связей, называемого множеством рёбер. Элемент множества рёбер есть пара элементов множества вершин.
Ориентированный граф — (мульти) граф, рёбрам которого присвоено направление. Направленные рёбра именуются также дугами, а в некоторых источниках и просто рёбрами. Граф, ни одному ребру которого не присвоено направление, называется неориентированным графом или неорграфом.
Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре.
Дерево — связный ациклический граф. Связность означает наличие маршрута между любой парой вершин, ацикличность — отсутствие циклов. Отсюда, в частности, следует, что число рёбер в дереве на единицу меньше числа вершин, а между любыми парами вершин имеется один и только один путь.
Связный граф — граф, содержащий ровно одну компоненту связности. Это означает, что между любой парой вершин этого графа существует как минимум один путь.
Эйлеров путь в графе — это путь, проходящий по всем рёбрам графа и притом только по одному разу.
Гамильтонов граф — граф, содержащий гамильтонов цикл. При этом гамильтоновым циклом является такой цикл, который проходит через каждую вершину данного графа ровно по одному разу; то есть простой цикл, в который входят все вершины графа.
В теории графов два типа объектов обычно называются циклами.
Турнир — это ориентированный граф, полученный из неориентированного полного графа путём назначения направления каждому ребру. Таким образом, турнир — это орграф, в котором каждая пара вершин соединена одной направленной дугой.
Теорема Роббинса, названная по имени американского математика Герберта Роббинса, утверждает, что графы, имеющие сильные ориентации, — это в точности рёберно 2-связные графы. То есть тогда и только тогда можно выбрать направление каждого ребра неориентированного графа G, превратив граф в ориентированный граф, в котором существует (ориентированный) путь из любой вершины в любую другу вершину, когда граф G связен и не имеет мостов.
Циклический ранг ориентированного графа — мера связности орграфа, предложенная Эгганом и Бучи. Это понятие интуитивно отражает, насколько близок орграф к направленному ациклическому графу, когда циклический ранг НАГ равен нулю, в то время как ориентированный орграф порядка n с петлями в каждой вершине имеет циклический ранг n. Циклический ранг ориентированного графа тесно связан с глубиной дерева неориентированного графа и высотой итерации регулярных языков. Циклический ранг нашёл применение также в вычислениях с разреженными матрицами и логике.
Ориентация неориентированного графа — это назначение направлений каждому ребру, что превращает исходный граф в ориентированный граф.
Модульное разложение — это разложение графа на подмножества вершин, называемых модулями. Модуль является обобщением компоненты связности графа. В отличие от компонент связности, однако, один модуль может быть собственным подмножеством другого. Модули, поэтому, ведут к рекурсивной (иерархической) декомпозиции графа, а не просто к разбиениям.
Кососимметрический граф — ориентированный граф, изоморфный своему собственному транспонированному графу. Этот граф образуется путём обращения всех дуг с изоморфизмом и является инволюцией без неподвижных точек. Кососимметрические графы идентичны двойным покрытиям двунаправленных графов.
Задача китайского почтальона, маршрут почтальона или задача инспекции дорог заключается в поиске кратчайшего замкнутого пути или цикла, который проходит через каждое ребро (связного) взвешенного неориентированного графа. Если граф имеет эйлеров цикл, тогда этот цикл служит оптимальным решением. В противном случае задачей оптимизации является поиск наименьшего числа рёбер графа с повторными проходами, так что получающийся мультиграф имеет эйлеров цикл. Эта задача может быть решена за полиномиальное время.
Минимально критичное остовное дерево во взвешенном неориентированном графе — это остовное дерево, в котором наиболее тяжёлое ребро весит как можно меньше. Критичное ребро — это самое тяжёлое ребро в стягивающем дереве. Стягивающее дерево является минимальным критичным остовным деревом, если граф не содержит стягивающего дерева с критичным ребром меньшего веса. Для ориентированного графа аналогичная задача известна как минимально критичное стягивающее ориентированное дерево.
Дополнение графа до сильно связного ― вычислительная задача теории графов, входными данными для которой является ориентированный граф. Цель задачи ― добавить минимальное число дуг так, чтобы исходный граф стал сильно связным.
Примене́ние тео́рии гра́фов — использование теории графов как математического орудия в различных дисциплинах.
