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

ЗАДАЧА 3.

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

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

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

Решение.

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

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

ЗАДАЧА 4.

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

Решение.

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

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

ЗАДАЧА 7.

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

Решение.

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

ЗАДАЧА 8.

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

Решение.

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

ЗАДАЧА 10.

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

Подсказка

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

Решение.

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