Сборник задач по теме "Графы"
учебно-методический материал по математике

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

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

1. Между девятью планетами солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам: Земля – Меркурий; Плутон – Венера; Земля – Плутон; Плутон – Меркурий; Меркурий – Венера; Уран – Нептун; Нептун – Сатурн; Сатурн – Юпитер; Юпитер – Марс и Марс – Уран. Можно ли долететь на рейсовых ракетах с Земли до Марса?

Решение.

 Нарисуем схему: планетами будут соответствовать точки, а соединяющим их маршрутам – не пересекающиеся между собой линии.

 Теперь видно, что долететь от Земли до Марса нельзя.  

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

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

 Решение.

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

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

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

Решение.

100·4 : 2 = 200. 

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

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

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

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

Решение

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

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

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

Решение.

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

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

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

Решение.

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

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

7. Жила-была одна дружная семья: мама, папа и сын. Они все любили делать вместе. Но вот мультфильмы любили разные: «Ну, погоди!», «Покемоны», «Том и Джерри». Определите, какой мультфильм любит каждый из них, если мама, папа и любитель мультфильма «Покемоны» никогда не унывают, а папа и любитель мультфильма «Том и Джерри» делают зарядку по утрам?

 Решение.

 Если точке из одной группы соответствует точка из другой группы, будем соединять эти точки сплошной линией, если не соответствует – то штриховой. Заметим, что по условию задачи у человека только один любимый мультфильм. Учитывая данные задачи, получаем следующую схему.

Из условия задачи следует, что нужно найти единственно возможное соответствие между элементами двух групп.

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

Поэтому граф на рисунке будет выглядеть следующим образом  

Теперь мы установили, что папа любит мультфильм «Ну, погоди!», сын – «Покемоны». В обеих группах остается только по одной точке, следовательно, мама любит мультфильм «Том и Джерри». Задача решена.

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

Решение.

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

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

Решение.

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

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

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

Решение.

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

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

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

Ответ

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

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

Решение.

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

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

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

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

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

Решение.

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

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

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

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

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

Подсказка

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

Решение

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

14. 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 ничьих. 

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

Решение

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

База: произведение равно единице. Это эквивалентно тому, что на каждой стрелке написано число 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, разбирается аналогично.

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

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

Решение

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

17. Каждому городу в некоторой стране присвоен индивидуальный номер. Имеется список, в котором для каждой пары номеров указано, соединены города с данными номерами железной дорогой или нет. Оказалось, что, какие ни взять два номера M и N из списка, можно так перенумеровать города, что город с номером M получит номер N, но список по-прежнему будет верным. Верно ли, что, какие ни взять два номера M и N из списка, можно так перенумеровать города, что город с номером M получит номер N, город с номером N получит номер M, но список по-прежнему будет верным?

Решение.

  Рассмотрим страну из 12 городов, соединённых дорогами так, как показано на рисунке.

Заметим, что рисунок симметричен относительно каждого диаметра, проходящего через середины малых хорд окружности, на которой лежат все города. Этими симметриями мы можем поменять номерами любую пару соседних по кругу городов. А с помощью нескольких симметрий каждый номер можно перевести в любой другой, то есть условие выполнено. Предположим, что нам удалось поменять номерами города 1 и 3 с сохранением списка соседних городов. Тогда их единственный общий сосед 2 обязан сохранить свой номер. Оставшемуся соседу 9 города 2 тоже придётся сохранить номер. Но у городов 3 и 9 два общих соседа (2 и 8), а у 1 и 9 – только один. Противоречие.

Ответ. Неверно.

 18. В королевстве некоторые пары городов соединены железной дорогой. У короля есть полный список, в котором поименно перечислены все такие пары (каждый город имеет свое собственное имя). Оказалось, что для любой упорядоченной пары городов принц может переименовать все города так, чтобы первый город оказался названным именем второго города, а король не заметил бы изменений. Верно ли, что для любой пары городов принц может переименовать все города так, чтобы первый город оказался названным именем второго города, второй город оказался названным именем первого города, а король не заметил бы изменений?

Решение

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

 Рассмотрим такое переименование всех городов, при котором города B и D поменялись именами. Покажем, что в этом случае король заметит изменения. Действительно, если город A изменил свое название, то король заметит, что единственный город, который был соединен дорогой и с B, и с D, теперь называется иначе. Если же город A не изменил свое имя, то новый город C теперь не будет соединен и с городом A, и с новым городом B, ведь новый город B раньше был городом D, а городов, соединенных и с A, и с D, не было.

Ответ. Неверно.

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

Решение.

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

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

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

20. В классе учится 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 звонков.

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

Решение.

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

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

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

Решение.

Оценка. Из данного Объекта можно добраться за один "ход" до трёх Объектов, а с пересадкой – еще до  2·3 = 6  Объектов. Следовательно, объектов не больше 10.

Пример с 10 Объектами изображен на рисунке.  

Ответ. 10.

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

Решение.

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

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

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

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

Решение

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

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

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

Решение.

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

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