Определение графа

Как было сказано во введении, первая работа по теории графов принадлежит Л.Эйлеру, и опубликована она была в 1736 г., однако термин “граф” впервые появился в книге венгерского математика Д. Кенига в 1936 г.

Дадим определение графа.

Пусть V - непустое множество, V ^{2} - множество всех его двухэлементных подмножеств. Пара (V, E), где Е Í V ^{2} называется графом (неориентированным графом).

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

Элементы множества V называются вершинами графа, а элементы множества Е называют рёбрами графа.

Число вершин графа G =(V, E) называется его порядком.

Исходя из определения графа, каждому ребру соответствует двухэлементное подмножество вершин. Если подмножество { v ₁, v ₂} соответствует ребру е, то говорят, что ребро е инцидентно вершинам v ₁ и v ₂, а вершины v ₁ и v ₂ смежны. Также говорят, что ребро е соединяет вершины v ₁ и v ₂. Вершины v ₁ и v ₂ называются концевыми вершинами ребра е.

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

Граф G =(V, E), V ={ v ₁, v ₂, v ₃, v ₄}, E ={{ v ₁, v ₂}, { v ₁, v ₄}, { v ₂, v ₃}, { v ₂, v ₄}, { v ₃, v ₄}} представлен графически на рис.1.1.

Обобщим понятие графа.

Мультиграф – это пара (V, E), где V - непустое множество, а E - семейство подмножеств множества V ^{2}.

Употребление термина “семейство” вместо “подмножество” означает, что элементы множества V ^{2} могут в E повторяться, то есть допускаются кратные рёбра.

Пример мультиграфа показан на рис. 1.2.

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

Такой граф называется псевдографом. Его пример приведен на рис. 1.3.

Псевдограф – это пара (V, E), где V - непустое множество (вершин), а E - некоторое семейство неупорядоченных пар вершин (рёбер), не обязательно различных.

Различают также ориентированные и смешанные графы.

Пусть V ⁽²⁾ - множество упорядоченных пар элементов множества V. Тогда ориентированный граф (или орграф) - это пара (V, А), где V - множество вершин, А Í V ⁽²⁾ - множество ориентированных рёбер, которые называются дугами.

Если пара (v ₁, v ₂) - дуга, то вершины v ₁ и v ₂ называются её началом и концом соответственно.

На рисунке дуги отмечаются стрелками, указывающими направление от начала к концу.

Орграф G =(V, E), V ={ v ₁, v ₂, v ₃, v ₄}, E ={(v ₁, v ₂), (v ₁, v ₄), (v ₂, v ₃), (v ₂, v ₄), (v ₃, v ₄)} представлен графически на рис.1.4.

Ориентированный мультиграф и ориентированный псевдограф определяются аналогично.

Смешанные графы имеют как дуги, так и неориентированные рёбра.

Пример смешанного графа представлен на рис. 1.5.

Ради сокращения речи термин “граф” употребляется вместо терминов “мультиграф”, ”орграф” и др., но подобные случаи либо специально оговариваются, либо ясны из контекста.

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