Граф Дракулы
Семь графических задач на математику и сообразительность
Граф — это множество точек, которые называются вершинами, соединенные кривыми, которые называются ребрами. Теория графов — важный раздел математики, который сочетает в себе сразу несколько замечательных качеств. Во-первых, это наглядность: задачи на графы понимает даже школьник младших классов. Во-вторых, широкий простор для приложений — от теории кодирования до логистики. Последнее, то есть логистика, — именно то, что интересно нашему партнеру, компании Бандеролька, вместе с которой мы сделали этот тест. Бандеролька занимается доставкой товаров из-за рубежа, поэтому знакома с логистическими сложностями не понаслышке. Наслаждайтесь!
1. Художник-абстракционист хочет раскрасить картину в два цвета так, чтобы в любых двух прилегающих областях были разные цвета. Сможет ли он это сделать?
2. Художник-абстракционист непонятно зачем хочет раскрасить вершины графа в два цвета так, чтобы никакие два цвета не были соединены ребром. Сможет ли он это сделать?
3. Это знаменитый граф кенигсбергских мостов. В XVIII веке бытовало поверие: тому, кто, гуляя по городу, перейдет каждый мост один раз, улыбнется удача. Великий русский математик Леонард Эйлер доказал, что этого сделать нельзя. Пусть у вас есть возможность закрывать мосты для пешеходов. Сколько минимум надо закрыть мостов, чтобы такой обход стал возможен?
4. Перед вами логотип легендарного производителя гитар и звукоусилителей Fender. Можно ли написать вторую часть логотипа (которая ender), одним росчерком, то есть не отрывая руки и не проходя ни по одной линии дважды?
5. Перед вами карта городов на острове Мкадо. Вершины здесь — это города, а ребра — дороги. Сейчас, чтобы попасть из города М в любой другой город, надо проехать по нескольким дорогам — от 1 до 4. Сколько еще надо построить дорог на Мкадо, чтобы путь из М в любой другой город занимал не больше двух дорог?
6. Перед вами карта городов на острове Пентамино. Вершины здесь — это города, а ребра — дороги. В пересечении дорог в центре на самом деле стоит мост, поэтому никакого перекрестка там нет, движение по ним идет независимо. Какое максимальное число дорог можно закрыть, чтобы из одного города Пентамино все еще можно было доехать до любого другого, двигаясь только по дорогам.
7. Мы снова на острове Пентамино, где губернатор-вредитель хочет закрыть дороги так, чтобы транспортная сеть острова распалась на части — так, чтобы из одной части нельзя было проехать в другую, двигаясь только по дорогам. При этом, разумеется, губернатор скуп, поэтому хочет закрыть минимальное число дорог. Помоги губернатору устроить транспортный коллапс, ответь, сколько дорог минимум надо закрыть?
Нашли опечатку? Выделите фрагмент и нажмите Ctrl+Enter.
