Тема Графы и турниры

Формула Эйлера для графов и многогранников

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела графы и турниры

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#68881

На плоскости нарисовано несколько окружностей, причем каждая пара окружностей пересекается ровно в двух точках, и никакие три окружности не имеют общей точки. Круглосторонник - это часть плоскости, со всех сторон ограниченная дугами этих окружностей, граница которой состоит из каких-то дуг этих окружностей, причем между любыми двумя внутренними точками круглосторонника можно пройти, не пересекая ни одной дуги данных окружностей. Например, ниже изображены две окружности, образующие 3 круглосторонника, обозначенные номерами 1, 2 и 3.

$PIC$

Смежные круглосторонники - это круглосторонники, имеющие общую дугу окружности в качестве границы, причем дуга должна быть невырожденной, то есть не сводящейся к одной точке. Например, на рисунке выше смежными являются круглосторонники 1 и 2, 2 и 3, но не 1 и 3. Для какого наименьшего $C ≥2023$ можно нарисовать окружности так, что выполнены условия, перечисленные выше, и эти окружности образовывали ровно $C$ круглосторонников?

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

Источники: Иннополис-2023, 10-12 (см. dovuz.innopolis.university)

Подсказки к задаче

Подсказка 1

Круглосторонники, окружности… Ну и ну. Хотя, вообще-то, вся это конструкция кое-что напоминает, если посмотреть на это под другим углом. У нас есть дуги, которые соединяют точки пересечения окружностей, у нас есть вот эти круглосторонники, которые отделены дугами , и внутри которых дуг нет. На что это похоже?

Подсказка 2

Верно, на плоский граф. Но, поскольку вершины этого графа, то есть точки пересечения пар окружностей, соединены дважды, то это плоский мультиграф. Интересно. А какую главную формулу мы знаем про плоские графы(и мультиграфы в том числе)?

Подсказка 3

Верно, формулу Эйлера для плоских графов. V - E + F = 2, где V - число вершин графа, E - число ребер, а F - число граней(здесь стоит сказать, что у нас вне этого плоского мультиграфа, тоже есть часть плоскости, которая отделена ребрами и внутри которой их нет - это часть плоскости вне графа, ее тоже стоит учитывать). Предположим, что окружностей у нас m, что тогда можно сказать про V? А как связать E и V?

Подсказка 4

Верно, так как окружностей m и каждая пара пересекается в двух точках, то всего точек пересечений, то есть вершин, 2*m(m-1)/2 = m(m-1)=V. Так как каждая вершина - точка пересечения ровно двух окружностей, то из нее исходит ровно 4 ребра. А значит E=4V/2=2V=2m(m-1). А значит F = 2 + E - V = m(m-1) + 2. Вспомним про рассуждения из предыдущего пункта, что число круглосторонников меньше числа граней на 1. Значит число круглосторонников равно m^2-m+1. Значит, нам надо решить неравенство m^2-m+1>=2023. Значит, m>=46. Но нужно привести пример. Подумайте как это можно сделать, использовав как-то правильный многоугольник и/или повороты на угол вокруг одной точки(что в общем-то, почти одно и тоже).

Подсказка 5

Теперь построим пример, для всех таких m от 1 до 46, когда никакие три окружности не пересекаются в одной точке. Возьмем окружность A_0 и точку О внутри нее, не совпадающую с ее центром. После чего построим, для всех i от 1 до m-1, окружности, которые получаются из А_0 поворотом на i*2pi/m против часовой стрелки, с центром в точке О. Почему этот пример подходит?

Подсказка 6

Верно, так как при такой картинке, «внешние» вершины соседних образуют правильный m-угольник, О - центр этого многоугольника. Тогда построим другую, неподходящую картинку, когда все окружности - есть описанные вокруг O и проходящие через свою сторону m - угольника. Тогда можно провести окружность(она не относится к нашим и нужна только для построения) с центром в точке О и посмотреть на пересечения этой окружностью серперов из точки О к сторонам нашего m-угольника. Тогда возьмем новые m штук окружностей, которые проходят через соответствующие стороны m-угольника и соответствующие точки пересечения серперов технической окружностью. Тогда, очевидно, они все перестанут пересекаться, так как мы на совсем чуть-чуть(пусть радиус технической окружности очень близок к нулю) сдвинули наши окружности(в силу непрерывности, доказали). Остался второй пункт задачи. Попробуйте доказать от противного.

Подсказка 7

Если предположить, что каждый круглосторонник ограничен как минимум 4 дугами, то общее число дуг, которые ограничивает круглосторонник не меньше чем 4*C=4(m^2-m+1). Пусть К - кол-во внешних граней мультиграфа, тогда K+4C<=E. Но тогда K+4+2m(m-1)<=0, что невозможно, так как K>=0, 4>0, 2m(m-1)>=0. Значит, предположение неверно, а значит, найдется круглосторонник, ограниченный не более чем 3 дугами.

Показать ответ и решение

Рассмотрим нарисованные окружности как плоский мультиграф (граф с кратными ребрами между вершинами): вершины – точки пересечений, ребра – дуги нарисованных окружностей, ограниченные точками пересечений. В такой интерпретации круглосторонники — это все грани этого графа, кроме «внешней» (т.е. части плоскости, лежащей вне всех окружностей).

Пусть нарисованы ровно $m$ окружностей. Согласно формуле Эйлера для плоских графов,

V − E +F = 2,

где $V$ — число вершин графа, $E$ — число ребер, а $F$ — – число граней (включая внешнюю).

Так как каждая пара окружностей пересекается ровно в двух своих уникальных точках, то число вершин

m-(m-−-1) V = 2⋅ 2 = m(m− 1)

Так как каждая вершина – это точка пересечения ровно двух окружностей, то наш граф является регулярным степени $4$ (то есть в каждую вершину входят ровно $4$ ребра). Поскольку каждое ребро соединяет две вершины, общее число ребер

4V E = -2-= 2V = 2m(m− 1)

Следовательно число граней нашего плоского мультиграфа должно быть равно

F = 2+ E− V =2+ 2m(m − 1)− m(m − 1)= 2+ m(m − 1)

Значит, число круглосторонников

C =F − 1⇒ C =1+ m (m − 1)

Найти наименьшее $m,$ такое, что $C ≥ 2023$ — значит найти наименьшее натуральное решение неравенства

2 m − m − 2022≥ 0

Решив, получаем, что наименьшее $m$ равно $46,$ соответственно $C =1 +46⋅45= 2071.$

Теперь заметим, что для любого $m ≥ 1$ (в том числе для $m = 46)$ можно расположить $m$ окружностей на плоскости так, что каждая пара пересекается ровно в двух своих уникальных точках. Действительно, нарисуем произвольную окружность $B$ на плоскости и выберем произвольную точку $O$ внутри нее (но не являющуюся ее центром), а потом рассмотрим $m$ окружностей $Bk,$ где $0≤ k≤ (m− 1),$ которые получаются в результате поворота окружности $B$ вокруг точки $O$ на угол $2πk m$ (окружность $B0$ совпадает с $B).$ На рисунке приведен пример для $m =4.$

$PIC$

Теперь докажем, что обязательно найдется круглосторонник, ограниченный менее чем $4-мя$ дугами. Предположим, что все круглосторонники ограничены не менее чем $4$ дугами. Тогда общее число «сторон» (дуг, ограничивающих круглосторонники) не меньше, чем $4C = 4(1+ m(m − 1)).$ Пусть $K$ — число границ внешней грани плоского мультиграфа, тогда

K + 4C = K +4+ 4m(m − 1)≤ 2m(m− 1)⇔ K +4 +2m (m − 2)≤ 0

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

Ответ: 2071

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#81162

В городе Озёрске семь озёр, соединённых десятью каналами так, что от любого озера можно доплыть до любого другого. Сколько островов в Озёрске?

Показать ответ и решение

Если считать, что озёра — вершины, а каналы — рёбра, то перед нами связный плоский граф с $7$ вершинами и $10$ рёбрами, значит мы можем использовать формулу Эйлера: $7− 10 +F = 2,$ откуда $F =5.$

Ответ:

$5$

Ошибка.
Попробуйте повторить позже

Задача 3#81165

Дан клетчатый прямоугольник $m ×n.$ Каждую его клетку разрезали по одной из диагоналей. На какое наименьшее число частей мог распасться прямоугольник?

Показать ответ и решение

Пример: в каждой клетке сделаем разрез от левого нижнего угла до правого верхнего.

Оценка: Построим граф, вершины будут соответствовать треугольничкам — половинам разрезанных клеток, а ребро между вершинами проведём, если соответствующие треугольнички имеют общий катет. Нетрудно понять, что каждой из частей, на которые распался прямоугольник, соответствует компонента связности нашего графа. Число вершин равно удвоенному числу клеток, то есть $2mn.$ Число ребер равно числу границ между соседними клетками, то есть $m(n− 1)+n(m − 1).$ По формуле Эйлера имеем $F = m+ n+ F − 1 ≥m + n.$

Ответ:

$m + n$

Ошибка.
Попробуйте повторить позже

Задача 4#81167

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

Показать ответ и решение

Из условия следует, что в каждой вершине сходятся два шестиугольника и один пятиугольник. Построим граф, где вершинами будут вершины пятиугольников и шестиугольников, а рёбрами — их стороны. Пусть в полученном графе будет $n$ вершин. Посчитаем количество шестиугольников: в каждую вершины входит по два шестиугольника и каждый шестиугольник имеет шесть вершин, а значит всего должно быть $2n- n 6 = 3$ шестиугольников. Аналогично получим, что должно быть $n 5$ пятиугольников. Заметим, что количество граней равно количеству многоугольников, то $n n 8- 3 + 5 = 15.$ Граф связен, а значит по теореме Эйлера в нём $23n 15 − 2$ рёбер. С другой стороны, степень каждой вершины равна $3,$ то есть всего $3n 2$ рёбер. Получаем уравнение $23n- 3n 15 − 2= 2 ,$ из которого следует, что $n =60.$