ТЕОРИЯ ГРАФОВ

Непустое множество X и множество отношений T называется графом и обозначается . Граф называется конечным, если множество X конечно.

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

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

Матрицей смежности называется матрица А_n´n, у которой элемент a_ij равен количеству ребер, соединяющих вершины x_i и x_j.

Матрицей инцидентности называется матрица В_n´m, у которой элемент b_ij равен 1, если вершина x_i инцидентна ребру l_j, и равен 0 в противном случае.

Графы можно задавать списками пар вершин, соединенных ребрами или заданием для каждой вершины множества смежных вершин.

Характеристики графа

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

Степенью вершины x_i графа называется число d_i, равное количеству ребер графа, инцидентных этой вершине. Вершина называется четной (нечетной), если ее степень - четное (нечетное) число.

Теорема 1. Если конечный граф (без петель) имеет
n вершин и m ребер, то

.

Теорема 2. Число нечетных вершин любого графа четно.

Теорема 3. Во всяком графе с n вершинами (n >2) всегда найдутся, по меньшей мере, две вершины с одинаковыми степенями.

Теорема 4. Если в графе с n вершинами (n >2) в точности две вершины имеют одинаковую степень, то в этом графе всегда найдется либо в точности одна вершина степени 0, либо в точности одна вершина степени n - 1.

Путь и цикл в графе

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

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

Теорема 5. Если у графа все простые циклы четной длины, то граф не имеет ни одного цикла нечетной длины.

Связность графа, деревья

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

Теорема 6. Связный граф представляет собой простой цикл тогда и только тогда, когда каждая его вершина имеет степень 2.

Ребро (x_i, x_j) называется мостом, если в графе , полученном после удаления ребра (x_i, x_j), вершины x_i и x_j несвязны.

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

Плоские графы

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

Плоское представление имеет только плоский граф, и обратно: у всякого плоского графа всегда найдется плоское представление.

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

В плоском представлении дерева за грань принимают всю плоскость чертежа.

Для всякого плоского графа без перегородок число вершин n, число ребер m и число граней с учетом бесконечной g связаны соотношением

n - m + g = 2,

которое называется формулой Эйлера.

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

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

Теорема 7. Для любого плоского графа существует плоское представление, в котором все ребра - прямолинейные отрезки.

Эйлеровы графы

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

Теорема 8. Эйлеров граф является связным, и все его вершины - четными.

Теорема 9. Если граф связный и все его вершины четны, то он обладает эйлеровым циклом.

Теорема 10. Если граф обладает эйлеровым путем с концами А и В, то граф связный и А и В его единственные нечетные вершины.

Теорема 11. Если граф связный и А и В его единственные нечетные вершины, то граф обладает эйлеровым путем с концами А и В.

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

Гамильтоновы графы

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

Теорема 13. Граф с m вершинами имеет гамильтонов цикл, если для любой его вершины A_i

степ. (A_i) ³ m/2.

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

Ребро графа называется ориентированным, или дугой, если одну вершину считают началом, а вторую концом ребра. На рисунке дугу изображают стрелкой. Дугу с началом в вершине x_i и концом в вершине x_j обозначают (x_i, x_j).

Граф, все ребра которого ориентированы, называется ориентированным графом. Число дуг, исходящих из вершины ориентированного графа x_i, называется полустепенью исхода вершины x_i; число дуг, входящих в вершину x_i, называется полустепенью захода вершины x_i.

Вершина x_i называется источником, если ее полустепень захода равна нулю; вершина x_i, называется стоком, если ее полустепень исхода равна нулю.

Последовательность дуг (x₁, x₂), (x₂, x₃) … (x_k-1, x_k), в которой конец предыдущей дуги совпадает с началом следующей, называется маршрутом от x₁ до x_k. Маршрут, в котором первая и последняя вершины совпадают, называется замкнутым. Маршрут, в котором все вершины различны, называется путем от x₁ до x_k.

Если существует путь из вершины x_i в вершину x_j, то говорят, что x_j достижима из x_i. Замкнутый путь называется контуром.

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

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

Ориентированный граф можно задать с помощью матрицы инцидентности. Пусть x₁, x₂, …, x_n - вершины графа, ℓ₁, ℓ₂, …, ℓ_m - дуги графа.

Матрицей инцидентности графа называется матрица В_n´m, у которой элемент b_ij равен 1, если дуга ℓ_j исходит из вершины x_i, равен , если дуга ℓ_j входит в вершину x_i, равен 0, если дуга ℓ_j и вершина x_i не инцидентны.