Граф (дискретная математика)

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

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

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

Определения

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

График

Граф (иногда называемый неориентированным графом , чтобы отличить его от ориентированного графа, или простым графом , чтобы отличить его от мультиграфа ) ^[4]^[5] представляет собой пару $G$ $= ($ $V$ $,$ $E$ $)$ , где $V$ — множество, элементы которого называются вершинами (единственное число: вершина), а $E$ — множество неупорядоченных пар вершин, элементы которых называются ребрами (иногда связями или линиями ). $\{v_{1},v_{2}\}$

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

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

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

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

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

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

Ребра графа определяют симметричное отношение на вершинах, называемое отношением смежности . В частности, две вершины $x$ и $y$ являются смежными, если ${x, y}$ является ребром. Граф полностью определяется своей матрицей смежности $A$ , которая является квадратной матрицей $n \times n$ , где $A ij$ указывает количество соединений от вершины $i$ до вершины $j$ . Для простого графа $A ij$ равно либо 0, что указывает на разрыв, либо 1, что указывает на соединение; более того, $A ii = 0,$ поскольку ребро в простом графе не может начинаться и заканчиваться в одной и той же вершине. Графы с самопетлями будут характеризоваться тем, что некоторые или все $A ii$ равны положительному целому числу, а мультиграфы (с несколькими ребрами между вершинами) будут характеризоваться тем, что некоторые или все $A ij$ равны положительному целому числу. Неориентированные графы будут иметь симметричную матрицу смежности (что означает $A ij = A ji$ ).

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

Ориентированный граф или орграф — это граф, в котором ребра имеют ориентацию.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Связный граф

В неориентированном графе неупорядоченная пара вершин { x , y } называется связанной , если путь ведет из 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 — это граф, в котором вершины могут быть перечислены в порядке v ₁ , v ₂ , …, v _n таким образом, что ребра — это { v _i , v _{i +1} }, где i = 1, 2, …, n − 1. Графы путей можно охарактеризовать как связные графы, в которых степень всех вершин, кроме двух, равна 2, а степень двух оставшихся вершин равна 1. Если граф путей встречается как подграф другого графа, то он является путем в этом графе.

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

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

График цикла

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

Дерево

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

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

Полидерево

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

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

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

Более продвинутые виды графиков:

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

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

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

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

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

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

Примеры

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

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

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

унарные операции , которые создают новый граф из исходного, например:
бинарные операции , которые создают новый граф из двух исходных, например:

Обобщения

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

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

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

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

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

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

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

Примечания

^ Трудо, Ричард Дж. (1993). Введение в теорию графов (Исправленное, дополненное переиздание. ред.). Нью-Йорк: Dover Pub. стр. 19. ISBN 978-0-486-67870-2. Архивировано из оригинала 5 мая 2019 . Получено 8 августа 2012 . Граф — это объект, состоящий из двух множеств, называемых его множеством вершин и его множеством ребер .
^
См.:
- JJ Sylvester (7 февраля 1878 г.) «Химия и алгебра», Архивировано 04.02.2023 в Wayback Machine Nature , 17 : 284. doi :10.1038/017284a0. Со страницы 284: «Таким образом, каждый инвариант и ковариант становится выразимым графиком, точно идентичным диаграмме Кекуле или хемикографу».
- JJ Sylvester (1878) «О применении новой атомной теории к графическому представлению инвариантов и ковариантов двоичной квантики, – с тремя приложениями», Архивировано 04.02.2023 в Wayback Machine American Journal of Mathematics, Pure and Applied , 1 (1): 64–90. doi :10.2307/2369436. JSTOR 2369436. Термин «граф» впервые появляется в этой статье на странице 65.
^ Гросс, Джонатан Л.; Йеллен, Джей (2004). Справочник по теории графов. CRC Press . стр. 35. ISBN 978-1-58488-090-5. Архивировано из оригинала 2023-02-04 . Получено 2016-02-16 .
^ Бендер и Уильямсон 2010, стр. 148.
^ См., например, Иянага и Кавада, 69 J , с. 234 или Биггс, с. 4.
^ Бендер и Уильямсон 2010, стр. 149.
^ Грэм и др., стр. 5.
^ ab Bender & Williamson 2010, стр. 161.
^ Стрэнг, Гилберт (2005), Линейная алгебра и ее приложения (4-е изд.), Brooks Cole, ISBN 978-0-03-010567-8
^ Льюис, Джон (2013), Java Software Structures (4-е изд.), Pearson, стр. 405, ISBN 978-0133250121
^ Флетчер, Питер; Хойл, Хьюз; Патти, К. Уэйн (1991). Основы дискретной математики (Международное студенческое изд.). Бостон: PWS-KENT Pub. Co. стр. 463. ISBN 978-0-53492-373-0Взвешенный граф — это граф , в котором каждому ребру e присвоено число w ( e ), называемое его весом .
^ Гранджин, Мартин (2016). «Анализ социальной сети Twitter: картирование сообщества цифровых гуманитарных наук». Cogent Arts & Humanities . 3 (1): 1171458. doi : 10.1080/23311983.2016.1171458 . Архивировано из оригинала 2021-03-02 . Получено 2019-09-16 .
^ Панкадж Гупта, Ашиш Гоэль, Джимми Лин, Аниш Шарма, Донг Ван и Реза Босаг Заде WTF: Система «на кого подписаться» в Twitter. Архивировано 12 июля 2019 г. в Wayback Machine , Труды 22-й международной конференции по Всемирной паутине . doi : 10.1145/2488388.2488433.

Ссылки

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

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

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

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

Библиотечные ресурсы по теме
Граф (математика)

Ресурсы в вашей библиотеке

Медиафайлы по теме Граф (дискретная математика) на Викискладе
Вайсштейн, Эрик В. "Граф". MathWorld .