Граф — математическая абстракция реальной системы любой природы, объекты которой обладают парными связями. Граф как математический объект есть совокупность двух множеств — множества самих объектов, называемого множеством вершин, и множества их парных связей, называемого множеством рёбер. Элемент множества рёбер есть пара элементов множества вершин.
Тео́рия гра́фов — раздел дискретной математики, изучающий графы, одна из ветвей топологии. В самом общем смысле граф — это множество точек, которые соединяются множеством линий. Теория графов включена в учебные программы для начинающих математиков, поскольку:
- как и геометрия, обладает наглядностью;
- как и теория чисел, проста в объяснении и имеет сложные нерешённые задачи;
- не имеет громоздкого математического аппарата ;
- имеет выраженный прикладной характер.
Ориентированный граф — (мульти) граф, рёбрам которого присвоено направление. Направленные рёбра именуются также дугами, а в некоторых источниках и просто рёбрами. Граф, ни одному ребру которого не присвоено направление, называется неориентированным графом или неорграфом.
Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре.
Дерево — связный ациклический граф. Связность означает наличие маршрута между любой парой вершин, ацикличность — отсутствие циклов. Отсюда, в частности, следует, что число рёбер в дереве на единицу меньше числа вершин, а между любыми парами вершин имеется один и только один путь.
В теории графов мультиграфом называется граф, в котором разрешается присутствие кратных рёбер, то есть рёбер, имеющих те же самые конечные вершины. Таким образом, две вершины могут быть соединены более чем одним ребром.
Связный граф — граф, содержащий ровно одну компоненту связности. Это означает, что между любой парой вершин этого графа существует как минимум один путь.
Эйлеров путь в графе — это путь, проходящий по всем рёбрам графа и притом только по одному разу.
Двудо́льный граф или бигра́ф в теории графов — это граф, вершины которого можно разбить на две части так, что каждое ребро соединяет вершину из одной части с вершиной другой части. То есть, между вершинами одной и той же части рёбра отсутствуют.
В теории графов два типа объектов обычно называются циклами.
Графовая вероятностная модель — это вероятностная модель, в которой в виде графа представлены зависимости между случайными величинами. Вершины графа соответствуют случайным переменным, а рёбра — непосредственным вероятностным взаимосвязям между случайными величинами. Графические модели широко используются в теории вероятностей, статистике, а также в машинном обучении.
В теории графов рёберным графом L(G) неориентированного графа G называется граф L(G), представляющий соседство рёбер графа G.
Турнир — это ориентированный граф, полученный из неориентированного полного графа путём назначения направления каждому ребру. Таким образом, турнир — это орграф, в котором каждая пара вершин соединена одной направленной дугой.
Зада́ча о кратча́йшем пути́ — задача поиска самого короткого пути (цепи) между двумя точками (вершинами) на графе, в которой минимизируется сумма весов рёбер, составляющих путь.
Веб-граф описывает направленные ссылки между страницами Всемирной паутины. В общем случае граф состоит из нескольких вершин, некоторые пары из которых соединены между собой ребрами. В ориентированном графе, ребра имеют направление. Веб-граф является ориентированным графом, вершины которого соответствуют веб-страницам сети, а рёбра — связям между ними. При этом ребро направленное со страницы X в направлении страницы Y строится в случае, если на странице X есть гиперссылка на страницу Y.
В теории графов псевдолес — это неориентированный граф, в котором любая связная компонента имеет максимум один цикл. То есть это система вершин и рёбер, соединяющих пары вершин, такая, что никакие два цикла не имеют общих вершин и не могут быть связаны путём. Псевдодерево — это связный псевдолес.
Ориентированная раскраска графа — это специальный вид раскраски графов. А именно, это назначение цветов вершинам ориентированного графа, которое
- правильное — никакие две смежные вершины не получают один и тот же цвет,
- сохраняется ориентация — если (x, y) и (u, v) являются дугами в графе, то недопустимо, чтобы цвета вершин x и v, а также цвета вершин y и u совпадали.
Ориентация неориентированного графа — это назначение направлений каждому ребру, что превращает исходный граф в ориентированный граф.
Гипотеза Сеймура о второй окрестности — это нерешенная математическая проблема об ориентированных графах, сформулированная Полом Сеймуром. Интуитивно понятно, что в социальной сети, описываемой таким графом, у кого-то будет хотя бы столько же друзей друзей, сколько и друзей. Эта проблема также известна как гипотеза Сеймура о расстоянии два.
