Сборник задач по теме «Графы» (с решениями)

Графы – замечательные математические объекты, с их помощью можно решать много различных, внешне не похожих друг на друга задач.

1 В стране Цифра есть 9 городов с названиями 1, 2, 3, 4, 5, 6, 7, 8, 9. Путешественник обнаружил, что два города соединены авиалинией в том и только в том случае, если двузначное число, составленное из цифр-названий этих городов, делится на 3. Можно ли добраться из города 1 в город 9?

Решение.

Ни из какого города-цифры, не кратной 3, нельзя долететь в город-цифру, кратную 3.

Ответ. Нельзя.

2. В государстве 100 городов, и из каждого из них выходит 4 дороги. Сколько всего дорог в государстве?

Решение.

100·4 : 2 = 200.

Ответ.200 дорог.

3. Докажите, что в любом графе

а) сумма степеней всех вершин равна удвоенному числу рёбер (и следовательно, чётна);

б) число вершин нечётной степени чётно.

Решение

а) При сложении степеней вершин каждое ребро учитывается дважды: по разу для каждой из вершин, которые оно соединяет.

б) Сразу следует из а) и того очевидного факта, что сумма нечётного числа нечётных чисел нечётна.

4. В классе 30 человек. Может ли быть так, что 9 из них имеют по 3 друга (в этом классе), 11 – по 4 друга, а 10 – по 5 друзей?

Решение.

В соответствующем графе было бы 30 вершин, 9 из которых имели бы степень 3, 11 – степень 4, 10 – степень 5. Однако у такого графа 19 нечётных вершин, что противоречит задаче (см. задачу 4)

Ответ. Не может.

5. В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы было 4 телефона, каждый из которых соединен с тремя другими, 8 телефонов, каждый из которых соединен с шестью, и 3 телефона, каждый из которых соединен с пятью другими?

Решение.

В соответствующем графе было бы 7 нечётных вершин, что противоречит задаче (см. задачу 4)

Ответ. Нельзя.

6. Докажите, что в дереве есть вершина, из которой выходит ровно одно ребро (такая вершина называется висячей).

Решение.

Рассмотрим произвольную вершину дерева и пойдем по любому выходящему из нее ребру в другую вершину. Если из новой вершины больше ребер не выходит, то мы остаёмся в ней, а в противном случае идём по любому другому ребру дальше. В этом путешествии мы никогда не сможем попасть в вершину, в которой уже побывали: это означало бы наличие цикла. Так как у графа конечное число вершин, то наше путешествие когда-нибудь закончится. Но закончиться оно может только в висячей вершине!

7. Докажите, что при удалении любого ребра из дерева оно превращается в несвязный граф.

Решение.

Предположим, что концы удалённого ребра в новом графе соединены простым путем. Тогда этот путь вместе с удалённым ребром образует в исходном графе цикл.

8. а) Дан кусок проволоки длиной 120 см. Можно ли, не ломая проволоки, изготовить каркас куба с ребром 10 см?

б) Какое наименьшее число раз придется ломать проволоку, чтобы всё же изготовить требуемый каркас?

Решение.

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

б) Поскольку нечётных вершин восемь, то таких кусков нужно не менее четырёх.

Четырёх кусков достаточно: например, в кубе ABCDA'B'C'D' проволоку по ломаной ABCDAA'B'C'D'A'. Оставшиеся три ребра BB', CC', DD' покроем тремя отдельными кусками проволоки.

Ответ

а) Нельзя; б) три раза.

9. Грани некоторого многогранника раскрашены в два цвета так, что соседние грани имеют разные цвета. Известно, что все грани, кроме одной, имеют число рёбер, кратное 3. Доказать, что и эта одна грань имеет кратное 3 число рёбер.

Решение.

Общее число рёбер многогранника равно общему числу рёбер белых граней и общему числу рёбер чёрных граней. Одна из этих сумм (а значит, и вторая) кратна 3. Во второй все слагаемые, кроме одного, кратны 3. Значит, и это слагаемое кратно 3.

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

Доказать, что их можно разбить на пары, в каждой из которых имеется общий язык.

б) То же для группы из 100 человек.

в) То же для группы из 102 человек.

Решение.

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

Первый способ. Если в тройке (A, B, C) проведены рёбра AB и AC, то рёбер BD и CD нет. Но тогда в тройке (B, C, D) не больше одного ребра. Противоречие.

Второй способ. Всего есть 4 тройки. Каждое ребро входит в две тройки. Следовательно, рёбер не менее 4·2 : 2 = 4. С другой стороны, каждому ребру соответствует отсутствующее "противоположное" ребро. Следовательно, рёбер не более трёх. Противоречие.

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

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

Подсказка

Выразите количество троек попарно знакомых людей через количество пар знакомых.

Решение

Обозначим через Р количество пар знакомых людей (то есть число рёбер в соответствующем графе), а через Т – количество треугольников в этом графе. По условию каждое из рёбер входит ровно в 5 треугольников. С другой стороны, в каждый из Т треугольников содержит ровно 3 ребра. Следовательно, 5Р = 3Т. Поскольку 3 и 5 – взаимно простые числа, Р делится на 3.

12. 12 шахматистов сыграли турнир в один круг. Потом каждый из них написал 12 списков. В первом только он, в (k+1)-м – те, кто были в k-м и те, у кого они выиграли. Оказалось, что у каждого шахматиста 12-й список отличается от 11-го. Сколько было ничьих?

Решение.

Рассмотрим ориентированный граф, вершины которого – шахматисты, а стрелки ведут от выигравшего к проигравшему. Условие означает, что для каждого шахматиста есть другой, до которого можно добраться только по 11 стрелкам (это, в частности означает, что от каждого шахматиста можно добраться до любого другого). Рассмотрим такой путь: A1 выиграл у A2, A2 – у A3, ..., A11 – у A12. Заметим, что Ai (1 < i < 12) не мог выиграть у A1 (иначе от A2 можно было бы добраться до каждого не более чем по 10 стрелкам). Но кто-то у A1 выиграл (иначе до A1 вообще нельзя было бы добраться), значит, это – A12. Как и выше, показываем, что в полученном цикле каждый мог выиграть только у следующего.

Следовательно, результативных партий всего 12, а ничьих – 12·11 : 2 – 12 = 54.

Ответ. 54 ничьих.

13. Дано несколько белых и несколько чёрных точек. Из каждой белой точки идет стрелка в каждую чёрную, на каждой стрелке написано натуральное число. Известно, что если пройти по любому замкнутому маршруту, то произведение чисел на стрелках, идущих по направлению движения, равно произведению чисел на стрелках, идущих против направления движения. Обязательно ли тогда можно поставить в каждой точке натуральное число так, чтобы число на каждой стрелке равнялось произведению чисел на ее концах?

Решение

Проведём индукцию по произведению чисел на всех ребрах.

База: произведение равно единице. Это эквивалентно тому, что на каждой стрелке написано число 1. Тогда можно поставить и в каждой точке число 1.

Шаг индукции. Пусть произведение равно n> 1, и для всех меньших произведений утверждение уже доказано. Возьмём произвольный простой делитель n, обозначим его через p. Ясно, что p делит число на какой-то стрелке из точки A в точку B.

Докажем, что числа на всех стрелках, выходящих из A, делятся на p, или числа на всех стрелках, входящих в B, делятся на p. Пусть это не так. Тогда есть стрелка из A в C, число на которой не кратно p, и стрелка из D в B, число на которой не кратно p. Пройдём по замкнутому маршруту A → B → D → C → A. По условию, произведение чисел на стрелках AB и DC равно произведению чисел на стрелках DB и AC. Но первое из произведений кратно p, а второе – не кратно. Противоречие.

Пусть все числа на всех стрелках из A кратны p. Поделим их все на p. Заметим, что расстановка чисел на стрелках все еще удовлетворяет условию. Действительно, в каждом замкнутом маршруте, проходящем через A ровно k раз, произведение чисел на стрелках по направлению движения и произведение чисел на стрелках против направления движения уменьшились ровно в pk раз. Так как произведение чисел на стрелках при этой операции уменьшилось, можно воспользоваться предположением индукции и должным образом расставить числа в точках. После этого увеличим число в точке A в p раз. Получившаяся расстановка чисел решает исходную задачу.

Случай, в котором числа на всех стрелках в B кратны p, разбирается аналогично.

Ответ. Обязательно.

14. В стране Мера расположено несколько замков. Из каждого замка ведут три дороги. Из какого-то замка выехал рыцарь. Странствуя по дорогам, он из каждого замка, стоящего на его пути, поворачивает либо направо, либо налево по отношению к дороге, по которой приехал. Рыцарь никогда не сворачивает в ту сторону, в которую он свернул перед этим. Доказать, что когда-нибудь он вернётся в исходный замок.

Решение

Все замки страны Мера связаны каким-то конечным числом дорог. Если рыцарь странствует по стране достаточно долго, то он проедет достаточно много дорог, поэтому хотя бы по одной дороге AB (A и B – замки) он проедет не менее пяти раз. При этом не менее трёх раз он проедет по этой дороге в одном и том же направлении (скажем, от A к B); поэтому, если из замка B, кроме BA, ведут еще две дороги BC и BD то рыцарь минимум дважды, – скажем, после i-го и после j-го посещения замка B, где j > i, – сворачивал, выезжая из B (куда он оба раза приезжал из A) в одну и ту же сторону, скажем, в сторону замка C. Но из условия тогда следует, что не только в i-е и в j-е посещение B рыцарь приехал в B из одного замка – из A, – но и в A он оба раза приезжал из одного и того же замка P (ведь если рыцарь после B свернул на дорогу BC, например, налево, то в A он должен был свернуть направо после посещения P). Аналогично этому устанавливается, что полностью совпадают пути рыцаря, предшествующие двум рассматриваемым посещениям замка B: в замок P он оба раза попал из одного и того же замка, и т. д. Но тогда, если рыцарь до i-го посещения B миновал, начиная с выезда из своего замка X, какое-то число k замков, то и за k замков до j-го посещения B он снова был в X, что и доказывает утверждение задачи.

15. Между зажимами A и B включено несколько сопротивлений. Каждое сопротивление имеет входной и выходной зажимы. Какое наименьшее число сопротивлений необходимо иметь и какова может быть схема их соединения, чтобы при порче любых девяти сопротивлений цепь оставалась соединяющей зажимы A и B, но не было короткого замыкания? (Порча сопротивления: короткое замыкание или обрыв.)

Решение.

Оценка. Рассмотрим граф, вершинами которого являются зажимы, а рёбрами – сопротивления. Заметим, что между вершинами A и B не может быть пути, состоящего менее чем из 9 рёбер (иначе при коротком замыкании всех рёбер этого пути у нас получалось бы короткое замыкание цепи). Кроме того, для любых 9 рёбер существует путь из A в B, не проходящий через эти рёбра. Следовательно, по теореме Менгера, существует не менее 10 попарно не пересекающихся (по рёбрам) путей из A в B. Так как в каждом из этих путей не менее 10 рёбер, то всего рёбер не менее 100.

Пример цепи со 100 сопротивлениями — это 10 попарно непересекающихся путей длины 10 из вершины A в вершину B.

Ответ.100 сопротивлений.

16. В классе учится 15 мальчиков и 15 девочек. В день 8 Марта некоторые мальчики позвонили некоторым девочкам и поздравили их с праздником (никакой мальчик не звонил одной и той же девочке дважды). Оказалось, что детей можно единственным образом разбить на 15 пар так, чтобы в каждой паре оказались мальчик с девочкой, которой он звонил. Какое наибольшее число звонков могло быть сделано?

Решение.

Обозначим мальчиков M1, M2, ..., M15, а девочек – D1, D2, ..., D15 так, чтобы M1-D1, M2-D2, ..., M15-D15 было единственным разбиением на пары из условия задачи. Предположим, что каждый мальчик позвонил хотя бы двум девочкам. Нарисуем стрелку от каждой девочки Di к мальчику Mi, с которым она находится в паре, а от каждого мальчика Mi – к другой (отличной от Di) девочке, которой он звонил. Тогда от каждого ребёнка ведёт по стрелке. Если мы будем двигаться по стрелкам (начав от произвольной девочки), то рано или поздно мы попадём к девочке, которая уже встречалась в строящейся цепочке. Таким образом, в соответствующем графе есть цикл. Объединим в этом цикле каждого мальчика с девочкой, к которой от него ведет стрелка; остальные пары оставим без изменения. Мы получили другое разбиение на пары, что противоречит условию.

Следовательно, найдётся мальчик, который звонил ровно одной девочке. Если отбросить эту пару, число звонков уменьшится не больше, чем на 15 – максимальное возможное количество звонков этой девочке. После этого снова найдется мальчик, сделавший ровно один звонок одной из оставшихся девочек. Отбросив эту пару, уменьшим количество звонков не более, чем на 14, и т. д. Итого, было сделано не более 15 + 14 + ... + 2 + 1 = 120 звонков.

Ровно 120 звонков получается, например, если каждой девочке Di звонили мальчики M1, M2, ..., Mi.

Ответ.120 звонков.

17. Докажите, что среди любых шести человек есть либо трое попарно знакомых, либо трое попарно незнакомых.

Решение.

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

Источники и прецеденты использования

18. За круглым столом сидят несколько гостей. Некоторые из них знакомы между собой; знакомство взаимно. Все знакомые каждого гостя (считая его самого) сидят вокруг стола через равные промежутки. (Для другого человека эти промежутки могут быть другими.) Известно, что каждые двое имеют хотя бы одного общего знакомого. Докажите, что все гости знакомы друг с другом.

Решение.

Заметим, что если у человека есть знакомые, сидящие рядом друг с другом (в частности, если он знаком со своим соседом), то этот человек знаком со всеми. Докажем, что такой гость найдётся.

Пусть A и B – двое соседей. Если они не знакомы между собой, то их общий знакомый C знаком со всеми, так как его знакомые сидят без промежутков. В противном случае со всеми знаком человек A (по той же причине).

Итак, пусть X – гость, знакомый со всеми. Тогда его соседи тоже знакомы со всеми, так как они знакомы с X (являющимся для них соседом). Соседи этих соседей также знакомы со всеми, и так далее по кругу.

19. В классе больше 32, но меньше 40 человек. Каждый мальчик дружит с тремя девочками, а каждая девочка – с пятью мальчиками. Сколько человек в классе?

Решение

Количество рёбер в соответствующем графе в три раза больше числа мальчиков и в 5 раз больше числа девочек. Следовательно, число девочек относится к числу мальчиков как 3 : 5, а общее число учеников делится на 8. Но между 32 и 40 таких чисел нет.

Ответ. Такого класса не существует.

20. Можно ли провести в городе 10 автобусных маршрутов и установить на них остановки так, что какие бы 8 маршрутов ни были взяты, найдётся остановка, не лежащая ни на одном из них, а любые 9 маршрутов проходят через все остановки.

Решение.

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

Ответ. Можно.