Сборник материалов выездных школ команды Москвы на Всероссийскую математическую олимпиаду
 Скачать 3.42 Mb.
|
|
кроме вершин. Обязательно ли найдутся хотя бы два треугольника разбиения, примыкающие к сторонам многоугольника двумя сторонами? г) Докажите, что в любой компании из шести человек найдутся либо трое попарно знакомых, либо трое попарно незнакомых. д)* Город N состоит из нескольких площадей (кругов, соединенных непересекающимися дорогами (прямолинейными отрезками. Известно, что существует замкнутый маршрут, проходящий по каждой дороге ровно один раз (этот маршрут может проходить по площадям несколько раз. Докажите, что существует несамопересекающийся маршрут, проходящий по каждой дороге ровно один раз. (Иными словами, в любом нарисованном на плоскости без самопересечений эйлеровом графе существует эйлеров цикл, аппроксимируемый вложениями.) Графом без петель и кратных ребер называется набор точек, некоторые пары которых соединены линиями, причем одна пара вершин не может быть соединена более чем одной линией. Точки называются вершинами графа, а линии — ребрами. Линии могут не быть отрезками. Им разрешается пересекаться, но точки пересечения не считаются, т. е. не являются вершинами Простейшие понятия теории графов 291 Распространенным примером графа без петель и кратных ребер является граф знакомств. Вершины этого графа соответствуют людям, и две вершины соединены ребром, если соответствующие два человека знакомы между собой. В задаче 1 а) можно рассмотреть граф, вершины которого соответствуют городам, а ребра — авиалиниям. Графом с петлями и кратными ребрами, называется набор точек, среди которых некоторые пары (возможно совпадающих) вершин соединены линиями. Ребра, соединяющие вершину саму с собой, называются петлями, а несколько ребер, соединяющих одну и туже пару вершин кратными ребрами. Количества вершин и ребер (с учетом кратности и включая петли) обозначаются V и E соответственно. Везде в задачах, где не оговорено обратное, графом называется граф без петель и кратных ребер. Степенью вершины графа называется число выходящих из нее ребер. При этом считается, что петля выходит из вершины дважды. Степени вершина) В любом графе найдутся две вершины одинаковой степени. б) Сумма степеней вершин в любом графе четна и равна в) При каких E и V существует граф с V вершинами и E ребрами, каждая вершина которого имеет степень 3? Такие графы называют кубичными или правильными степени Путем в графе называется последовательность вершин, в которой любые две соседние вершины соединены ребром. Циклом называется путь, в котором первая и последняя вершины совпадают. Путь (цикл) называется несамопересекающимся, если он проходит по каждой своей вершине только один раз. Длиной пути (цикла) называется количество ребер, вдоль которых он проходит. Граф называется связным, если любые две его вершины можно соединить путем. Граф называется деревом, если он связен и не содержит несамопересекающихся циклов. Деревья. а) В любом дереве, отличном от точки, найдется вершина степени 1 (даже две). б) В любом дереве V − E = в) В дереве любые две вершины соединены ровно одним несамопе- ресекающимся путем. г) В любом связном графе G существует максимальное дерево, или остов, те. дерево, содержащее все вершины графа G. Это дерево может быть не единственно. Дадим несколько определений, которые будут использоваться далее Гл. 12. Миникурс по теории графов Граф называется полным, если любые две его вершины соединены ребром. Раскраска вершин графа в несколько цветов называется правильной, если любые две вершины, соединенные ребром, окрашены в разные цвета. Цикл (путь) называется эйлеровым, если он проходит через каждое ребро графа ровно по одному разу. Граф называется эйлеровым, если в нем есть эйлеров цикл. Цикл (путь) называется гамильтоновым, если он проходит через каждую вершину графа ровно по одному разу. Граф называется га- мильтоновым, если в нем есть гамильтонов цикл. Ориентированный граф — граф, каждое ребро которого является стрелкой от одной вершины ребра к другой. Путь в ориентированном графе — такая последовательность вершин, что в каждую следующую вершину ведет стрелка из предыдущей. Замечание. Дадим строгое определение графа (хотя при решении задач можно пользоваться нестрогим, данным ранее. Графом без петель и кратных ребер называется конечное множество, некоторые двухэлементные подмножества (те. неупорядоченные пары несовпадающих элементов) которого выделены. Элементы данного множества называются вершинами. Выделенные пары вершин называются ребрами. Приданном определении каждое ребро соединяет различные вершины (нет петель, и любые две вершины соединены не более чем одним ребром (нет кратных ребер). Графом с петлями и кратными ребрами, или просто графом, называется конечное множество V , в котором выделены некоторые неупорядоченные пары (возможно совпадающих) элементов, и каждой выделенной паре приписано натуральное число — кратность этой пары. При работе с графами удобно пользоваться их изображениями. Вершины изображаются точками (например, на плоскости или в пространстве. Каждое ребро, соответствующее паре различных элементов изображается ломаной (или кривой, соединяющей соответствующие точки. Каждое ребро, соответствующее паре (A, A) изображается замкнутой ломаной (или кривой, соединяющей эту вершину A саму с собой. На изображении ломаные могут пересекаться, но точки пересечения (кроме двух концов ребра) не являются вершинами. Для простоты будем рассматривать только те рисунки, на которых ребра изображаются ломаными (а непроизвольными кривыми. Важно, что граф (в строгом определении) и его изображение — не одно и то же. Зачетные задачи все, кроме любых двух пунктов задачи 1. Пути в графах 293 Пути в графах (ДА. Пермяков класс Для решения задач этого раздела нужно понять, как устроен граф при наложенных на него условиях ив частности, как устроены пути в этом графе. Вам понадобится только знание основных определений теории графов, которые можно изучить в разделе Простейшие понятия теории графов. Докажите, что вершины графа можно правильно покрасить в два цвета тогда и только тогда, когда в нем нет циклов нечетной длины. Такие графы называются двудольными. В графе есть цикл нечетной длины. Докажите, что в нем есть несамопересекающийся цикл нечетной длины. В графе между любыми двумя вершинами существует несамопе- ресекающийся путь четной длины. Докажите, что между любыми двумя вершинами существует несамопересекающийся путь нечетной длины. В графе есть простой цикл, проходящий через ребра a и b, и есть простой цикл, проходящий через ребра b и c. Докажите, что есть простой цикл, проходящий через ребра a и c. 5. Вершины A и B не связаны ребром. При удалении любой другой вершины найдется путь между A и B. Докажите, что в исходном графе между A и B найдутся два пути, пересекающиеся только по концевым вершинам. В группе из нескольких человек некоторые люди знакомы друг с другом, а некоторые — нет. Каждый вечер один из них устраивает ужин для всех своих знакомых и знакомит их друг с другом. После того как каждый человек устроил хотя бы один ужин, оказалось, что какие-то два человека все еще незнакомы. Докажите, что наследующем ужине им познакомиться тоже не удастся. Эйлеровы графы. а) Докажите, что в связном графе есть эй- леров цикл тогда и только тогда, когда степень каждой его вершины четна. б) При каком условии в графе существует эйлеров путь? в) При каком условии в ориентированном графе существует эйлеров цикл? г) Рассеянный математик забыл трехзначный код своего замка. Замок открывается, если три цифры кода набраны подряд (даже если Гл. 12. Миникурс по теории графов перед этим были набраны другие цифры. Математик набирает одну цифру в секунду. Докажите, что математик сможет открыть замок за) 29 секунд, если в коде использованы только цифры 1, 3 и 7; 2) 1002 секунды, если в коде использованы все десять цифр. Зачетные задачи все, кроме любых 4 пунктов класс. Турист, приехавший в Москву на поезде, весь день бродил по городу. Поужинав в кафе на одной из площадей, он решил вернуться на вокзал, и при этом идти только по улицам, по которым он проходил до этого нечетное число раз. Докажите, что он сможет это сделать. В некотором обществе любые два знакомых не имеют общих знакомых, а любые два незнакомых имеют ровно двух общих знакомых. Докажите, что в этом обществе все имеют одинаковое число знакомых. Дан граф, степень любой вершины которого не меньше k, где k > 2. Докажите, что в этом графе найдется простой цикл длины не меньшей, чем k + 1. 11. Все ребра связного графа раскрашены в 2 цвета. Из каждой вершины выходит поровну ребер обоих цветов. Докажите, что из любой вершины до любой другой можно добраться, каждый раз меняя цвет ребра. Диаметр связного графа — наибольшее из расстояний 1) между его вершинами. Пусть в связном графе диаметра d минимальная длина цикла 2d + 1. Докажите, что степени всех вершин равны. Дан связный граф, который при удалении любого своего ребра остается связным. Двое игроков по очереди ставят стрелки на ребрах. Проигрывает игрок, после хода которого от какой-то вершины нельзя добраться до какой-нибудь другой, двигаясь только по направлению стрелок и по ребрам без стрелок. Докажите, что при правильной игре обоих соперников партия закончится вничью. Зачетные задачи все, кроме любой одной класс Для решения основной задачи этого раздела потребуются некоторые навыки работы с графами. Перед этой серией задач полезно (ноне обязательно) прорешать две предыдущие. 1) Расстояние между двумя вершинами — длина кратчайшего пути, соединяющего эти вершины Пути в графах 295 Турнир — ориентированный граф, между любыми двумя вершинами которого есть ровно одно ребро. Ориентированный граф называется сильносвязным, если от любой его вершины можно добраться до любой другой, двигаясь по направлению стрелок на ребрах (основная. Какое минимальное количество несамопересекаю- щихся циклов длины k может быть в сильносвязном турнире с n вершинами Данная задача является сложной, к ней не так просто подступиться. Обычно при решении сложной задачи бывает полезно рассмотреть частные случаи, попытаться решить близкие задачи. Это позволяет заметить закономерности, которые можно сформулировать в виде гипотез и затем доказать. Мы не будем подсказывать эти гипотезы, а предлагаем вам самим исследовать эту задачу и высказывать ваши предположения, б, в, г, . . . Сформулируйте и докажите какую-нибудь лемму, которая, по вашему мнению, поможет в решении задачи После того как вы попробовали найти путь к решению самостоятельно, мы предлагаем вам доказать следующие утверждения. Они могут оказаться полезными в решении задачи 14 и, возможно, помогут довести решение до конца. Докажите, что турнир является сильносвязным тогда и только тогда, когда в нем есть несамопересекающийся цикл, идущий по направлениям стрелок на ребрах и проходящий по всем вершинам графа. Докажите, что в сильносвязном турнире через любую вершину проходит несамопересекающийся цикл (идущий по направлениям стрелок на ребрах) любой длины от трех до количества вершин турнира. Решения 2. Рассмотрим любую вершину, по которой цикл проходит хотя бы дважды. Можно рассмотреть две части цикла между первыми вторым прохождениями этой вершины и оставшуюся. Каждая из этих частей является циклом, и одна из них имеет нечетную длину. Уменьшая так длину нечетного цикла, получим циклу которого нет точек самопересечения. Обозначим через и вершины ребра c, через T ab — простой цикл, проходящий через ребра a и b, а через T bc — простой цикл, проходящий через ребра b и c. Пойдем из вершины по циклу T bc не по ребру c. Первое пересечение с циклом T ab обозначим через C ′ 1 . Аналогично найдем вершину C ′ 2 . Искомый цикл будет состоять из части цикла Гл. 12. Миникурс по теории графов от до C ′ 2 , содержащей a, пути от до C 2 , ребра c и пути от до C ′ 1 8. Назовем четными те улицы, по которым турист на пути к кафе прошел четное число раз, остальные — нечетными. На пути к кафе турист с вокзала выходил на один раз больше, чем возвращался, значит, по выходящим с вокзала улицам он проходил в сумме нечетное число раз. Следовательно, с вокзала выходит нечетное число нечетных улиц. Аналогично из кафе выходит тоже нечетное число нечетных улица из любой другой площади — четное число нечетных улиц. Пусть турист идет из кафе по нечетным улицам как угодно, но проходя каждую улицу не более одного раза. Когда он входит на площадь, отличную от вокзальной, остается еще нечетное число неиспользованных нечетных улиц, выходящих с этой площади. Значит, он всегда сможет с нее выйти. Поэтому в тот момент, когда туристу будет некуда идти, он уже будет находиться на вокзале. Рассмотрим человека A с максимальным числом знакомых Пусть его знакомые — это B 1 , B 2 , . . . , B n . У каждой пары B i и B j есть общий знакомый A, значит, B i и B j незнакомы между собой. У и B i (i = 2, 3, . . . , n) есть общий знакомый C i , отличный от A. Если C i и C j для некоторых i 6= j — один и тот же человек, то у C i и A есть общие знакомые B 1 , B i и B j , что невозможно по условию. Значит, уесть хотя бы n знакомых A, C 2 , C 3 , . . . , C n . В силу максимальности числа n у ровно n знакомых. Аналогично у всех B i , i = 2, 3, . . . , n, ровно по n знакомых, откуда, в свою очередь, у всех знакомых с B i также по n знакомых. Каждый человек знаком либо с A, либо с кем-нибудь из значит, у всех в обществе ровно по n знакомых. Теория Рамсея (ДА. Пермяков Данный раздел посвящен классической задаче по оценке чисел Рам- сея (задачи 8 и 11). Хотя эти оценки известны давно, точные значения известны только для нескольких первых чисел Рамсея. Для изучения этого раздела понадобится только знание определения графа. Докажите, что среди пяти человек может не найтись ни трех попарно знакомых, ни трех попарно незнакомых. Среди любых шести человек найдется либо трое попарно знакомых, либо трое попарно незнакомых. Среди любых десяти человек найдется либо четверо попарно знакомых, либо трое попарно незнакомых Теория Рамсея 297 4. Среди любых девяти человек найдется либо четверо попарно знакомых, либо трое попарно незнакомых. Среди любых 20 человек найдется либо 4 попарно знакомых, либо попарно незнакомых. Обозначим через r(m, n) минимальное такое число, что среди любых r(m, n) человек найдется либо m попарно знакомых, либо n попарно незнакомых. Числа r(m, n) называются числами Рамсея. 6. a) Найдите r(3, 3). б) Найдите r(4, 3). 7. Докажите, что r(m, n) 6 r(m − 1, n) + r(m, n − 1). 8. Докажите, что r(m, n) 6 C m m+n 9. На плоскости отметили 17 точек и соединили каждые 2 из них цветным отрезком красным, желтым или зеленым. Докажите, что найдутся точки в вершинах одноцветного треугольника. Обозначим через r(m 1 , . . . , m k ) минимальное такое число, что если полный граф с r(m 1 , . . . , m k ) вершинами раскрашен в k цветов, то для некоторого i найдется m вершин, попарно соединенных ребрами цвета. Докажите, что r(m 1 , m 2 , . . . , m k ) 6 r(m 1 − 1, m 2 , . . . , m k )+ + r(m 1 , m 2 − 1, . . . , m k ) + . . . + r(m 1 , m 2 , . . . , m k − 1). 11. Найдите оценку на r(m 1 , m 2 , ..., m k ), аналогичную задаче Зачетные задачи 1, Решения. Рассмотрим произвольного человека. Пусть у него есть хотя бы знакомых. Если среди них есть пара знакомых между собой, то они вместе с рассмотренным человеком образуют тройку попарно знакомых. Иначе они сами образуют тройку попарно незнакомых. Пусть теперь у рассмотренного человека среди оставшихся 5 человек нет трех знакомых. Тогда у него найдется 3 незнакомых. Если среди них есть пара незнакомых между собой, то они вместе с рассмотренным человеком образуют тройку попарно незнакомых. Иначе они сами образуют тройку попарно знакомых Гл. 12. Миникурс по теории графов. Рассмотрим произвольного человека. У него найдется либо 6 знакомых, либо 4 незнакомых. Пусть найдется 4 незнакомых. Если среди них есть пара незнакомых между собой, то они вместе с рассмотренным человеком образуют тройку попарно незнакомых. Иначе они сами образуют четверку попарно знакомых. Пусть теперь у рассмотренного человека найдется 6 знакомых. Согласно задаче 1, среди них найдется либо трое попарно незнакомых, либо трое попарно знакомых, образующих с рассмотренным человеком четверку попарно знакомых. Если у некоторого человека найдется 6 знакомых или 4 незнакомых, то мы найдем нужную группу людей аналогично задаче 2. Единственный плохой случай, когда у всех девяти человек ровно по 5 знакомых. Тогда количество пар знакомых людей равняется · 5 2 = 22,5, т. е. не целое число, что невозможно. Литература [1] Гарднер М. Рамсеевская теория графов // Квант. 1988. № Раскраски графов (ДА. Пермяков Данный раздел посвящен исследованию, в какое наименьшее количество цветов можно правильно раскрасить вершины различных графов. Для решения задач этого раздела полезно иметь некоторые навыки работы с графами, например, полезно прорешать задачи раздела Пути в графах класс Напомним, что раскраска графа (те. раскраска всех вершин графа) называется правильной, если любые две вершины, соединенные ребром, окрашены в разный цвета) В графе степени всех вершин не превосходят d. Докажите, что его можно правильно раскрасить в d + 1 цвет. б) В связном графе степени всех вершин не превосходят d и есть вершина степени меньше d. Докажите, что его можно правильно раскрасить в d цветов. в) В связном графе степени всех вершин не превосходят d и есть вершина, после удаления которой граф перестает быть связным. Докажите, что исходный граф можно правильно раскрасить в d цветов Раскраски графов 2. Вершины некоторого графа нельзя правильным образом раскрасить в менее, чем k цветов. Докажите, что для любой правильной раскраски вершин этого графа в k цветов существует путь, в котором встречается ровно по одной вершине каждого цвета. В ориентированном графе из каждой вершины выходит небо- лее d ребер. Докажите, что его вершины можно правильно раскрасить в 2d + 1 цвет. В графе максимальный несамопересекающийся путь проходит через l вершин. Докажите, что граф можно правильно раскрасить в l цветов. Зачетные задачи все, кроме любого одного пункта класс. В графе максимальный нечетный простой цикл имеет длину Докажите, что граф можно правильно раскрасить в l + 1 цвета) В связном графе степень каждой вершины не превосходит Его можно правильно раскрасить в 3 цвета, чтобы для некоторой вершины среди ее соседей не встречалось хотя бы двух цветов. Добавили одну вершину и выходящие из нее ребра так, что по-прежнему степени всех вершин не превосходят 3. Докажите, что полученный граф можно правильно раскрасить в 3 цвета. б) В связном графе степень каждой вершины не превосходит 3. Его можно правильно раскрасить в 3 цвета, но при любой правильной раскраске у каждой вершины найдется соседняя вершина каждого из двух оставшихся цветов. Добавили одну вершину и выходящие из нее ребра так, что по-прежнему степени всех вершин не превосходят 3 и полученный граф отличен от полного четырехвершинника (графа с 4 вершинами. Докажите, что полученный граф можно правильно раскрасить в 3 цвета. в) Теорема Брукса. В графе степень каждой вершины не превосходит и нет полного подграфа с d + 1 вершиной. Докажите, что его можно правильно раскрасить в d цветов. Степень любой вершины графа не превосходит d. Натуральные числа d 1 , . . . , d таковы, что d 1 + d 2 + . . . + d k = d + 1 − k. Докажите, что вершины можно так разбить на k групп, что любая вершина й группы соединена не более, чем с d вершинами своей группы. В выпуклом многоугольнике провели несколько диагоналей, не пересекающихся между собой во внутренних точках. Докажите, что полученный плоский граф можно правильно раскрасить в 3 цвета Гл. 12. Миникурс по теории графов. Трем смышленым девочкам Ире, Тане и Юле выдали по копии одного итого же графа. Юля и Таня раскрасили свои графы правильно, те. так покрасили все вершины, что концы каждого ребра — разного цвета. Юля использовала меньше цветов, чем Таня, зато у Тани в каждый цвет покрашены минимум две вершины. Докажите, что Ира может правильно раскрасить свой граф так, чтобы использовать цветов не больше, чему Юлии покрасить в каждый цвет не меньше двух вершин. Зачетные задачи все, кроме 5 или Решения. а) Будем красить вершины как попало ив произвольном порядке. На цвет каждой очередной вершины имеется не более d запретов, поэтому мы сможем ее окрасить. б) Докажем индукцией по количеству вершин. Удалим из графа вершину степени меньше d со всеми выходящими из нее ребрами. Оставшийся граф можно правильно раскрасить по предположению индукции. Вернем удаленную вершину. На ее цвет меньше, чем d запретов, поэтому мы сможем ее окрасить. Все вершины цвета k − 1, не соединенные ребром с цветом перекрасим в цвет k. После этого все вершины цвета k − 2, которые можно, перекрасим в цвет k − 1. Аналогично перекрасим вершины цветов. Согласно условию, в полученной раскраске найдется вершина цвета 1. Мы ее не перекрасили, значит, есть соседняя с ней вершина цвета 2. Мы не перекрасили вершину цвета 2, значит, есть соседняя с ней вершина цвета 3. Аналогично найдутся такие вершины цветов 4, . . . , k, что каждая следующая соседствует с предыдущей. Эти вершины имели те же цвета в исходной раскраске графа (до перекра- шиваний) в силу правильности исходной раскраски. Значит, мы нашли требуемый путь. Сразу следует из задачи Подсчеты в графах (ДА. Пермяков Данный раздел содержит задачи, для решения которых ненужно изучать устройство графа, а нужно посчитать количество некоторых объектов в нем ребер, треугольников, определенных вершин и т. п. Для решения этих задач потребуется только знание определения графа. Но Подсчеты в графах 301 если задачи вызовут затруднения, можно сначала прорешать раздел «Теория Рамсея», содержащий более простые задачи по близкой теме. Часть задач этого раздела взята из окружных олимпиад разных лет. Назовем человека малообщительным, если у него менее 10 знакомых. Назовем человека чудаком, если все его знакомые малообщительны. Докажите, что количество чудаков не больше количества малообщительных. На вечеринку пришли 10 человек. Затем те, у кого не было знакомых среди пришедших, ушли. Затем те, у кого был ровно 1 знакомый среди оставшихся, тоже ушли. Затем аналогично поступали те, у кого было ровно 2, 3, 4, . . . , 9 знакомых среди оставшихся к моменту их ухода. Какое наибольшее число людей могло остаться в конце вечеринки. В круговом турнире участвовало 2007 команд и не было ничьих. Найдите максимальное возможное количество троек команд, что первая команда выиграла у второй, вторая у третьей, а третья у первой. В каждой из трех школ учится по n человек. Любой ученик имеет в сумме ровно n + 1 знакомых учеников из двух других школ. Докажите, что можно выбрать по одному ученику из каждой школы так, чтобы все трое выбранных учеников были знакомы друг с другом. а) В графе для любых двух смежных вершин есть ровно одна вершина, смежная сними обеими. Может ли в этом графе быть ровно ребер? б) В графе для любых двух смежных вершин есть две вершины, смежные сними обеими. Может ли в этом графе быть ровно 100 ребер. В графе 2007 вершин и степень каждой вершины является степенью двойки. Володя посчитал для каждой вершины количество выходящих из нее путей, проходящих по не более чем двум ребрам, а затем просуммировал полученные результаты по всем вершинам. У него получилось. Докажите, что Володя ошибся. На предприятии трудятся 50 000 человек. Для каждого из них сумма количества его непосредственных начальников и его непосредственных подчиненных равна 7. В понедельник каждый работник предприятия издает приказ и выдает копию этого приказа каждому своему непосредственному подчиненному (если такие есть. Далее, каждый день работник берет все полученные им в предыдущие дни приказы и либо раздает их копии всем своим непосредственным подчиненным, либо, если таковых у него нет, выполняет приказы сам. Оказалось, что в пятницу никакие бумаги по предприятию не передаются. Докажите, что на предприятии не менее 97 начальников, над которыми нет начальников Гл. 12. Миникурс по теории графов Зачетные задачи все пункты, кроме любых двух. Решения 1. Малообщительных, не являющихся чудаками, будем называть «просто малообщительными, а чудаков, не являющихся малообщительными просто чудаками. Малообщительные чудаки не могут быть знакомы с просто чудаками, значит, просто чудаки знакомы только с просто малообщительными. Каждый просто чудак знаком с хотя бы 10 просто малообщительными, а каждый малообщительный не более чем с 9 просто чудаками. Пусть между просто чудаками и просто малообщительными всего n знакомств. Тогда просто чудаков не более n 10 , а просто малообщительных не менее n 9 . Получаем, что просто чудаков не больше, чем просто малообщительных, а значит, всего чудаков не больше, чем всего малообщительных. Нетрудно проверить, что если все пришедшие, кроме двух человек и B, были знакомы между собой, тов конце должны остаться все, кроме A и B, те человек. Докажем, что не могло остаться 9 человек. Ясно, что человек A, имевший изначально меньше всего знакомых (в некоторый момент уйдет. Если больше никто не ушел, то все остальные (кроме A) имели больше k знакомых до ухода A и меньше k + после его ухода. Но тогда A должен быть знаком со всеми остальными, т. е. k = 9, что противоречит строгой минимальности Задачи по комбинаторной теории графов (А. Б. Скопенков Данный раздел посвящен некоторым классическим задачами теоремам комбинаторной теории графов. Компоненты связности. а) В некотором царстве имеется столица, город Дальний и несколько других городов. Некоторые пары городов соединены дорогами (дороги могут пересекаться. Из столицы выходит 21 дорога, из города Дальнего — 1 дорога, а из остальных городов по 20 дорог. Обязательно ли из столицы можно проехать в Дальний |