Экстремальные графы

Среди первых результатов в одном из направлений теории графов - теории экстремальных графов - можно отметить следующую известную теорему Турана [1]. Как обычно, пусть [r] - наибольшее целое число, не превышающее действительного числа r, а {r} = есть наименьшее целое число, не меньшее r .

Теорема:Наибольшее число ребер у графов, имеющих р вершин и не содержащих треугольников, равно[р2/4].

Доказательство: Утверждение очевидно для малых значений р. Доказательство по индукции можно дать отдельно для нечетных и для четных р; здесь будет рассмотрен только случай четных значений р. Предположим, что утверждение справедливо для всех четных значений р<=2п. Докажем его для р=2n+2. Итак, пусть G — граф с р=2n+2 вершинами, не содержащий треугольников. Поскольку граф G не является вполне несвязным, то в нем существуют две смежные вершиныuиv. В подграфе G' = G — {и, v} имеется 2n вершин и нет треугольников, так что по предположению индукции в графе G' самое большее [4n2/4] = n2 ребер. Сколько еще ребер может быть в графе G? В графе G нет такой вершины w, что вершиныuи v одновременно смежны с w, т. е. вершины и, v и w образуют в графе G треугольник. Таким образом, если вершинаuсмежна с k вершинами графа G', то вершина v может быть смежна самое большее с 2n—k вершинами. Поэтому в графе G не больше чем

n2+k+(2n—k)+l = n2+2n+1=p*p/4=[p²/4] ребер.

Для завершения доказательства осталось установить, что для каждого четного р существует (р, Р²/4)-граф, не содержащий треугольников. Такой граф можно образовать следующим образом: возьмем два множества V1 и V2, каждое из которых имеет р/2 вершин, и соединим каждую вершину из V1 с каждой вершиной из V2.

Двудольный граф(илибиграф) G - это граф, множество вершинVкоторого можно разбить на два подмножества V1 и V2 таким образом, что каждое ребро графа G соединяет вершины из разных множеств (будем говорить, что ребра графа G соединяют множества V1 и V2)- Например, граф, представленный на рис. слева, можно нарисовать так, как показано на рисунке справа, чтобы подчеркнуть, что этот граф - двудольный.

Если граф G содержит все ребра, соединяющие множества V1 и V2, то этот граф называется полным двудольным. Если при этом в множестве V1 имеетсяmвершин а в V2 имеетсяnвершин, то будем писать G =Km,n.= K(m,n). Звездойназывается полный двудольный граф К₁,n. Понятно, что в графе Кm,nимеетсяmnребер. Поэтому, если р четно, то граф К (р/2, р/2) содержит р2/4 ребер; если р нечетно, то граф К ([р/2], {р/2}) содержит [р/2] {р/2} = [p2/4] ребер. В каждом из таких графов нет треугольников, что следует из теоремы Кёнига

Теорема:Граф является двудольным тогда и только тогда, когда все его простые циклы четны.

Доказательство. Если G — двудольный граф, то множество его вершин V можно разбить на два подмножества V1 и V2 таким образом, что любое ребро этого графа соединяет некоторую вершину из множества V1 с некоторой вершиной из V2. Поэтому каждый простой цикл v1v2... vnv1 графа G содержит вершины из V1, скажем, с нечетными номерами и вершины из V2 с четными, так что длинаnэтого цикла является четным числом.

Чтобы доказать обратное, предположим, не теряя общности, что G — связный граф (поскольку каждую компоненту графа G можно рассматривать отдельно). Возьмем произвольную вершину vjV и обозначим через V1 множество, состоящее из v1 и всех вершин, находящихся в графе G на четном расстоянии от v1; пусть V2= V-V1. Так как все простые циклы графа G четны, то каждое его ребро соединяет множества V1 и V2. В самом деле, если существует ребро uv, соединяющее две вершины из множества V2, то объединение геодезических, идущих из вершины v1 к вершине u, а также из вершины v1 к вершинеu, вместе с ребром uv образует цикл нечетной длины; мы пришли к противоречию.

Теорема является первым примером решения одной из задач «теории экстремальных графов»: для данного графа Н найти ех(р, Н) — наибольшее число ребер, которое может быть в графе, имеющем р вершин и не содержащем запрещенный подграф H. Таким образом, в теореме утверждается, что ех (р, К3) = [p*p/4]. Приведем некоторые другие подобные результаты (Эрдёш [3]):

ex(p,Cp) = 1 + (p(p+1))/2

ex(p,K4-x) = [p*p/4]

ex(p,K1,3 + x) = [p*p/4]

Известно также, что каждый (2п,n*n+1)-граф содержит n треугольников, каждый (р, Зр-5)-граф содержит два простых цикла, не имеющих общих ребер (для р>= 6), и каждый (Зn, 3n₂+ 1)-граф содержит n₂простых циклов длины 4.