Введение

множества вершин, соединенных ребрами. Вершины, соединенные попарно ребрами.

В дискретной математике, и в частности в теории графов, граф – это структура, состоящая из множества объектов, в котором некоторые пары объектов связаны между собой в определенном смысле. Объекты представляются абстракциями, называемыми вершинами (также называемыми узлами или точками), и каждая из связанных пар вершин называется ребром (также называемым связью или линией). Как правило, граф изображается в виде набора точек или кругов, представляющих вершины, соединенных линиями или кривыми, представляющими ребра. Ребра могут быть ориентированными или неориентированными. Например, если вершины представляют людей на вечеринке, и между двумя людьми есть ребро, если они пожимают друг другу руки, то этот граф неориентированный, поскольку человек А может пожать руку человеку В только в том случае, если В также пожмет руку А. Напротив, если ребро от человека А к человеку В означает, что А должен деньги В, то этот граф ориентированный, поскольку долг не обязательно является взаимным. Графы – основной предмет изучения теории графов. Слово "граф" впервые в этом значении использовал Дж. Дж. Сильвестр в 1878 году в связи с прямой зависимостью между математикой и химической структурой (которую он назвал химико-графическим изображением).

Определения

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

График

Граф (иногда называемый ненаправленным графом, чтобы отличить его от ориентированного графа, или простым графом, чтобы отличить его от мультиграфа) — это пара G = (V, E), где V — множество, элементы которого называются вершинами (в единственном числе — вершина), а E — множество неупорядоченных пар вершин, элементы которых называются ребрами (иногда связями или линиями). Вершины u и v ребра {u, v} называются конечными точками ребра. Говорят, что ребро соединяет u и v и инцидентно им. Вершина может не принадлежать ни одному ребру, в этом случае она не соединена ни с какой другой вершиной и называется изолированной. Если ребро существует, вершины u и v называются смежными. Мультиграф — это обобщение, которое позволяет нескольким ребрам иметь одну и ту же пару конечных точек. В некоторых текстах мультиграфы просто называются графами. Иногда графам разрешено содержать петли — это ребра, соединяющие вершину саму с собой. Чтобы разрешить петли, парам вершин в E должно быть разрешено содержать один и тот же узел дважды. Такие обобщенные графы называются графами с петлями или просто графами, если из контекста ясно, что петли разрешены. Обычно множество вершин V считается конечным (что подразумевает, что множество ребер E также конечно). Иногда рассматриваются бесконечные графы, но обычно они рассматриваются как особый вид бинарного отношения, поскольку большинство результатов для конечных графов либо не распространяются на бесконечный случай, либо требуют существенно иного доказательства. Пустой граф — это граф, имеющий пустое множество вершин (и, следовательно, пустое множество ребер). Порядок графа — это количество его вершин, обычно обозначаемое n. Размер графа — это количество его ребер, обычно обозначаемое m. Однако в некоторых контекстах, например, при выражении вычислительной сложности алгоритмов, термин «размер» используется для обозначения количества (в противном случае непустой граф может иметь размер 0). Степень или валентность вершины — это количество ребер, инцидентных ей; для графов с петлями петля учитывается дважды. В графе порядка n максимальная степень каждой вершины равна n − 1 (или n + 1, если разрешены петли, поскольку петля вносит вклад 2 в степень), а максимальное количество ребер равно n(n − 1)/2 (или n(n + 1)/2, если разрешены петли). Ребра графа определяют симметричное отношение на вершинах, называемое отношением смежности. В частности, две вершины x и y смежны, если {x, y} является ребром. Граф полностью определяется своей матрицей смежности A, которая является квадратной матрицей размера n × n, указывающей количество соединений от вершины i к вершине j. Для простого графа A[i][j] равно либо 0, что указывает на отсутствие соединения, либо 1, что указывает на соединение; более того, A[i][i] = 0, поскольку ребро в простом графе не может начинаться и заканчиваться в одной и той же вершине. Графы с петлями характеризуются тем, что некоторые или все элементы A[i][i] равны положительному целому числу, а мультиграфы (с несколькими ребрами между вершинами) характеризуются тем, что некоторые или все элементы A[i][j] равны положительному целому числу. Неориентированные графы имеют симметричную матрицу смежности (то есть A[i][j] = A[j][i]).

Смешанный график

Смешанный граф — это граф, в котором некоторые рёбра могут быть ориентированными, а некоторые — неориентированными. Он представляется упорядоенной тройкой G = (V, E, A) для смешанного простого графа и для смешанного мультиграфа, где V — множество вершин, E — множество неориентированных рёбер, A — множество ориентированных рёбер, и определяется, как описано выше. Ориентированные и неориентированные графы являются частными случаями.

Взвешенный график

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

Ориентированный график

Одно из определений ориентированного графа состоит в том, что это ориентированный граф, в котором может существовать не более одного из ребер (x, y) и (y, x). Иными словами, это ориентированный граф, который можно получить ориентацией ненаправленного (простого) графа. Некоторые авторы используют термин "ориентированный граф" как синоним "ориентированного графа". Некоторые авторы под "ориентированным графом" понимают любую ориентацию заданного ненаправленного графа или мультиграфа.

Регулярный график

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

Полный график

Полный граф — это граф, в котором каждая пара вершин соединена ребром. Полный граф содержит все возможные рёбра.

Оконченный график

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

Соединенный график

В ненаправленном графе неупорядоченная пара вершин называется связанной, если существует путь из x в y. В противном случае неупорядоченная пара называется несвязной. Связный граф — это ненаправленный граф, в котором каждая неупорядоченная пара вершин связана. В противном случае граф называется несвязным. В ориентированном графе упорядоченная пара вершин (x, y) называется сильно связной, если существует ориентированный путь из x в y. В противном случае упорядоченная пара называется слабо связной, если после замены всех ориентированных ребер на неориентированные, существует неориентированный путь из x в y. В противном случае упорядоченная пара называется несвязной. Сильно связный граф — это ориентированный граф, в котором каждая упорядоченная пара вершин сильно связна. В противном случае граф называется слабо связным, если каждая упорядоченная пара вершин слабо связна. В противном случае граф называется несвязным. k-вершинно связный граф или k-реберно связный граф — это граф, в котором не существует множества из k-1 вершин (соответственно, ребер), удаление которого делает граф несвязным. k-вершинно связный граф часто называют просто k-связным графом.

График двустороннего

Двудольный граф — это простой граф, в котором множество вершин можно разбить на два непересекающихся множества, W и X, так, что никакие две вершины из W не соединены ребром, и никакие две вершины из X не соединены ребром. Альтернативно, это граф с хроматическим числом 2. В полном двудольном графе множество вершин является объединением двух непересекающихся множеств, W и X, так, что каждая вершина из W смежна со каждой вершиной из X, но внутри W и X нет рёбер.

График пути

Граф пути или линейный граф порядка n ≥ 2 — это граф, в котором вершины можно перечислить в порядке v1, v2, ..., vn таким образом, что рёбрами являются (vi, vi+1), где i = 1, 2, ..., n − 1. Графы пути можно охарактеризовать как связные графы, в которых степень всех вершин, кроме двух, равна 2, а степень двух оставшихся вершин равна 1. Если граф пути встречается как подграф другого графа, то он является путём в этом графе.

Плановый график

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

Цикл график

Циклический граф или круговой граф порядка n ≥ 3 — это граф, в котором вершины можно перечислить в порядке v1, v2, ..., vn таким образом, что ребрами являются (vi, vi+1), где i = 1, 2, ..., n − 1, плюс ребро (vn, v1). Циклические графы можно охарактеризовать как связные графы, в которых степень каждой вершины равна 2. Если циклический граф возникает как подграф другого графа, он является циклом в этом графе.

Дерево

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

Полидрево

Полидерево (или направленное дерево, или ориентированное дерево, или односвязная сеть) — направленный ациклический граф (DAG), базовый неориентированный граф которого является деревом. Полилес (или направленный лес, или ориентированный лес) — направленный ациклический граф, базовый неориентированный граф которого является лесом.

Свойства графиков

Два ребра графа называются смежными, если у них общая вершина. Два ребра ориентированного графа называются последовательными, если конец первого является началом второго. Аналогично, две вершины называются смежными, если у них есть общее ребро (последовательными, если первая является началом, а вторая – концом ребра), в этом случае общее ребро соединяет эти две вершины. Ребро и вершина, лежащая на этом ребре, называются инцидентными. Граф, содержащий только одну вершину и не содержащий ребер, называется тривиальным графом. Граф, содержащий только вершины и не содержащий ребер, известен как граф без ребер. Граф, не содержащий вершин и не содержащий ребер, иногда называют нулевым графом или пустым графом, но терминология не является последовательной, и не все математики допускают существование такого объекта. Обычно вершины графа, по своей природе как элементы множества, различимы. Такой граф можно назвать графом с маркированными вершинами. Однако для многих задач лучше рассматривать вершины как неразличимые. (Разумеется, вершины могут быть различимы по свойствам самого графа, например, по количеству инцидентных ребер.) Те же замечания применимы и к ребрам, поэтому графы с маркированными ребрами называются графами с маркировкой ребер. Графы с метками, прикрепленными к ребрам или вершинам, в более общем смысле обозначаются как маркированные графы. Следовательно, графы, в которых вершины неразличимы и ребра неразличимы, называются немаркированными графами. (В литературе термин «маркированный» может применяться к другим видам маркировки, помимо той, которая служит только для различения различных вершин или ребер.) Категория всех графов – это предельная категория Set ↓ D, где D: Set → Set – это функтор, отображающий множество s в s × s.

Обобщения

В гиперграфе ребро может соединять любое положительное число вершин. Неориентированный граф можно рассматривать как симплициальный комплекс, состоящий из 1-симплексов (рёбер) и 0-симплексов (вершин). Таким образом, комплексы являются обобщениями графов, поскольку они допускают симплексы более высокой размерности. Каждый граф порождает матроид. В теории моделей граф — это просто структура. Однако в этом случае нет ограничений на число рёбер: оно может быть любым кардинальным числом, см. непрерывный граф. В вычислительной биологии анализ степенных графов вводит степенные графы как альтернативное представление неориентированных графов. В географических информационных системах геометрические сети тесно моделируются на основе графов и заимствуют многие концепции из теории графов для выполнения пространственного анализа дорожных сетей или сетей инженерных коммуникаций.