logo
Elektr_prak_po_DM

3.3.2.6. Решите следующие задачи по обходу графов:

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

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

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

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

  5. Пешеход обошёл шесть улиц одного города, пройдя каждую ровно два раза, но не смог обойти их, пройдя каждую лишь раз. Могло ли это быть?

  6. В центре куба 333 сидит жук. Доказать, что он, переползая через ребра, не сможет обойти все кубики 111по одному разу.

  7. В квадрате 6×6 отмечают несколько клеток так, что из любой отмеченной можно пройти в любую другую отмеченную, переходя только через общие стороны отмеченных клеток. Отмеченную клетку называют концевой, если она граничит по стороне ровно с одной отмеченной. Отметьте несколько клеток так, чтобы получилось а) 10, б) 11, в) 12 клеток.

  8. В одной из вершин а) октаэдра б) куба сидит муха. Может ли она проползти по всем его ребрам ровно по одному разу и возвратиться в исходную вершину? (Примечание: октаэдр представляет собой две четырехугольные пирамиды, склеенные по основаниям.)

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

  10. Можно ли провести в каждом квадратике на поверхности кубика Рубика диагональ так, чтобы получился несамопересекающийся путь? Указание: на поверхности кубика Рубика всего 54 квадрата.