«Друг моего друга мне не друг» или две теоремы теории графов. Решения задач.

Это страница содержит решения задач, предложенных здесь

1. В шахматном турнире принимает участие 15 шахматистов. Возможна в течении турнира ситуация, когда каждый шахматист сыграл ровно 7 партий?

Сопоставим каждому шахматисту вершину графа, а каждой сыгранной партии — ребро графа, соединяющего вершины, соответствующие игравшим в ней шахматистам. Тогда количество сыгранных шахматистом партий равно степени соответствующей вершины. Если каждый шахматист сыграл 7 партий, сумма степеней вершин равна $15 \cdot 7 =105$, что невозможно, так как, согласно лемме о рукопожатиях, сумма степеней вершин четна.

2. На плоскости даны 60 точек. Какое наибольшее количество отрезков можно провести, чтобы в любом множестве из $n$ точек нашлись две точки, не соединенные между собой отрезком. Рассмотрите случаи $n=3,4,5,9,10,11$.

Данное множество точек и отрезков можно рассматривать, как граф из 60 вершин. Максимальное количество ребер дает граф Турана T(15,k), где $k=n-1$. Введем обозначение ($1800=\frac{60^2}{2}$): $$ t(k)= 1800 \left(1−\dfrac{1}{k}\right) $$

Тогда, если $k$ — делитель 60, то $r_{max}(60,k) = t(k)$ Значения $n=3,4,5,11$ (отвечающие $k=2,3,4,10$) удовлетворяют этому требованию, так что имеем: $\begin{matrix}\\ n=3: & r_{max}(60,2) = & t(2)=& 900 & | & n=4: & r_{max}(60,3) = & t(3)=& 1200 \\ n=5: & r_{max}(60,4) =& t(4)=& 1350 & | & n=11: & r_{max}(60,10) =& t(10)=& 1620 \end{matrix}$

Осталось рассмотреть случаи $n=9$ и $n=10$:

$n=9:$ Так как $t(8)=1575$ — целое число, то согласно (11) части 2, $r_{max}(60,8)=t(8)-1=1574$

$n=10:$ Так как $k=9$ превышает 8, приходится пользоваться непосредственно (10) части 2. Имеем $t(9)=1600$ и $b=6$ (остаток от деления 60 на 9), так что, согласно (10), $r_{max}(60,9)=1600-\dfrac{6\cdot3}{18}=1599$.

3. На плоскости даны 15 точек, так что никакие три из них не лежат на одной прямой. Какое наименьшее количество отрезков следует провести, чтобы в любом множестве из $n$ точек нашлись две точки, соединенные между собой отрезком. Рассмотрите случаи $n=3,4,5$.

Данное множество точек и отрезков можно рассматривать, как граф из 60 вершин. Условие означает, что в графе не существует независимых подмножеств, содержащих $n$ вершин. Рассмотрим тогда дополнительный граф, то есть граф, соединяющий ребрами те и только те вершины, которые не были соединены в исходном графе. Каждому независимому множеству из $n$ вершин в исходном графе соответствовал бы полный подграф порядка $n$ в дополнительном подграфе. Отсутствие таких множеств означает отсутствие в дополнительном графе полных подграфов порядка $n$. Отсюда в дополнительном подграфе не более $r_{max}(60,k)$ вершин ($k=n-1$). Так как полный 60-вершинный граф имеет $\frac{60 \cdot 59}{2}= 1770$ ребер, исходный граф имеет не менее $1770-r_{max}(60,k)$

Используя результаты предыдущей задачи, обозначив для краткости искомые значения через $c_{min}(60,k)$, получаем: $\begin{matrix}\\ n=3: & c_{min}(60,2) = & 870 & | & n=4: & c_{min}(60,3) = & 570 \\ n=5: & c_{min}(60,4) = & 420 & | & n=9: & c_{min}(60,8) = & 196 \\ n=10: & c_{min}(60,9) = & 171 & | & n=11: & c_{min}(60,10) = & 150 \\ \end{matrix}$

Догадались, где используется условие «никакие три из них не лежат на одной прямой»? Ведь, с формальной точки зрения это геометрическая задача, в которой графы не упоминаются. Если три точки $А, B, C$ лежат на одной прямой, то отрезок, соединяющий крайние точки $A$ и $С$ пройдет через $B$ что, конечно, не существенно в теории графов, зато имеет значение с геометрической точки зрения. Поэтому, такой случай следует исключить. В следующей задаче автор пошел дальше, позаботившись о том, чтобы все линии были скрещивающимися, полностью исключая возможность самопересечений. Появление фразы «никакие 4 не лежат в одной плоскости» в скобках возможно связано с тем, что она была добавлена в последний момент. В рассуждении это условие нигде явно не используется.

4. В пространстве расположено $2n$ ($n\geslant 2$) точек (так что никакие 4 не лежат в одной плоскости) и проведено $n^2+1$ отрезков с концами в этих точках. Докажите, что проведенные отрезки образуют: а) хотя бы один треугольник; б)* не менее $n$ треугольников.

Задачник Кванта. Задача М934. «Квант» 1985 № 7 стр. 42

Пункт а) сразу следует из теоремы Мантеля. Действительно, если граф не содержит треугольников, то количество вершин не превышает $\dfrac{(2n)^2}{4}=n^2$, а так как вершин на 1 больше, то хотя бы один треугольник должен быть.

Пункт b) далеко не столь очевиден. Хотя, если подумать, здесь тоже все логично. Вспомним, что максимум ребер $2n$-вершинного графа дает полный двудольный граф по $n$ вершин в каждой доле, поэтому добавить одну вершину, можно только в какую-то из долей. Поскольку каждая из вершин, которые добавленное ребро соединяет, инцидентна $n$ вершинам другой доли, получаем как раз $n$ новых треугольников.

Однако, вы заметили в вышеприведенном рассуждении изъян? Откуда известно, что какой-нибудь граф, не являющийся максимальным, не даст больше треугольников при добавлении ребра? Как видите, все это не так просто, как кажется на первый взгляд. Приходится пасовать и привести авторское доказательство (С.Б. Гашков. «Квант» 1985 № 11, стр 37-38), которое лишь чуть-чуть детализировано для прояснения моментов, которые могут быть непонятны неискушенному читателю.

Докажем индукцией по $n$ ($n \geslant 2$).

База индукции. При n=2 имеем имеем граф из 4 вершин. Полный граф имеет 6 ребер (4 стороны и две диагонали) и 4 треугольника (по два, прилежащих каждой диагонали). Интересующий нас граф имеет $n^2+1=5$ ребер, то есть одним ребром меньше. Легко видеть, что удаление любого ребра (стороны или диагонали) сохраняет 2 (то есть $n$) треугольника.

Индукционный переход. Допустим, что утверждение верно для $2n$ вершин. Рассмотрим граф из $2(n+1)$ вершин и $(n+1)^2+1$ ребер. Согласно пункту а) (то есть теореме Мантеля) в нем обязательно есть треугольник, назовем его $ABC$. Поскольку треугольников должно быть $(n+1)$, требуется доказать существование еще $n$ из них.

Обозначим количество ребер, выходящих из вершин $A$, $B$ и $C$ не считая ребер треугольника ABC через $k_A$, $k_B$ и $k_C$ соответственно (каждое из этих величин на единицу меньше степени соответствующей вершины). Введем обозначение $k = k_A + k_B + k_C$ и рассмотрим следующие два случая.

Случай 1. $k \leslant 3n-2$. Если каждое из $k_A + k_B$, $k_A + k_С$, $k_A + k_B$ не меньше $2n-1$, то суммируя все три неравенства, получим: $2(k_A+k_B+k_C) \geslant 6n-3$, или $к \geslant 3n-1$, что противоречит предположению $k \leslant 3n-2$. Таким образом, одна из сумм, для определенности $k_A + k_B$ не превосходит $2n-2$. Исключив точки $A$ и $B$, а также все инцидентные им ребра, включая ребра треугольника $ABC$, получим граф из $(n+1)^2+1-(k_A + k_B)-3$ ребер, что не менее $(n+1)^2+1-(2n-2)-3 = n^2+1$ ребер. Согласно индукционному предположению он образует не менее $n$ треугольников, что и требовалось доказать.

Случай 2. $k \geslant 3n-1$. Среди $2n+2-3=2n-1$ вершин, отличных от $A$, $B$ и $C$ рассмотрим по-отдельности вершины, соединенные с одной двумя или всеми тремя вершинами треугольника $ABC$. Обозначим количество таких вершин через $n_1$, $n_2$ и $n_3$ соответственно. Тогда $$ n_1 + n_2 + n_3 \leslant 2n-1 $$ (неравенство вызвано тем, что некоторые вершины могут не быть соединены ни с одной из $A$, $B$, $C$). Подсчитав количество ребер, инцидентных $A$, $B$ и $C$ (кроме ребер треугольника $ABC$) получим: $$ n_1+2n_2+3n_3=k \geslant 3n-1$$

Надеюсь, вы не забыли, что целью всего этого является доказательство существования дополнительных $n$ треугольников. Подсчитаем количество дополнительных треугольников $t$, образованных ребрами треугольника $ABC$. Каждая внешняя вершина соединенная с тремя ребрами из $ABC$ образует три таких треугольника, вершина, соединенная с двумя ребрами из $ABC$ образует 1 треугольник, прочие внешние вершины не образуют треугольников со ребрами треугольника $ABC$. Таким образом, $$ t=n_2+3n_3 \geslant n_2+2n_3 = (n_1+2n_2+3n_3)-(n_1+n_2+n_3) $$

Применяя полученные ранее неравенства, получаем: $t \geslant (3n-1)-(2n-1) = n$, чем ставится окончательная точка в доказательстве.

Одно из красивейших доказательств, которые я когда-либо встречал!