2.4 Графы Эйлера

№14

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

Ответ. а) Можно. б) Нельзя. Рисуя граф в каждую вершину, за исключением начальной и конечной, мы войдём столько же раз, сколько выйдем из неё. Поэтому степени всех вершин должны быть чётными.

Рисунок 2.10

№15

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

Решение.а) на Троекратный турист 3 раза зашёл и 3 раза из него вышел, то есть использовал 6 мостов, б) в этом случае турист зашел на остров дважды, а вышел трижды, в) 4.

№16

Хулиган Вася решил прогуляться по парку и его окрестностям (см. рис. 2.11), так, чтобы при этом перелезть через каждый забор ровно один раз. Сможет ли он это сделать?

Ответ. Нет.

Рисунок 2.11

№17

а) Дан кусок проволоки длиной 120 см. Можно ли, не ломая проволоки, изготовить каркас куба ребром 10 см? б) Какое наименьшее число раз придётся ломать проволоку, чтобы изготовить требуемый каркас? в) Жук ползёт по рёбрам куба. Сможет ли он последовательно обойти все 12 рёбер куба, не пройдя дважды по одному ребру?

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

№18

На рис. 2.12 -- план подвала из 10 комнат. Можно ли пройти через все двери всех комнат, запирая каждый раз ту дверь, через которую Вы проходите? С какой комнаты надо начинать движение?

Решение. Можно, так как есть лишь две комнаты с нечётным числом дверей -- 8 и 10, с одной из которых и надо начинать.

Рисунок 2.12

№19

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

Решение. Ровно один город должен быть пересадочным, а так как в связном графе с 50 вершинами рёбер не меньше 49, то 49 -- наименьшее число авиалиний.

№20

Можно ли составить решётку на рис. 2.13 а) из пяти ломаных длины 8; б) из восьми ломаных длины 5? (Длины сторон клеток равны 1.)

Ответ. а) Нельзя. Никакие две ломаные не должны иметь общих отрезков. Поэтому 12 узлов решётки, расположенных на границе квадрата и отличных от его вершины, должны быть концами ломаных, а у 5 ломаных всего 10 концов. б) Можно.

Рисунок 2.13

№21

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

Доказательство. Граф связен, степени его вершин чётны.

№22

Можно ли, не отрывая карандаш от бумаги и не проводя по одной линии дважды, нарисовать: а) квадрат с диагоналями; б) правильный пятиугольник с диагоналями?

Ответ. а) Нельзя. б) Можно.

№23

Турист обошёл 6 улиц одного города, пройдя каждую ровно 2 раза, но не смог обойти их, пройдя каждую по одному разу. Могли ли так быть, если а) улицы могут оканчиваться тупиком; б) конец каждой улицы -- перекрёсток?

Ответ. а) Да. Например, все улицы прямые и выходят из одной точки. б) Да. Например, 3 улицы образуют правильный треугольник, и ещё 3 улицы соединяют центр треугольника с его вершинами (теорема Эйлера).

№24

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

Решение. Не смогут. Допустим, что это возможно. Пусть на шоссе nгородов, тогда всего 2n-1 дорог. Поскольку дороги одной компании соединяют все города в связное множество, то этих дорог не меньше n. Тогда дорог двух компаний не меньше 2n. Противоречие.