Тема КОМБИНАТОРИКА

Графы и турниры → .16 Формула Эйлера для графов и многогранников

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

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

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

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

Подтемы раздела комбинаторика

Разделы подтемы Графы и турниры

Индукция в графах и теорема Турана

Турниры в терминах графов и не только (считаем игры и очки)

Лемма о рукопожатиях

Считаем рёбра

Простой путь, Гамильтонов путь, Гамильтонов цикл

Подвешивание, ранжирование, упорядочивание в графах

Деревья и остовные деревья

Двудольные графы и переформулировки к ним

Связность и связные подграфы (клики)

Паросочетания и лемма Холла

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

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

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

Задача 1#139297Максимум баллов за задание: 7

Вася нашёл кубический граф (все степени вершин равны трём) и нарисовал его на плоскости без самопересечений так, что все рёбра являются отрезками, параллельными прямым $l1,$ $l2,$ $l3,$ причём рёбра, исходящие из одной вершины, параллельны разным прямым. Петя покрасил каждое ребро в красный или синий цвет так, что если три отрезка образуют «клювик», то центральное ребро одного цвета, а крайние другого, а если «треножку», то все цвета одинаковые.

$PIC$

1) Приведите пример получившейся картинки.

2) Покажите, что Васин граф — двудольный.

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

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

Источники: ЮМШ - 2024, 10.1 (см. yumsh.ru)

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

1) Рассмотрим красный шестиугольник и концентрический синий шестиугольник внутри него. Соединим соответственные вершины синими ребрами.

2) Без потери общности можно считать что углы между прямыми содержащими ребра расположены под углами в $∘ 60$ друг к другу. Рассмотрим произвольный цикл, он является $N$ -угольником. Рассмотрим некоторый угол этого $N$ -угольнка, если он равен $∘ 60$ или $∘ 300 ,$ то примыкающие стороны разноцетны, если же $∘ 120$ или $∘ 240 ,$ то ребра одноцветны. Из соображений чётности получаем, что углы $∘ 60$ и $∘ 300$ встречаются четное число раз, поэтому сумма углов делится на $∘ 120 ,$ но с другой стороны сумма углов $180(N − 2).$ Получили, что $N$ чётное, значит, все циклы имеют сётную длины, а это критерий двудольности.

3) Пусть в графе $n$ вершин, тогда ребер $3n -2 ,$ из формулы Эйлера граней $n 2 + 2.$ Посмотрим на грань, так как это цикл, он разноцветный, это происходит только грань содержит угол в $60∘$ , из соображений четности из предыдущего пункта, этих клювика хотя бы два. Каждый клювик содержит ровно два угла по $60∘,$ это позволяет оценит количество клювиков через число граней. Получили, что клювиков хотя бы $n2 + 2,$ а это больше половины от числа вершин.

4) Размыкаем синее рёбер в точке пересечения с красным, получаем две точки, соединим их какой-нибудь выпуклой красной кривой, поставим на ней пять точек и отметим "внутри"ещё две точки. Точки на кривой соединяем красными ребрами, а "внутрение"точки друг с другом синими. Осталось из внутренних провести два синих ребра, для этого соединим их точками с кривой.

Ответ:

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

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

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

Задача 2#68881Максимум баллов за задание: 7

На плоскости нарисовано несколько окружностей, причем каждая пара окружностей пересекается ровно в двух точках, и никакие три окружности не имеют общей точки. Круглосторонник - это часть плоскости, со всех сторон ограниченная дугами этих окружностей, граница которой состоит из каких-то дуг этих окружностей, причем между любыми двумя внутренними точками круглосторонника можно пройти, не пересекая ни одной дуги данных окружностей. Например, ниже изображены две окружности, образующие 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

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

Задача 3#81162Максимум баллов за задание: 7

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

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

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

Ответ:

$5$

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

Задача 4#81165Максимум баллов за задание: 7

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

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

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

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

Ответ:

$m + n$

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

Задача 5#81167Максимум баллов за задание: 7

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

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

Из условия следует, что в каждой вершине сходятся два шестиугольника и один пятиугольник. Построим граф, где вершинами будут вершины пятиугольников и шестиугольников, а рёбрами — их стороны. Пусть в полученном графе будет $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.$

Ответ:

$60$

Предыдущая подтема