РЕШЕНИЕ ЗАДАЧ С ПОМОЩЬЮ ГРАФОВ

ЗАДАЧА 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 нечётных вершин, что противоречит задаче.

Ответ: не может.

 ЗАДАЧА 5.

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

Решение.

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

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

ЗАДАЧА 6.

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

Решение.

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

ЗАДАЧА 7.

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

Решение.

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

ЗАДАЧА 8.

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

Решение.

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

ЗАДАЧА 9.

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

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

Решение.

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

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

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

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

ЗАДАЧА 10.

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

Подсказка

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

Решение.

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