Леонард Эйлер (1707-1783) – швейцарец по происхождению – обрёл в России вторую родину. Он проработал в Петербургской академии наук более 30 лет. Исторически теория графов зародилась при решении Леонардом Эйлером головоломки о Кёнигсбергских мостах.
Река Прегель, протекающая через Кёнигсберг (Калининград), омывает два острова. Берега реки с островами были во времена Эйлера связаны мостами так, как показано на рисунке.
Жители Кёнигсберга любили говорить, что никто не может осмотреть центр города, пройдя при этом по каждому из семи мостов лишь по одному разу, а начало и конец пути при этом должны совпадать. Эйлер начертил схематическую карту города, обозначив его четыре части, отделённые друг от друга водой, точками и буквами A, B, C, D и соединив их рёбрами – мостами.
Пользуясь полученным графом, Эйлер доказал, что маршрута, который бы отвечал условиям задачи, не существует, и разработал теорию решения такого рода головоломок.
Эйлеровым путём в графе называется путь, содержащий все рёбра графа. Иными словами, граф обладает эйлеровым путём, если его можно начертить, не отрывая карандаш от бумаги и не проводя дважды по одному и тому же ребру.
Эйлеровым циклом в графе называется цикл, содержащий все рёбра графа. Иными словами, если граф можно начертить не отрывая карандаш от бумаги и не проводя дважды по одному и тому же ребру, при этом начало и конец нашего пути совпадут, то граф обладает эйлеровым циклом.
1. Попробуй нарисовать графы не отрывая карандаш от бумаги, обводя каждое ребро в точности один раз.
Какие графы нельзя нарисовать так, чтобы линия удовлетворяла условиям?
Какие графы получилось нарисовать, но начало и конец не совпадают?
2. На озере семь островов, которые соединены между собой мостами. На какой остров катер должэен доставить путешественников, чтобы они могли пройти по каждому мосту и только один раз? С какого острова катер должен снять этих людей?
3. На реке 8 островов, которые соединены между собой мостами. Могут ли путешественники пройти по всем эти мостам? Могут ли они пройти по всем мостам и вернуться на тот остров, с которого они начнут свой маршрут?
a)
б)
в)
4. Инженер разработал проект соединения островов мостами. Могут ли путешественники пройти все мосты и вернуться на остров, с которого начали путь?
Как, убрав всего один мост, сделать так, чтобы путешественники прошли по всем мостам и вернулись на остров, с которого начали свой путь?
Как, добавив два моста, сделать так, чтобы путешественники прошли по всем мостам и вернулись на остров, с которого начали путь?
5. На рисунке изображена схема зоопарка (вершины графа – вход, выход, перекрестки, повороты, тупики; рёбра – дорожки, вдоль которых расположены клетки). Найдите маршрут, по которому экскурсовод мог бы провести посетителей, показав им всех зверей и не проходя более одного раза ни одного участка пути.
6. Придумана игра: шарик катится по дорожкам и закатывается в отверстия. На графе дорожки изображены рёбрами, а отверстия – вершинами графа. Может ли шарик прокатиться по всем дорожкам, но не более одного раза?
Как, добавив одно ребро (одну дорожку в игре), сделать так, чтобы шарик мог прокатиться по всем дорожкам (при этом начало и конец пути не совпадают)?
Как, добавив два ребра, сделать так, чтобы шарик мог прокатиться по всем дорожкам (при этом начало и конец пути совпадают)?
7. Придумай для своего товарища фигуры (графы), которые он должен начертить , не отрывая карандаш от бумаги.
