Основные понятия теории графов

Граф G состоит из множества вершин Х (точек) и множества ребер U (линий) соединяющих между собой все или часть вершин. Обозначение графа G=(X;U). Запись u_ijU означает, что ребро графа u_ij=(x_i, x_j) образовано парой вершин x_i и x_j, x_iX, x_jX. Таким образом, ребра — это упорядоченные пары вершин.

С помощью графов можно отразить наиболее общие свойства объектов (топологические свойства), отвлекаясь от их геометрических форм и размеров.

Если ребра ориентированы, что обычно показывают стрелками, то они называются дугами, и граф с такими ребрами называется ориентированным графом. Для такого графа u_kj=(x_k, x_j)(x_j, x_k)=u_jk — это различные ребра Если ребра не имеют ориентации, граф называется неориентированным.

Для него u_kj=(x_k, x_j)=(x_j, x_k)=u_jk.

Пример:

Вершины: здания; ребра: прямые улицы В нашем курсе изучаются неориентированные графы. Две вершины x_i и x_j называются смежными, если существует ребро u_ijU, соединяющее эти вершины. Другими словами, смежными называются вершины, прилегающие к одному и тому же ребру.

Ребро u_ij инцидентно вершинам x_i, x_j, если оно связывает эти вершины. Ребра u_kl, u_lm называются смежными, если они имеют общую вершину (в примере вершина l).

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

Петли — ребра графа, у которых обе концевые вершины совпадают, то есть u_ij=(x_i, x_j), i=j (рис. 1.2).

Число ребер, инцидентных некоторой вершине, называют степенью вершины, обозначается p (x). Для графа на рис 1(а) p (x₅)=3, p (x₁)=1. Легко увидеть, что если сложить степени всех вершин графа, то получится четное число равное удвоенному числу ребер, так как каждое ребро участвует в сумме 2 раза. Этот результат называют леммой Эйлера о рукопожатиях (если несколько человек обменялись рукопожатием, то число пожатых рук — четно). Из этой леммы следует, что в любом графе число вершин нечетной степени всегда четно.

Лемма о рукопожатиях. Число вершин в графе (или мультиграфе без петель), имеющих нечетную степень, четно.

Доказательство леммы. Заметим, что сумма степеней всех вершин в графе (или мультиграфе без петель) должна быть четной. Это следует из того, что если взять вершины, вообще не связанные друг с другом, то сумма степеней этих вершин равна нулю. Прибавляя любое ребро, которое связывает две вершины, увеличиваем сумму всех степеней на 2 единицы. Таким образом, сумма всех степеней вершин четна. Удаляя из этой суммы степени четных вершин, получим, что сумма степеней нечетных вершин, должна быть четной. Это значит, что само число таких вершин должно быть четным. Лемма доказана.