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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Двадцать городов соединены 172 авиалиниями. Докажите, что, используя эти авиалинии, можно из любого города перелететь в любой другой (быть может, делая пересадки).

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

Подсказка 1:

Давайте пойдём от противного. Пусть из города A нельзя добраться в город B. Можно ли как-то оценить количество рёбер в графе, которые отсутствуют?

Подсказка 2:

Например, давайте рассмотрим произвольную вершину C. Что можно сказать про рёбра AC и BC? Какое количество рёбер точно отсутствует?

Показать доказательство

Предположим, что из города A нельзя попасть в город B. Пусть C – какой-то из оставшихся 18 городов. Тогда по крайней мере одна их двух авиалиний A–C, B–C отсутствует. Итого из $2 C20 = 190$ возможных авиалиний отсутствуют не менее 19 (считая линию A–B), то есть линий не больше 171. Противоречие.

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

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

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

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

В связном графе $n$ вершин и $2n− 1$ ребер. Докажите, что из этого графа можно выкинуть все ребра некоторого цикла так, чтобы он остался связным.

Показать доказательство

Выделим в графе остовное дерево. А теперь выкинем все рёбра, вошедшие в это дерево. Остался граф с $n$ вершинами и $n$ рёбрами. Количество рёбер больше, чем $n − 1,$ а значит граф связен и не является деревом. Таким образом, в графе есть цикл, его и удалим. При этом связность сохранена, потому что мы не трогали рёбра, образующие остовное дерево на изначальном графе. Что и требовалось.

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

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

В стране $15$ городов, некоторые из них соединены авиалиниями, принадлежащими трём авиакомпаниям. Известно, что даже если любая из авиакомпаний прекратит полеты, можно будет добраться из каждого города в любой другой (возможно, с пересадками), пользуясь рейсами оставшихся двух компаний. Какое наименьшее количество авиалиний может быть в стране?

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

Подсказка 1:

Мы знаем, что если выкинуть рёбра, соответствующие рейсам одной компании, граф остаётся связным. Но связность же накладывает некоторые ограничения на количество рёбер в графе.

Подсказка 2:

В связном графе на n вершинах есть хотя бы n - 1 ребро. Если обозначить количества рейсов компаний через a, b, c, то мы получим оценку на их попарные суммы. Осталось получить оценку на их сумму и придумать несложный пример.

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

Пусть первой компании принадлежит $a$ авиалиний, второй — $b,$ третьей — $c.$ По условию, если выкинуть $a$ рёбер первой авиакомпании, граф останется связным, то есть в нём будет хотя бы $14$ рёбер, откуда $b+c≥ 14.$ Аналогично получаем неравенства $a+ b≥ 14$ и $a+ c≥ 14.$ Если сложить эти неравенства и поделить полученное на $2,$ мы получим оценку $a+ b+c≥ 21.$ Ниже приведён пример на $21.$

$PIC$

Ответ:

$21$

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

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

В стране $300$ городов, некоторые пары городов соединены дорогами. Оказалось, что для любой четверки городов от любого города этой четверки можно добраться до любого другого города этой четверки, не проезжая через оставшиеся $296$ городов. При каком наибольшем $k$ в стране обязательно можно выбрать $k$ городов так, чтобы любые два выбранных города были соединены дорогой?

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

Подсказка 1

Сразу переведём все на язык графов. У нас есть условие на любую четверку вершин. Может ли тогда какая-то вершина иметь слишком мало смежных вершин?

Подсказка 2

Подумайте, в чём противоречие, если несмежных с ней вершин хотя бы 3)

Подсказка 3

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

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

Ясно, что степень каждой вершины хотя бы $297,$ иначе мы можем рассмотреть четв̈eрку, состоящую из вершины и три вершин, с которыми она не смежна. Очевидно, она не удовлетворит условию.

Теперь будем набирать вершины следующим образом: берём вершину, а те вершины (не более двух), с которыми она не соединена, мы не бер̈eм. Таким образом мы сможем набрать хотя бы $100$ вершин. Осталось предъявить пример, в котором $101$ вершину взять не получится. Например, можно рассмотреть полный стодольный граф (по $3$ вершины в каждой доле).

Ответ:

$100$

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

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

Каждая грань кубика разбита на $4$ квадрата. Некоторые стороны этих квадратов раскрасили в красный цвет — всего $26$ сторон. Докажите, что на поверхности кубика найдется замкнутая ломаная из красных отрезков.

Показать доказательство

Рассмотрим узлы, в которых соединяются стороны. Их всего $26.$ Посчитаем, сколько узлов являются концами красных сторон. Заметим, что при добавлении каждой следующей стороны, кроме первой, добавляется новый такой узел. Действительно, если нового узла не появилось, то мы дважды покрасили какую-то сторону.

Теперь рассмотрим граф, в котором вершины — узлы, а ребром вершины соединены, лишь когда соответствующие узлы соединены красной стороной. В этом графе $26$ вершин и $26$ рёбер. Значит, он точно является связным и при этом не деревом, потому что в дереве было бы $25$ рёбер. То есть в нём есть цикл, что и требовалось.

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

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

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

Показать доказательство

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

Курсы

Всё необходимое для достижения цели

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

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

В графе $n$ вершин и $nd 2$ рёбер $(d≥ 1).$ Докажите, что в нём можно выбрать множество из не менее чем $n- 2d$ вершин так, чтобы никакие две из них не были соединены ребром.

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

Подсказка 1

Давайте считать, что ребер не более nd/2, тогда и исходная задача будет решена. Для начала решите случай d=1. При нем задача имеет максимально понятное условие, поэтому ее приятнее всего решать. Как теперь свести всю задачу к этому случаю?

Подсказка 2

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

Показать доказательство

Будем решать чуть более общую задачу – пусть число ребер в графе не превосходит $nd. 2$ Рассмотрим отдельно случай $d= 1.$ Пусть в графе $n$ вершин и $n ≤ 2$ ребер. Пусть в нем также ровно $k$ изолированных вершин. Если $n k≥ 2,$ то задача уже решена. Выделим все изолированные вершины в отдельное независимое множество. Будем обозначать граф, из которого удалили все изолированные вершины, как $′ G .$ Если $n k < 2,$ то поскольку в $′ G$ $n n− k> 2$ вершин и $n ≤ 2$ ребер, в нем существует висячая вершина. Добавим ее в независимое множество, и удалим из графа ее соседа со всеми исходящими из него ребрами. Ясно, что после этого преобразования множество осталось независимым. После этого действия число вершин в графе $′ G$ сократилось на $2,$ а ребер – хотя бы на $1,$ поэтому разница между числом вершин и ребер сократилась не более чем на 1. Будем повторять эту операцию пока в графе $′ G$ вершин больше чем ребер. Ясно, что мы гарантированно сможем ее провести $n n n − k− 2 = 2 − k$ раз. В результате мы сформировали независимое множество размера хотя бы $n n k+ 2 − k= 2,$ что и требовалось.

Теперь перейдем к случаю произвольного $d >1.$ Оценим среднее количество ребер в подграфе на $⌈nd⌉$ вершин. Достаточно найти сумму количества ребер во всех таких подграфах и поделить на их количество: $n Cn⌈d⌉.$ А первое можно вычислить альтернативным способом: как сумму по всем ребрам числа подграфов размера $⌈nd⌉,$ его содержащих. Это число не превосходит $n nd2 ⋅C ⌈n−d⌉−22.$ Если ребро фиксировано, то чтобы дополнить его до подграфа размера $⌈nd⌉$ необходимо выбрать ровно $⌈nd⌉− 2$ среди оставшихся $n− 2.$ Итак,

n nd C⌈nd−⌉2−2 nd ⌈nd⌉(⌈nd⌉−-1)- (n-− 1)⌈nd⌉ 1 ⌈n ⌉ 2 ⋅ C⌈nd⌉ = 2 ⋅ n(n− 1) ≤ 2(n− 1) ≤ 2 ⋅ d n

Существует подграф размера $⌈nd⌉,$ в котором количество ребер не превосходит среднего, то есть $12 ⋅⌈nd⌉.$ Покажем, что в этом графе всегда можно выбрать хотя бы половину вершин так, чтобы они образовывали независимое множество. В базе мы доказали именно то, что в графе, в котором ребер хотя бы в два раза меньше чем вершин, всегда можно выбрать независимое множество размером хотя бы в половину от числа вершин. Осталось убедиться в том, что $2nd ≤ ⌈12 ⋅⌈nd⌉⌉.$

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

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

В связном графе $G$ даны два непересекающихся множества вершин $X$ и $Y,$ между этими множествами нет ни одного ребра. Пусть в графе $G − X$ ровно $m$ компонент связности, а в графе $G − Y$ ровно $n$ компонент связности. Какое наименьшее количество компонент связности может быть в графе $G− (X∪ Y)?$

Напомним, что для множества вершин $W$ через $G − W$ обозначается граф, полученный из $G$ в результате удаления всех вершин множества $W$ и всех выходящих из них ребер.

Источники: СПБГОР - 2023, 11.7 (см.pdmi.ras.ru)

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

Подсказка 1

Операцию G - W, не так удобно рассматривать в данной задаче, как операцию G\Е(это граф получающий удалением в G всех ребер, входящих в Е), где Е — множество рёбер, у которых хотя бы один конец лежит в W.
Тогда хочется сделать какую-нибудь оценку на количество компонент связи в графе G\(Eₓ∩Eᵧ), где Eₓ — множество ребер, у которых хотя бы один конец лежит в X, Eᵧ определяем аналогично.

Подсказка 2

Пусть количество компонент связанности в графе H = G\(E₁∩E₂) равно k, где G — связный граф, а E₁ и E₂ — два непересекающихся множества его рёбер. Пусть n₁ и n₂ — количество компонент связанности в G\E₁ и G\E₂ соответственно.
Что, если в H из E₂ добавить только те ребра, которые уменьшают число компонент связанности? Сколько их? А сколько для E₁?

Подсказка 3

Если добавить и те, и другие ребра из прошлой подсказки, то граф станет связным, тогда можно составить неравенство для k, n₁ и n₂, которое и даст оценку для k.

Подсказка 4

Теперь можно использовать полученную оценку для G, Eₓ и Eᵧ. Тогда, если обозначить vₓ и vᵧ как количество вершин множества X и Y соответственно, то можно точно выразить число компонент связанности G\Eₓ и G\Eᵧ. Тогда, после применения ранее полученной оценки, останется привести для неё пример.

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

Пример графа показан на рисунке. Множество $X$ содержит $m− 1$ вершину, множество $Y$ — $n− 1$ вершину.

$PIC$

_________________________________________________________________________________________________________________________________________________________________________________

Оценка. Для графа $G = (V,E)$ и некоторого множества его ребер $E′ ⊂ E$ через $G∖E′$ обозначим граф, получающийся из графа $G$ удалением всех его ребер, входящих в $E ′$ , т.е. граф $(V,E∖E′)$ .

_________________________________________________________________________________________________________________________________________________________________________________

Лемма. Пусть $G$ — связный граф, и пусть $E1$ и $E2$ — два непересекающихся множества его ребер. Обозначим через $ni$ ( $i= 1,2$ ) количество компонент связности графа $G ∖Ei$ . Тогда количество компонент связности графа $G ∖(E1∪ E2)$ не меньше, чем $n1+ n2− 1$ .

_________________________________________________________________________________________________________________________________________________________________________________

Доказательство. Пусть в графе $H = G∖(E1∪E2)$ ровно $k$ компонент связности. Если добавить к $H$ все ребра из множества $E2$ , то получится $n1$ компонент связности. Поэтому если мы будем последовательно добавлять в граф $H$ те ребра из $E2$ , которые уменьшают число компонент связности, то, добавив в точности $k− n1$ ребер из $E2$ , получим $n1$ компонент связности (поскольку добавление каждого ребра уменьшает число компонент связности не более, чем на 1). Добавление остальных ребер из $E2$ уже не уменьшит количество компонент связности. Аналогично к графу $H$ можно добавить такие $k − n2$ ребер из множества $E1$ , что в итоге получаются все $n2$ компонент связности графа $G∖E2$ . Но если к графу $H$ добавить и те, и другие ребра (в общей сложности $(k − n )+ (k− n ) 1 2$ ребер), то граф станет связным. Следовательно, $(k− n)+ (k− n )≥ k− 1 1 2$ и, значит, $k ≥n + n − 1 1 2$ .

_________________________________________________________________________________________________________________________________________________________________________________

Обозначим через $vX$ и $vY$ количества вершин в множествах $X$ и $Y$ . Пусть $EX$ — множество ребер, хотя бы один конец, который лежит в $X$ , а $EY$ — множество ребер, хотя бы один конец которых лежит в $Y$ . Поскольку между вершинами из $X$ и $Y$ нет ни одного ребра, множества $EX$ и $EY$ не пересекаются. Тогда в графе $G ∖EX$ ровно $vX +m$ компонент связности (среди них $vX$ компонент состоят из одной вершины), в графе $G∖EY$ ровно $vY + n$ компонент связности, а в графе $G ∖(EX ∩EY )$ ровно $k+ vX + vY$ компонент связности, где $k$ — число компонент связности в графе $G− X − Y$ . Тогда по лемме

k+ vX + vY ≥ (vX + m)+ (vY +n)+ 1,

следовательно, $k≥ m + n− 1$ .

Ответ:

$m + n− 1$

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

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

Ваня выложил из спичек клетчатый квадрат $10× 10.$ Он хочет убрать $n$ спичек так, чтобы муравей, оказавшись в любом месте этого «лабиринта», мог выбраться наружу. При каком наименьшем $n$ это возможно?

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

Рассмотрим квадрат как граф. Вершинами будут клетки, а также всё внешнее пространство будем считать за одну вершину. Тогда удаление спички равносильно проведению ребра между двумя вершинами. Следовательно, нам нужно провести минимально возможное количество рёбер так, чтобы граф стал связным. Как мы знаем, в связном графе количество рёбер не меньше, чем количество вершин, уменьшенное на один. Следовательно, в графе должно быть хотя бы $100$ рёбер. То есть $n ≥100.$

Приведём пример для $n = 100.$ Введём систему координат так же, как в прошлой задаче. Удалим рёбра, соединяющие вершины $(x,y)$ и $(x+ 1,y),y > 0.$ Также удалим рёбра, соединяющие вершины $(x,9)$ и $(x,10),x> 0.$

Ответ:

$100$

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

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

Есть $n$ камней разного веса. За одно взвешивание можно сравнить любые два камня между собой. За какое наименьшее число взвешиваний можно наверняка найти самый тяжелый?

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

Введём граф следующим образом: камни будут вершинами, вершины соединены ребром, если соответствующие камни сравнивались. Ясно, что для выявления самого тяжёлого камня граф должен быть связным. То есть количество рёбер должно быть не меньше $n − 1.$

Приведём пример на $n− 1$ взвешивание: возьмём любые два камня, сравним их. Далее возьмём другой камень и сравним с максимальным камнем с прошлого взвешивания. Снова возьмём новый камень и сравним с максимальным камнем с прошлого взвешивания и так дальше.

Ответ:

$n − 1$

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

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

Волейбольная сетка имеет вид прямоугольника размером $50×600$ клеток. Какое наибольшее число раз можно разрезать составляющие сетку верёвочки так, чтобы сетка не распалась на куски?

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

Рассмотрим граф с вершинами в узлах сетки и ребрами из веревки. Тогда после разрезаний у нас должен остаться связный граф, следовательно в нем хотя бы $51⋅601− 1$ ребро (количество вершин минус $1).$ Тогда разрезов не больше, чем

51⋅600+601⋅50− 51 ⋅601+ 1= 30000

Так разрезать очевидно можно, достаточно разрезать любое ребро, входящее в любой цикл, пока не останется связный граф без циклов, то есть дерево.

Ответ:

$30000$

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

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

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

Вася посмотрел на граф $G$ на $n$ вершинах и поставил на каждую вершину $v$ переменную $x . v$ После чего рассмотрел выражение

∑ xixj f (x1,...,xn)=2⋅(i,j)−-ребро--- n∑ x2i i=1

Пусть $m$ и $M$ — минимум и максимум $f.$

(a) Пусть степень каждой вершины в графе равна $d.$ Найдите $M.$

(b) Докажите, что вершины графа $G$ можно покрасить в $[M ]+1$ цвет, так что любые две соседние вершины получат разные цвета.

( ) Z = 1 1 −-1 , 2 w

где $w$ — максимальный размер множества вершин графа $G,$ попарно соединенных ребрами.

Источники: ЮМШ-2022, 11 класс, сюжет 1 (см. yumsh.ru)

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

Пункт а, подсказка 1

Нам нужно как-то оценить f. При этом в числителе мы видим сумму всех попарных произведений, а в знаменателе — сумму квадратов. Как можно связать квадраты и попарные произведения?

Пункт а, подсказка 2

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

Пункт а, подсказка 3

Внесём двойку под знак суммы. Получится, что числитель — это сумма всех возможных удвоенных произведений, каждое из которых не больше, чем сумма квадратов множителей. Оценим так каждое слагаемое. Сколько раз в итоговой сумме встретится квадрат каждого из чисел xᵢ?

Пункт а, подсказка 4

Столько же, сколько каждое из чисел xᵢ встречается во всевозможных попарных произведениях! Или столько же, сколько рёбер выходит из вершины xᵢ.

Пункт а, подсказка 5

Степень вершины равна количеству рёбер, выходящих из неё! Поэтому квадрат каждого числа в числителе встречается ровно d раз. Чему в таком случае равна вся дробь?

Пункт а, подсказка 6

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

Пункт b, подсказка 1

Подумаем, а что будет, если граф нельзя покрасить в [M]+1 цветов так, чтобы никакие две соседние вершины не были одноцветными?

Пункт b, подсказка 2

Это значит, что найдется такой подграф, степени всех вершин которого не меньше [M]+1. Например, это может быть полный подграф из [M]+1 вершине. Попробуйте как-нибудь использовать это при подсчёте f.

Пункт b, подсказка 3

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

Пункт b, подсказка 4

Верно, значение функции будет равно [M]+1. Постойте, а не противоречит ли это условию?

Пункт c, подсказка 1

Нам нужно доказать, что максимальное значение суммы всех попарных произведений равно определенному выражению. Утверждение не самое очевидное, поэтому попробуйте проверить, выполняется ли это на каком-нибудь простом графе.

Пункт c, подсказка 2

В задаче фигурирует клика — подмножество вершин графа, в котором любые 2 вершины соединены ребром. Будем рассматривать максимальную клику, ведь в ней как раз w вершин. Кажется, отделив вершины этой клики от остальных, гораздо проще придумать пример!

Пункт c, подсказка 3

В вершины максимальной клики поставим 1/w, а в остальные вершины — 0. Тогда искомое значение Z действительно достигается! Ура, мы доказали, что есть такие расстановки (по крайней мере одна) при которых утверждение задачи верно! Теперь попробуем доказать, что при изменении такой расстановки утверждение остаётся верным! Не забудьте учесть, что сумма всех чисел на вершинах равна 1.

Пункт c, подсказка 4

Обратите внимание на вершины, в которых стоит 0. Можно ли их просто убрать?

Пункт c, подсказка 5

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

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

(a)

Оценка. Занесём 2 в числитель и оценим каждое слагаемое следующим образом

2 2 2xixj ≤ xi +xj

Получим

∑ 2xixj ∑ (x2 +x2) (i,j)−-ребро---- ≤ (i,j)−-ребро-i---j- n∑ x2 ∑nx2 i=1 i i=1 i

Так как у каждой вершины степень у каждой вершины в графе равны $d,$ то каждая $2 xi$ в числителе встретиться ровно $d$ раз, следовательно

∑ 2 2 n∑ 2 ∑n 2 (i,j)− ребро(xi +xj) i=1dxi di=1xi -----∑n-2------= -n∑--2-= -n∑--2-= d i=1xi i=1xi i=1xi

Пример. Поставим во все вершины $1,$ получим

dn f(1,...,1)= n = d

(b) Предположим, что это не так, то есть граф так покрасить нельзя. Тогда по теореме Брукса найдётся подграф, в котором степени вершин хотя бы $[M ]+1.$ Поставим в вершины этого подграфа $1,$ а во все остальные вершины графа $0.$ Тогда значение выражения $f$ станет равным $[M ]+1> M,$ а это противоречит тому, что $M$ — максимум выражения $f.$

(c) Кликой графа называется подмножество его вершин, любые две из которых соединены ребром. Аналогично определяется антиклика

Пример. Найдём в графе максимальную клику, в его вершины поставим $1 w,$ а в остальные $0.$

Оценка.

( ) Z ≤ 1 1− 1- 2 w

Рассмотрим расстановку, на которой достигается $Z.$ Если там есть вершина с 0, удалим её. По предположение

( ) Z ≤ 1 1− -1 , 2 w

если максимальная антиклика не уменьшилась, и

1( 1 ) 1 ( 1) Z ≤ 2 1− w−-1 <2 1− w- ,

если максимальная антиклика уменьшилась. Таким образом сделаем все числа ненулевыми.

Обозначим $S(v)$ — сумму чисел в смежных с $v$ вершинах. Заметим, что если $a$ и $b$ — несмежные вершины и $S(a)< S(b),$ то можно заметить $(xa,xb)$ на $(0,xa+ xb).$ Общая сумма не измениться, а $Z$ увеличиться, противоречие. Следовательно, если $a$ и $b$ — несмежные вершины, то $S(a)=S (b).$

Рассмотрим антиграф, проверим два случая:

1) Если он связен. Значит, для любых вершин $a$ и $b$ $S(a)= S(b),$ обозначим это число за $S.$ Следовательно по предположению

1 1 1- 1- Z = 2S > 2(1− w)⇒ S > 1− w

Рассмотрим вершину $A$ максимальной антиклики.

1 S(A)> 1− w-

Следовательно, число в $A$ плюс в вершинах, не смешных с $A,$ меньше $1 w-.$ Просуммируем по врем вершинам максимальной антиклики. Мы посчитали каждое число неменее 1 раза, значит сумма всех меньше, чем $w⋅ 1-= 1 w$ . Противоречие, следовательно, такое невозможно.

2) Антиграф не связен.

Ответ:

(a) d

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

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

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

Показать доказательство

После закрытия одной дороги ровно 2 города А и В имеют степень вершины 99, а остальные - степень вершины 100.

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

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

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

Имеется $10$ различных гирь. За одно взвешивание на чашечных весах можно сравнить две гири. За какое наименьшее количество взвешиваний можно определить

(a) самую лёгкую гирю;

(b) одну из двух самых легких гирь?

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

Подсказка 1, пункт (a)

Рассмотрим граф взвешиваний. Какое минимальное число ребер в нем должно быть?

Подсказка 2, пункт (a)

Верно! Не меньше 9 ребер, а иначе граф несвязен, и информации не хватает! А как сравнить гири за 9 взвешиваний?

Подсказка 1, пункт (b)

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

Подсказка 2, пункт (b)

Верно! Потребуется как минимум 8 взвешиваний, чтобы показать, что гиря меньше 8 других. А как определить за 8 взвешиваний одну из двух легких гирь?

Подсказка 3, пункт (b)

Выбирая две гири, мы определим легкую из них. Тогда, выбрав еще одну гирю, нетрудно понять, какая будет самая легкая среди этих трех. Можно ли продолжить этот алгоритм?

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

(a) Оценка: Рассмотрим граф на $10$ вершинах, соответствующий гирям. Соединим две вершины, если соответствующие гири сравнивались на весах. Предположим, что граф несвязен и в нём есть хотя бы две компоненты связности. Это означает, что ни одна гиря из одной компоненты не сравнивалась ни с одной гирей из другой компоненты. Это означает, что мы не можем достоверно определить, какая самая лёгкая, потому что, например, мы можем уменьшить или увеличить все веса гирь в одной из долей и тогда вес наименьшей гири изменится. Значит граф связен, а тогда в нём имеется хотя бы $9$ рёбер.

Пример: возьмём две произвольные гири $x$ и $y,$ сравним их (пусть $x$ легче), далее возьмём гирю $z$ и сравним её с $x,$ если $x$ тяжелее, возьмём следующую гирю и сравним с $z,$ в противном случае будем сравнивать с $x$ и так дальше, то есть на каждом шаге берём самую лёгкую и сравниваем с какой-нибудь гирей, которую ещё не трогали.

(b) Для того, чтобы гиря была одной из двух самых лёгких, необходимо и достаточно, чтобы она была легче каких-то восьми других гирь. Из оценки прошлого пункта следует, что для того, чтобы доказать, что какая-то гиря легче восьми других, потребуется хотя бы $8$ взвешиваний.

Теперь приведём пример. Будем реализовывать алгоритм из примера в первом пункте до тех пор, пока на весах не побывают девять гирь. Нетрудно понять, что в этом алгоритме после $k$ -го взвешивания мы знаем, какая гиря самая лёгкая из $k$ гирь, побывавших на весах. Тогда через восемь взвешиваний мы получим гирю, которая легче каких-то восьми других, что и требовалось.

Ответ:

(a) $9$

(b) $8$

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

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

Тетрадный лист раскрасили в $23$ цвета по клеткам (при этом все цвета присутствуют). Пара цветов называется хорошей, если найдутся две соседние клетки, закрашенные этими цветами. Каково минимальное число хороших пар?

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

Подсказка 1

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

Подсказка 2

Верно! Граф, очевидно, связен, а потом и ребер не меньше 22! А на какой раскраске достигается такое число?

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

Рассмотрим граф на $23$ вершинах, в котором каждая вершина олицетворяет какой-то из $23$ цветов. Между вершинами проведено ребро, если пара из двух соответствующих цветов хорошая. Понятно, что, двигаясь по клеточкам на листке, мы сможем попасть из любой клетки в любую, но тогда рассмотренный граф цветов должен быть связным, а значит в нём должно быть хотя бы $22$ ребра.

Пример построить несложно: левая нижняя клетка $1$ -го цвета, её не покрашенные соседи — $2$ -го, не покрашенные соседи соседей $3$ -го и так дальше до $22$ цвета. Получили диагональную раскраску в $22$ цвета. Все остальные клетки покрасим в $23$ -й. В такой раскраске получается ровно $22$ пары. Каждая из сторон тетрадного листа содержит больше $23$ клеток, поэтому пример реализуется.

Ответ:

$22$

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

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

Определение. Граф $G$ называется $k$ -связным, если он имеет больше чем $k$ вершин и после удаления менее чем $k$ любых вершин граф остаётся связным.

Пусть $G$ — двусвязный граф, каждое ребро которого принадлежит ровно одному простому циклу. Тогда $G$ — простой цикл.

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

Подсказка 1

Рассмотрим произвольный цикл C этого графа и предположим, что он не совпадает со всем графом. Тогда есть ребро из вершины v цикла в вершину u не из цикла. Попробуем удалить вершину v. Что можно сказать про получившийся граф?

Подсказка 2

Верно! Он связен, так как исходный граф двусвязен. Тогда у вершины u есть путь в вершину t, которая связана ребром с удаленной вершиной v в исходном графе. Что теперь можно сказать про ребро vt?

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

Выделим какой-то цикл $C = v v ...v. 1 2 k$ Если это не весь граф, то из какой-то вершины цикла есть ещё одно ребро (пусть $v u 1$ ). Из двусвязности графа $G$ знаем, что в графе $G − v1$ есть путь $P$ из $u$ в $v2.$ Пусть $Q$ это часть пути $P$ от $u$ до первого пересечения $P$ с циклом $C.$ Тогда можно выделить два цикла, содержащих ребро $v1v2,$ что противоречит условию.

Ответ:

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

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

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

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

Докажите равносильность следующих условий:

(a) граф двусвязен;

(b) для любых двух вершин существует простой цикл, проходящий по ним;

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

Подсказка 1

Удаление k-1 вершины в k-связном графе не разрушает его связность. Какой вывод можно сделать для доказательства следствия из пункта (a) в пункт (b) по теореме Менгера?

Подсказка 2

В графе любые две вершины содержатся в простом цикле. Какой вывод из удаления одной из них для доказательства следствия из пункта (b) в пункт (a)?

Подсказка 3

Рассмотрим множество вершин-соседей некоторой вершины u и множество из двух вершин: концов некоторого ребра. Какой вывод можно сделать по теореме Геринга для доказательства следствия из пункта (a) в пункт (c)?

Подсказка 4

Для доказательства следствия из пункта (c) в пункт (a) попробуем использовать одно из уже проделанных доказательств, и выполнить аналогичное.

Показать доказательство

a $⇒$ b Между любыми двумя вершинами есть два непересекающихся пути по теореме Менгера.

b $⇒$ a При удалении любой вершины между любыми двумя оставшимися остался путь (одна из частей цикла), а значит граф двусвязен.

a $⇒$ c Пусть даны вершина $u$ и ребро $vw.$ Пусть $u1,u2,...,uk$ — соседи $u$ ( $k≥2,$ так как граф двусвязен). По теореме Геринга между множествами ${u1,u2,...,uk}$ и ${v,w}$ есть два непересекающихся пути. Следовательно, есть цикл через $u$ и ребро $vw.$

c $⇒$ a Аналогично b $⇒$ a.

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

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

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

(b) Верно ли, что в любом трёхсвязном графе есть цикл, содержащий любые три заданных ребра без общих концов?

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

Подсказка, пункт а

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

Подсказка 1, пункт б

Попробуйте нарисовать три ребра и сделать три непересекающихся пути из одного ребра в другое (для каждой пары ребер).

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

(a) Пусть это рёбра $uv$ и $xy.$ По теореме Геринга между множествами ${u,v}$ и ${x,y}$ есть два непересекающихся пути, которые и образуют вместе с рёбрами $uv$ и $xy$ искомый цикл.

(b) Нет. Легко видеть, что в графе на картинке ниже нет цикла, который содержит три отмеченных ребра, но он трехсвязный.

$PIC$

Ответ:

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

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

Пусть $G$ — двусвязный, но недвудольный граф.

(a) Докажите, что для любой вершины $a∈V (G )$ в $G$ есть нечетный цикл, проходящий через $a.$

(b) В $G$ никакие два нечетных цикла не имеют общего ребра. Докажите, что этот граф является простым нечетным циклом.

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

Подсказка 1, пункт а

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

Подсказка 2, пункт а

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

Подсказка, пункт б

Один нечетный цикл у нас точно есть. Пусть это не весь граф. Значит есть вершина вне этого цикла. Попробуйте вспомнить доказательство предыдущего пункта и получить противоречие с условием.

Показать доказательство

(a) В недвудольном графе существует цикл нечетной длины. Обозначим этот цикл за $C.$ Для вершин из этого цикла условие выполняется. Поэтому рассмотрим вершину $a,$ которая лежит вне этого цикла. По теореме Геринга и в силу того, что наш граф двусвязный получаем, что существует два непересекающихся пути из $a$ в $C.$ Обозначим вершины цикла $C$ за $c1,c2,...,c2k+1$ в порядке обхода. Пусть пути из $a$ в $C$ идут в вершины $ci$ и $cj,$ где $i<j.$ Тогда цикл $a,ci,ci+1,...,cj$ или цикл $a,cj,cj+1...ci$ будет нечётной длины.

(b) В недвудольном графе существует цикл нечетной длины. Пусть это не весь граф. Тогда есть вершина $a$ вне этого цикла. По доказательству из прошлого пункта мы знаем, что есть нечетный цикл, который содержит $a$ и при этом точно имеет общее ребро с этим нечетным циклом, но такого не может быть по условию.

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

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

В графе на 100 вершинах степень каждой вершины не больше 3. Докажите, что в нем можно выделить 25 вершин, попарно несоединенных ребрами.

Показать доказательство

Выберем наибольшее количество вершин, попарно несоединенных ребрами (наибольшую антиклику). Пусть их $k$ и это вершины $A1,...,Ak$ . Докажем, что их хотя бы $25$ . Пусть $k <25$ . Тогда из любой другой вершины $B$ в одну из этих $k$ вершин должно идти ребро, так как иначе среди $A1,...,Ak,B$ нет ребер, а $k$ мы выбирали максимальный. Значит из любой другой вершины, кроме $A1,...,Ak$ , есть ребро в $A1,...,Ak$ и поэтому количество ребер между $A1,...,Ak$ и остальными вершинами хотя бы $100 − k$ . С другой стороны, все ребра между $A1,...,Ak$ и остальными вершинами выходят из между $A1,...,Ak$ и остальными вершинами и значит всего ребер не больше $3k$ . Итого $100− k≤ 3k$ и $25≤k$ .

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

Следующая подтема