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

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

Впервые понятие «граф» ввёл в 1936 году венгерский математик Денеш Кëниг. Однако первая работа по теории графов была написана еще в 1736 году ЛеонардомЭйлером, в которой он решил «задачу о кëнигсбергских мостах». Суть этой задачи состоит в следующем. На рис. 1 представлена схема центральной части города Кëнигсберг (ныне Калининград), которая включает два берега реки, два острова в ней и семь соединяющих их мостов. Требуется обойти все четыре части суши, пройдя по каждому мосту один раз, и вернуться в исходную точку. Позже мы рассмотрим решение этой задачи.

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

Следует отметить, что для понятия «граф» нет общепризнанного единого определения. Разные авторы подразумевают под «графом» различные объекты, хотя и очень похожие. В данном пособии рассматриваются только конечные графы и используется терминология [5], позволяющая на множестве всех графов ввести бинарное отношение «быть частным случаем».

Основные понятия и определения

Пусть S – непустое конечное множество, V⁽²⁾ – множество всех его двухэлементных подмножеств.

Определение 1.1. Псевдографом (или просто графом) G называется пара множеств (S, U), где U – произвольное подмножество множества V⁽²⁾. При этом пишут G = (S, U).

Определение 1.2. Пусть G = (S, U) – псевдограф. Элементы множества S называются вершинами графа G, а элементы множества U – его рëбрами.

Определение 1.3. Граф G = (S, U) называется пустым или нуль-графом, если

U = Æ.

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

Если порядок графа равен n, то пишут = n.

Двухэлементное подмножество множества S (ребро), принадлежащее U и состоящее из элементов x и y, будем обозначать через (x, y).

В общем случае множество U может содержать пары с одинаковыми элементами вида (x, x) и одинаковые пары.

Определение 1.5. Рëбра вида(x, x) называются петлями.

Определение 1.6. Одинаковые пары из множества U называются кратными (или параллельными) рëбрами.

Таким образом, псевдограф может содержать петли и кратные рëбра. В этом смысле псевдографы еще называются графами с кратными рëбрами и петлями.

Определение 1.7. Псевдограф без петель называется мультиграфом (или графом с кратными рëбрами).

Определение 1.8. Мультиграф без кратных рëбер называется простым графом.

Таким образом, простой граф не содержит петель и кратных рëбер.

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

Пример 1.1. Указать, какие из графов, диаграммы которых изображены на

рис. 2, являются псевдографами, мультиграфами, простыми графами.

Решение. Все графы являются псевдографами, графы G₁, G₃, G₄, G₅ – мультиграфами, графы G₁, G₄, G₅ – простыми графами. 

Определение 1.9. Граф называется неориентированным (кратко – неорграфом), если пары в множестве U являются неупорядоченными.

Если (x, y) – неупорядоченная пара, то ребро (x, y) называется неориентированным, а вершины x и y называются концами неориентированного ребра

(x, y).

Определение 1.10. Граф называется ориентированным (кратко – орграфом), если пары в множестве U являются упорядоченными.

Определение 1.11. Ребра орграфа называются дугами (или ориентированными ребрами).

Вершина x дуги (x, y) называется еë началом, а вершина y – еë концом. В этом случае говорят, что дуга (x, y) исходит из вершины x и входит в вершину y.

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

Замечание 1.1. Неориентированное ребро (x, y) равносильно двум противоположно направленным дугам (x, y) и (y, x). Поэтому неорграф можно рассматривать как орграф, который вместе с каждой дугой (x, y) содержит и дугу (y, x) противоположного направления. 

Условимся вершины графа обозначать буквами x, y, z (без индексов или с индексами), а ребра и дуги – буквами v, u, w (без индексов или с индексами).

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

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

Определение 1.13. Вершина x и ребро u графа называются инцидентными, если x является концом ребра u, и неинцидентными в противном случае.

Определение 1.14. Две вершины графа называются смежными, если существует инцидентное им ребро.

Определение 1.15. Число рëбер (дуг) графа (орграфа) G, инцидентных данной вершине x_i называется степенью (валентностью) вершины x_i и обозначается через deg (x_i) (от англ. degree – степень).

Определение 1.16. Вершина графа называется изолированной, если еë степень равна нулю.

Определение 1.17. Вершина графа называется висячей, если еë степень равна единице.

Замечание 1.2. В случае неориентированного псевдографа обычно считается, что вклад каждой петли, инцидентной некоторой вершине x, в еë степень P (x) равен 2, в то время как вклад любого другого ребра, инцидентного вершине x, равен 1. 

Определение 1.18. Полустепенью исхода (захода) вершины x_i орграфа называется число deg ⁺ (x_i) (deg ^– (x_i)) его дуг, исходящих из вершины x_i (заходящих в вершину x_i).

Для орграфа deg (x_i) = deg ⁺ (x_i) + deg ^– (x_i).

Замечание 1.3. В случае ориентированного псевдографа вклад каждой петли, инцидентной некоторой вершине x, равен 1, как в deg ⁺ (x), так и в deg ^– (x). 

Пример 1.2. Найти степени вершин x₂, x₄ графа G₁ и полустепени исхода и захода вершин x₂, x₄ графа G₂, изображëнных на рис. 3.

Решение. Для графа G₁ имеем:

deg (x₂) = 2и deg (x₄) = 5.

Для графа G₂ имеем:

deg ⁺ (x₂) = 2, deg ^– (x₂) = 3 и

deg ⁺ (x₄) = 2, deg ^– (x₄) = 1. 

Определение 1.19. Неориентированный простой граф, в котором любые две различные вершины смежны, называется полным. Полный граф порядка n обозначается через K_n.

На рис. 4 изображены диаграммы полных графов K₁, K₂, K₃ и K₄.

Определение 1.20. Неорграф называется двудольным, если существует такое разбиение множества его вершин на две части (доли), что концы каждого ребра принадлежат разным частям.

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

На рис. 5 изображены полные двудольные графы K_1,4 и K_3,3.