Полный граф на десяти вершинах¶

Полный граф на десяти вершинах (обозначается K₁₀) — граф, каждая пара вершин которого соединена ровно одним ребром. В прикладной формулировке задачи это означает: если десять столбов соединены между собой проводами так, что от каждого столба отходит ровно девять проводов, то полученная структура является полным графом на десяти вершинах. Число рёбер такого графа равно 45, а суммарное число концов проводов — 90, что согласуется с условием: 10 столбов × 9 проводов = 90 концов, и каждый провод имеет ровно два конца.

¶Основные свойства

Полный граф Kₙ на n вершинах — граф, в котором любые две различные вершины соединены ребром. Каждая вершина имеет степень n − 1. Для n = 10 степень каждой вершины равна 9, что соответствует условию задачи о столбах и проводах.

Число рёбер полного графа вычисляется по формуле:

|E| = n(n − 1) / 2

При n = 10 это 10 × 9 / 2 = 45. Каждый из 45 проводов имеет два конца, поэтому суммарное число концов равно 90 — ровно столько же, сколько даёт умножение числа столбов на число проводов от каждого из них. Это частный случай формулы рукопожатий, согласно которой сумма степеней всех вершин графа всегда равна удвоенному числу рёбер.

Полный граф K₁₀ является регулярным графом девятой степени: все его вершины равнозначны, изометризм (автоморфизм) любой вершины в любую другую осуществляется соответствующей перестановкой. Число автоморфизмов Kₙ равно n!, то есть для K₁₀ — 3 628 800.

¶Связность и устойчивость

Полный граф обладает максимальной связностью среди графов на заданном числе вершин. Связность Kₙ равна n − 1, то есть для K₁₀ равна 9: чтобы разъединить граф, необходимо удалить не менее девяти вершин. Аналогично, чтобы сделать граф несвязным удалением рёбер, требуется убрать не менее 9 рёбер, исходящих из одной вершины.

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

¶Рёберная раскраска и задача о разбиении на пары

Полный граф на чётном числе вершин является графом чётной степени и потому 1-факторизуем: его множество рёбер можно разбить на n − 1 = 9 попарно не пересекающихся 1-факторов (perfect matchings), то есть на 9 классов, в каждом из которых все 10 столбов объединены в 5 попарно непересекающихся проводов.

Для K₁₀ это разбиение можно построить явно. Зафиксируем один столб (скажем, десятый) и рассмотрим остальные девять, пронумерованных от 1 до 9. В k-м классе (k = 1, …, 9) соединяем столб k с десятым, а остальные восемь столбов объединяем в пары по схеме «k + 1 с k + 8, k + 2 с k + 7, k + 3 с k + 6, k + 4 с k + 5» (арифметика ведётся по модулю 9). Каждый класс содержит 5 рёбер, покрывающих все 10 вершин, и все 9 классов вместе покрывают каждое ребро ровно один раз.

Эта конструкция связана с классической задачей о круговых турнирах: если 10 шахматистов играют турнир «каждый с каждым» в 9 туров, то в каждом туре каждый игрок играет ровно одну партию — и расписание туров задаётся именно 1-факторизацией K₁₀.

¶Планарность и вложение в плоскость

Полный граф Kₙ планарен тогда и только тогда, когда n ≤ 4. Уже K₅ непланарен, поэтому K₁₀ тем более не может быть нарисовано на плоскости без пересечений рёбер. По формуле Эйлера для планарных графов максимальное число рёбер равно 3n − 6 = 24 при n = 10, тогда как K₁₀ содержит 45 рёбер.

На сфере K₁₀, как и любой полный граф, допускает вложение без пересечений: вершины распределяются, например, по окружности экватора, а рёбра проводятся по дугам северного и южного полушарий.

¶Хроматические числа

Хроматическое число вершин K₁₀ равно 10: поскольку любые две вершины смежны, каждая из них требует собственного цвета. Хроматическое число рёбер равно 9 (равно степени регулярности): 45 рёбер раскрашиваются в 9 цветов, по 5 рёбер в каждом цвете, что соответствует 1-факторизации, описанной выше.

¶Применение модели

Конфигурация «10 объектов, попарно связанных проводами» встречается в нескольких областях:

• Теория графов — K₁₀ служит стандартным примером полного графа с чётным числом вершин при обсуждении 1-факторизации и задачи о круговом турнире.
• Коммуникационные сети — полная связность используется в ядрах небольших вычислительных систем, где каждый узел соединён с каждым выделенным каналом.
• Электротехника — задача о числе проводов при полной попарной коммутации n объектов решается формулой n(n − 1)/2; для 10 объектов требуется 45 проводов.
• Комбинаторика — K₁₀ входит в семейство графов, используемых при построении стейнеровых систем и конструкций, связанных с проективными плоскостями.

¶Смежные понятия

Полный двудольный граф K₅,₅ содержит 25 рёбер и также не является планарным. Дополнение K₁₀ — пустой граф на 10 вершинах без рёбер. Квадратом K₁₀ называется граф, у которого соединены не только смежные, но и вершины на расстоянии 2; поскольку в K₁₀ любые две вершины уже на расстоянии 1, квадрат совпадает с исходным графом.

Источники:

• Диест К. Графы. — М.: Техносфера, 2014.
• Бонди Дж., Мёрти У. Теория графов. — М.: Мир, 1974.
• Литвинов Г. Л. Дискретная математика. — М.: МЦНМО, 2010.
• Кормен Т., Лейзерсон Ч., Ривест Р., Штейн К. Алгоритмы: построение и анализ. — М.: Вильямс, 2011.