Теория графов

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

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

В одном ограниченном, но очень распространенном смысле этого термина ^{[1] [2]} граф представляет собой упорядоченную пару , состоящую из:${\ Displaystyle G = (В, Е)}$

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

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

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

Рисунок графика .

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

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

Сетевой граф, сформированный редакторами Википедии (ребра), вносящими вклад в различные языковые версии Википедии (вершины) в течение одного месяца летом 2013 г. ^[6]

Теория графов в социологии: Социограмма Морено (1953). ^[16]

Проблема Кенигсбергского моста