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

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

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

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

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

Определения

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

График

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

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

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

А мультиграф - это обобщение, которое позволяет нескольким ребрам иметь одну и ту же пару конечных точек. В некоторых текстах мультиграфы называются просто графами.^[6][7]

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

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

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

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

Ребра графа определяют симметричное отношение на вершинах, называемых отношение смежности. В частности, две вершины Икс и у находятся соседний если {Икс, у} это край. Граф может быть полностью задан своим матрица смежности А, что является nxn квадратная матрица, с А_ij указание характера связи между вершинами я и вершина j. Для простого графика А_ij= 0 или 1, что означает отключение или соединение соответственно, с А_ii= 0. Графики с петлями будут характеризоваться некоторыми или всеми А_ii равны положительному целому числу, а мультиграфы (с несколькими ребрами между вершинами) будут характеризоваться некоторыми или всеми А_ij равно положительному целому числу. Ненаправленные графы будут иметь симметричную матрицу смежности (А_ij= А_джи).

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

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

А ориентированный граф или же диграф это граф, в котором ребра ориентированы.

В одном ограниченном, но очень здравом смысле этого слова:^[8] а ориентированный граф пара ${ Displaystyle G = (V, E)}$ в составе:

• ${ displaystyle V}$, а набор из вершины (также называемый узлы или же точки);
• ${ Displaystyle E substeq {(x, y) mid (x, y) in V ^ {2} ; { textrm {and}} ; x neq y }}$, а набор из края (также называемый направленные края, направленные ссылки, направленные линии, стрелки или же дуги) которые заказанные пары вершин (т. е. ребро связано с двумя различными вершинами).

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

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

В еще одном общем смысле термина, допускающем несколько ребер,^[8] а ориентированный граф упорядоченная тройка ${ Displaystyle G = (V, E, phi)}$ в составе:

• ${ displaystyle V}$, а набор из вершины (также называемый узлы или же точки);
• ${ displaystyle E}$, а набор из края (также называемый направленные края, направленные ссылки, направленные линии, стрелки или же дуги);
• ${ displaystyle phi: E to {(x, y) mid (x, y) in V ^ {2} ; { textrm {and}} ; x neq y }}$, функция инцидентности отображение каждого ребра на упорядоченная пара вершин (т. е. ребро связано с двумя различными вершинами).

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

А петля это ребро, соединяющее вершину с самой собой. Направленные графы, как это определено в двух определениях выше, не могут иметь циклов, потому что цикл, соединяющий вершину ${ displaystyle x}$ самому себе является ребром (для ориентированного простого графа) или инцидентно (для ориентированного мультиграфа) ${ Displaystyle (х, х)}$ которого нет в ${ displaystyle {(x, y) mid (x, y) in V ^ {2} ; { textrm {and}} ; x neq y }}$. Поэтому, чтобы разрешить циклы, определения должны быть расширены. Для ориентированных простых графов определение ${ displaystyle E}$ следует изменить на ${ Displaystyle E substeq {(x, y) mid (x, y) in V ^ {2} }}$. Для направленных мультиграфов определение ${ displaystyle phi}$ следует изменить на ${ displaystyle phi: E to {(x, y) mid (x, y) in V ^ {2} }}$. Во избежание двусмысленности эти типы объектов можно назвать именно ориентированный простой граф, разрешающий петли и направленные мультиграфические разрешающие петли (или колчан ) соответственно.

Ребра ориентированного простого графа, допускающие петли ${ displaystyle G}$ это однородное отношение ~ на вершинах ${ displaystyle G}$ это называется отношение смежности из ${ displaystyle G}$. Конкретно для каждого ребра ${ Displaystyle (х, у)}$, его конечные точки ${ displaystyle x}$ и ${ displaystyle y}$ как говорят соседний друг к другу, что обозначается ${ displaystyle x}$ ~ ${ displaystyle y}$.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

График пути

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

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

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

График цикла

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

Дерево

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

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

Polytree

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

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

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

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

• Граф Петерсена и его обобщения;
• идеальные графики;
• кографы;
• хордовые графы;
• другие графики с большими группы автоморфизмов: вершинно-транзитивный, дуговой переходный, и дистанционно-транзитивные графы;
• сильно регулярные графы и их обобщения дистанционно регулярные графы.

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

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

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

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

В категория всех графов категория срезов Установить ↓ D куда D: Set → Set - это функтор брать набор s к s × s.

Примеры

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

• Схема представляет собой схематическое изображение графа с вершинами ${ Displaystyle V = {1,2,3,4,5,6 }}$ и края ${ Displaystyle E = { {1,2 }, {1,5 }, {2,3 }, {2,5 }, {3,4 }, {4 , 5 }, {4,6 } }.}$
• В Информатика ориентированные графы используются для представления знаний (например, концептуальный граф ), конечные автоматы, и многие другие дискретные структуры.
• А бинарное отношение р на съемочной площадке Икс определяет ориентированный граф. Элемент Икс из Икс является прямым предшественником элемента у из Икс если и только если xRy.
• Направленный граф может моделировать информационные сети, такие как Twitter, когда один пользователь следует за другим.^[12][13]
• Особенно регулярные примеры ориентированных графов даются Графики Кэли конечно порожденных групп, а также Графы смежных классов Шрайера
• В теория категорий, каждый малая категория имеет лежащий в основе ориентированный мультиграф, вершинами которого являются объекты категории, а ребрами - стрелки категории. На языке теории категорий говорят, что существует забывчивый функтор от категория малых категорий к категория колчанов.

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

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

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

Обобщения

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

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

Каждый граф дает начало матроид.

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

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

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

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

• Концептуальный график
• График (абстрактный тип данных)
• База данных графиков
• Рисование графика
• Список тем теории графов
• Список публикаций по теории графов
• Теория сети

Примечания

Рекомендации

• Балакришнан, В. К. (1997). Теория графов (1-е изд.). Макгроу-Хилл. ISBN  978-0-07-005489-9.
• Bang-Jensen, J .; Гутин, Г. (2000). Орграфы: теория, алгоритмы и приложения. Springer.
• Бендер, Эдвард А .; Уильямсон, С. Гилл (2010). Списки, решения и графики. Знакомство с вероятностью.
• Берже, Клод (1958). Теория графических и других приложений (На французском). Пэрис: Данод.
• Биггс, Норман (1993). Алгебраическая теория графов (2-е изд.). Издательство Кембриджского университета. ISBN  978-0-521-45897-9.
• Боллобаш, Бела (2002). Современная теория графов (1-е изд.). Springer. ISBN  978-0-387-98488-9.
• Дистель, Рейнхард (2005). Теория графов (3-е изд.). Берлин, Нью-Йорк: Springer-Verlag. ISBN  978-3-540-26183-4.
• Graham, R.L .; Grötschel, M .; Ловас, Л. (1995). Справочник по комбинаторике. MIT Press. ISBN  978-0-262-07169-7.
• Гросс, Джонатан Л .; Йеллен, Джей (1998). Теория графов и ее приложения. CRC Press. ISBN  978-0-8493-3982-0.
• Гросс, Джонатан Л .; Йеллен, Джей (2003). Справочник по теории графов. CRC. ISBN  978-1-58488-090-5.
• Харари, Фрэнк (1995). Теория графов. Издательство Эддисон Уэсли. ISBN  978-0-201-41033-4.
• Иянага, Сёкити; Кавада, Юкиёси (1977). Энциклопедический математический словарь. MIT Press. ISBN  978-0-262-09016-2.
• Цвиллинджер, Даниэль (2002). Стандартные математические таблицы и формулы CRC (31-е изд.). Чепмен и Холл / CRC. ISBN  978-1-58488-291-6.

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

• Трюдо, Ричард Дж. (1993). Введение в теорию графов (Исправленное, расширенное переиздание. Ред.). Нью-Йорк: Dover Publications. ISBN  978-0-486-67870-2. Получено 8 августа 2012.

внешняя ссылка

• СМИ, связанные с Граф (дискретная математика) в Wikimedia Commons
• Вайсштейн, Эрик В. «График». MathWorld.