Раскраска графа – одно из главных направлений теории графов, которое находит свое применение в различных инженерных сферах. В нашем проекте мы рассмотрим реальную задачу по раскраске рёбер графа, модель которой была представлена на LI олимпиаде по математике 1988 года. Условие задачи: «Десять телефонов соединены проводами так, что каждый провод соединяет два телефона, каждая пара телефонов соединена не более чем одним проводом и от каждого телефона отходит не более трёх проводов. Нужно закрасить провода (каждый провод целиком одной краской) так, чтобы от каждого телефона выходит провода разных цветов. Какого наименьшего количества красок достаточно для такой закраски?»

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

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

Теорема Визинга: если максимальная степень вершин графа G равна k, χ′(G) – хроматический индекс графа G, то k ≤ χ′(G) ≤ k + 1.

Перейдем к доказательству теоремы. Нижняя граница очевидна: потребуется не менее, чем k цветов (k – максимальная степень вершины графа) чтобы раскрасить все ребра вершины со степенью k. Верхняя граница доказывается с помощью метода математической индукции. Максимальная степень k вершины рассмотренного ниже графа G равна 4, значит, 4 ≤ χ′(G) ≤ 5. Для раскраски использовано 5 цветов: зеленый, желтый, синий, оранжевый, красный.