19.23 Графы: вершины, ребра
Ошибка.
Попробуйте повторить позже
В стране 100 городов, занумерованных от 1 до 100. Дума приняла закон, по
которому из каждого города с номером 
должно выходить количество дорог,
равное 
-ному простому числу. Можно ли выполнить такой закон?
Есть только одно четное простое число, а именно 2. Все остальные простые числа нечетны, поэтому при таком условии только из одного города выходит четное количество дорог, а из остальных 99 — нечетное. Итого получается нечетное количество городов, из которых выходит нечетное количество дорог, чего быть не может.
Ошибка.
Попробуйте повторить позже
В стране 96 городов, из которых 24 — «областные». Некоторые пары городов соединены между собой дорогами (но не более чем одной), причём любой путь по дорогам между двумя обычными городами, если он есть, проходит хотя бы через один «областной» город. Какое наибольшее количество дорог могло быть в этой стране?
Очевидно, что обычные города не соединены дорогами, иначе бы существовал путь не проходящий через областной город. Значит, максимальное число дорог в том случае, когда каждый обычный город соединен с каждым областным, и все областные соединены между собой. Нетрудно убедиться, что ответ в таком случае будет равен
Ошибка.
Попробуйте повторить позже
На спартакиаде проводились соревнования по пяти видам спорта. Каждый из 30 семиклассников принял участие в соревнованиях либо по одному, либо по трём видам спорта, а в каждом из видов число принимавших участие было 15 или 25. Докажите, что такого быть не могло.
Рассмотрим граф, в котором вершинами будут семиклассники и виды спорта, а ребра проведены от семиклассников к тем видам спорта, в которых они участвовали. Так как от каждого из 30 семиклассников выходит нечетное количество ребер, то всего ребер в графе четное количество. С другой стороны, если в каждом виде спорта также участвовало нечетное количество спортсменов, но видов спорта было 5. Поэтому количество ребер, выходящих от вершин-видов спорта нечетное количество. Итак, ребер в графе одновременно и четно, и нечетно, а такого быть не могло.
Ошибка.
Попробуйте повторить позже
Из полного графа на 100 вершинах выкинули 98 ребер. Мог ли получиться несвязный граф?
Предположим, что полученный граф оказался несвязным. Тогда его можно
мысленно разделить на два подграфа, между которыми нет ребер (ни одна
вершина первого подграфа не связана ни с какой вершиной второго подграфа).
Обозначим количество вершин в первом подграфе за 
Тогда было выкинуто по
крайней мере 
рёбер, соединявших вершины этого подграфа с
вершинами другого подграфа. Но
Противоречие. Значит, свзяный граф получиться не мог.
Ошибка.
Попробуйте повторить позже
Можно ли придумать пять таких слов, чтобы каждое имело хотя бы одну общую букву ровно с тремя другими?
Предположим, что удалось придумать пять таких слов. Обозначим слова вершинами и соединим ребром те вершины, соответствующие слова которых имеют общую букву. Тогда должен получиться граф с 5 вершинами, степень каждой из которых равна 3. Но тогда суммарная степень всех вершин графа равна 15, то есть нечетна, чего не может быть.
