Граф (дискретная математика) - Graph (discrete mathematics)

Граф с шестью вершинами и семью ребрами.

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

Края могут быть направленными или ненаправленными. Например, если вершины представляют собой людей на вечеринке, и есть ребро между двумя людьми , если они пожать друг другу руки, то этот граф неориентированный , потому что любой человек может пожать друг другу руки с человеком B только если B также рукопожатием с A . Напротив, если какое-либо ребро от человека A к человеку B соответствует тому, что A должен деньги B , то этот граф является направленным, потому что задолженность не обязательно является взаимной. Первый тип графа называется неориентированным графом, а второй тип графа называется ориентированным графом .

Графы - это основной предмет, изучаемый теорией графов . Слово «граф» было впервые использовано в этом смысле Дж. Дж. Сильвестром в 1878 году в прямой связи между математикой и химической структурой (то, что он назвал химико-графическим изображением).

Определения

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

График

Граф с тремя вершинами и тремя ребрами.

График (иногда называемый неориентированный граф отличить от ориентированного графа , или простого графа для различения от мультиграфе ) является пара G = ( V , E ) , где V представляет собой набор, элементы которого называются вершинами ( в единственном числе: вершина), а E - набор парных вершин, элементы которых называются ребрами (иногда звеньями или линиями ).

Вершины x и y ребра { x , y } называются концами ребра. Ребро называется присоединиться х и у и быть падающей на х и у . Вершина не может принадлежать ни одному ребру, в этом случае она не соединяется ни с какой другой вершиной.

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

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

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

Пустой граф представляет собой график , который имеет пустое множество вершин (и , таким образом , пустое множество ребер). Порядок графа является числом вершин | V | . Размер графа является число ребер | E | . Однако в некоторых контекстах, например, для выражения вычислительной сложности алгоритмов, размер | V | + | E | (в противном случае непустой граф мог иметь размер 0). Степень или валентность вершины есть число ребер, инцидентных к нему; для графов с циклами цикл считается дважды.

В графе порядка n максимальная степень каждой вершины равна n - 1 (или n, если петли разрешены), а максимальное количество ребер равно n ( n - 1) / 2 (или n ( n + 1) / 2, если петли разрешены).

Ребра графа определяют симметричное отношение на вершинах, называемое отношением смежности . В частности, две вершины х и у являются смежными , если { х , у } является ребром. Граф может быть полностью задан своей матрицей смежности A , которая является квадратной матрицей, где A ij определяет количество соединений от вершины i к вершине j . Для простого графа, тем временем, обозначает разъединение или соединение соответственно (то есть ребро не может начинаться и заканчиваться в одной и той же вершине). Графы с петлями будут характеризоваться тем, что некоторые или все равны положительному целому числу, а мультиграфы (с несколькими ребрами между вершинами) будут характеризоваться тем, что некоторые или все будут равны положительному целому числу. Ненаправленные графы будут иметь симметричную матрицу смежности ( ).

Направленный граф

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

Ориентированный граф или орграф представляет собой график , в котором ребра имеют ориентацию.

В одном ограниченном, но очень общем смысле этого термина ориентированный граф - это пара, состоящая из:

  • , А набор из вершин (также называемые узлами или точки );
  • , А набор из ребер (также называемые ориентированных ребер , направленные ссылки , направленные линии , стрелка или дуги ) , которые упорядоченные пары вершин (то есть, ребро связанно с двумя различными вершинами).

Во избежание двусмысленности этот тип объекта можно назвать именно ориентированным простым графом .

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

В более общем смысле этого слова, допускающего наличие нескольких ребер, ориентированный граф - это упорядоченная тройка, содержащая:

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

Во избежание двусмысленности этот тип объекта можно назвать именно ориентированным мультиграфом .

Цикл является ребром , который соединяет вершину саму с собой. Направленные графы, как определено в двух определениях выше, не могут иметь петли, потому что петля, соединяющая вершину с самой собой, является ребром (для ориентированного простого графа) или инцидентна (для ориентированного мультиграфа), которая не входит в . Итак, чтобы разрешить циклы, определения должны быть расширены. Для ориентированных простых графов определение следует изменить на . Для направленных мультиграфов определение следует изменить на . Чтобы избежать двусмысленности, эти типы объектов могут быть названы в точности ориентированным простым графом, разрешающим циклы, и ориентированным мультиграфом, разрешающим циклы (или колчаном ) соответственно.

Края направленного простого графа разрешающего петли является однородным отношением \ на вершинах , что называется отношение смежности о . В частности, для каждого ребра его концы и называются смежными друг с другом, что обозначается ~ .

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

Смешанный график представляет собой график , в котором некоторые ребра могут быть направлены и некоторые из них могут быть неориентированными. Это упорядоченная тройка G = ( V , E , A ) для смешанного простого графа и G = ( V , E , A , ϕ E , ϕ A ) для смешанного мультиграфа с V , E (неориентированные ребра), A (направленные ребра), ϕ E и ϕ A, определенные выше. Направленные и неориентированные графы - это особые случаи.

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

Взвешенный граф с десятью вершинами и двенадцатью ребрами.

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

Типы графиков

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

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

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

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

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

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

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

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

Конечный граф

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

Чаще всего в теории графов подразумевается, что обсуждаемые графы конечны. Если графики бесконечны, это обычно оговаривается особо.

Связанный граф

В неориентированном графе неупорядоченная пара вершин { x , y } называется связной, если путь ведет от x к y . В противном случае неупорядоченная пара называется отключенной .

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

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

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

К-вершинный граф соединены или к-кр-связный граф представляет собой график , в котором нет набора к - 1 вершине (соответственно, ребро) не существует , что, когда удаляется, разъединяет граф. К -vertex-связный граф часто называют просто к-связного графа .

Двудольный граф

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

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

График пути

Путь графа или линейный граф порядка п ≥ 2 представляет собой график , в котором вершины могут быть перечислены в порядке V 1 , V 2 , ..., v п такие , что ребра являются { v я , v я + 1 } , где i = 1, 2,…, n - 1. Графы путей можно охарактеризовать как связные графы, в которых степень всех вершин, кроме двух, равна 2, а степень двух оставшихся вершин равна 1. Если граф путей встречается как подграф другого графа, это путь в этом графе.

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

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

График цикла

Цикл графа или круговая диаграмма порядка п ≥ 3 представляет собой график , в котором вершины могут быть перечислены в порядке V 1 , V 2 , ..., v п такие , что ребра являются { v я , v я + 1 } , где i = 1, 2,…, n - 1, плюс ребро { v n , v 1 } . Графы циклов можно охарактеризовать как связанные графы, в которых степень всех вершин равна 2. Если граф циклов встречается как подграф другого графа, это цикл или схема в этом графе.

Дерево

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

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

Polytree

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

Polyforest (или направлены лес или ориентированные на лес ) представляет собой ориентированный ациклический граф, лежащий в основе неориентированный граф является лесом.

Продвинутые классы

Более сложные виды графиков:

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

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

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

Обычно вершины графа по своей природе как элементы множества различимы. Этот вид графов можно назвать вершинно-помеченными . Однако для многих вопросов лучше рассматривать вершины как неразличимые. (Конечно, вершины могут быть различимы по свойствам самого графа, например, по количеству инцидентных ребер.) Те же замечания относятся и к ребрам, поэтому графы с помеченными ребрами называются реберно-помеченными . Графы с метками, прикрепленными к ребрам или вершинам, обычно называются метками . Следовательно, графы, в которых вершины неразличимы, а рёбра неразличимы, называются немаркированными . (В литературе термин « маркированный» может применяться к другим видам маркировки, помимо той, которая служит только для различения различных вершин или ребер.)

Категория всех графиков является категория запятой Set ↓ D , где D : Set → Set является функтор принимает множество s для s × сек .

Примеры

Граф с шестью вершинами и семью ребрами.
  • Схема представляет собой схематическое изображение графа с вершинами и ребрами.
  • В информатике ориентированные графы используются для представления знаний (например, концептуального графа ), конечных автоматов и многих других дискретных структур.
  • Бинарное отношение R на множестве X определяет ориентированный граф. Элемент x из X является прямым предшественником элемента y из X тогда и только тогда, когда xRy .
  • Направленный граф может моделировать информационные сети, такие как Twitter , где один пользователь следует за другим.
  • Особенно регулярными примерами ориентированных графов являются графы Кэли конечно порожденных групп, а также графы смежных классов Шрайера.
  • В теории категорий каждая малая категория имеет направленный мультиграф, вершины которого являются объектами категории, а ребра - стрелками категории. На языке теории категорий говорят, что существует забывчивый функтор из категории малых категорий в категорию колчанов .

Графические операции

Есть несколько операций, которые создают новые графы из начальных, которые можно разделить на следующие категории:

Обобщения

В гиперграфе ребро может соединять более двух вершин.

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

Каждый граф порождает матроид .

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

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

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

Смотрите также

Примечания

использованная литература

дальнейшее чтение

внешние ссылки