Леонард Эйлер (1707-1783) – швейцарец по происхождению – обрёл в России вторую родину. Он проработал в Петербургской академии наук более 30 лет. Исторически теория графов зародилась при решении Леонардом Эйлером головоломки о Кёнигсбергских мостах.

Река Прегель, протекающая через Кёнигсберг (Калининград), омывает два острова. Берега реки с островами были во времена Эйлера связаны мостами так, как показано на рисунке.

Задача Эйлера

Жители Кёнигсберга любили говорить, что никто не может осмотреть центр города, пройдя при этом по каждому из семи мостов лишь по одному разу, а начало и конец пути при этом должны совпадать. Эйлер начертил схематическую карту города, обозначив его четыре части, отделённые друг от друга водой, точками и буквами A, B, C, D и соединив их рёбрами – мостами.

Задача Эйлера

Пользуясь полученным графом, Эйлер доказал, что маршрута, который бы отвечал условиям задачи, не существует, и разработал теорию решения такого рода головоломок.

Эйлеровым путём в графе называется путь, содержащий все рёбра  графа. Иными словами, граф обладает эйлеровым путём, если его можно начертить, не отрывая карандаш от бумаги и не проводя дважды по одному и тому же ребру.

Эйлеровым циклом в графе называется цикл, содержащий все рёбра графа. Иными словами, если граф можно начертить не отрывая карандаш от бумаги и не проводя дважды по одному и тому же ребру, при этом начало и конец нашего пути совпадут, то граф обладает эйлеровым циклом.

1. Попробуй нарисовать графы не отрывая карандаш от бумаги, обводя каждое ребро в точности один раз.

Задача Эйлера

Какие графы нельзя нарисовать так, чтобы линия удовлетворяла условиям?

Какие графы получилось нарисовать, но начало и конец не совпадают?

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

Задача Эйлера

3. На реке 8 островов, которые соединены между собой мостами. Могут ли путешественники пройти по всем эти мостам? Могут ли они пройти по всем мостам и вернуться на тот остров, с которого они начнут свой маршрут?

a)

 

б)

Задача Эйлера

в)

Задача Эйлера

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

Задача Эйлера

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

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

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

Задача Эйлера

6. Придумана игра: шарик катится по дорожкам и закатывается в отверстия. На графе дорожки изображены рёбрами, а отверстия – вершинами графа. Может ли шарик прокатиться по всем дорожкам, но не более одного раза?

Задача Эйлера

Как, добавив одно ребро (одну дорожку в игре), сделать так, чтобы шарик мог прокатиться по всем дорожкам (при этом начало и конец пути не совпадают)?

Как, добавив два ребра, сделать так, чтобы шарик мог прокатиться по всем дорожкам (при этом начало и конец пути совпадают)?

7. Придумай для своего товарища фигуры (графы), которые он должен начертить , не отрывая карандаш от бумаги.

Добавить комментарий


Защитный код
Обновить

Участник Общероссийского рейтинга школьных сайтов

Новости

Команда "Апельсинки"
03 июнь 2017 12:30

Поздравляем команду "Апельсинки", ставшую победителем олимпиады [ ... ]

Читать далее
Ломоносовские чтения
12 фев 2017 12:44

11 февраля в нашей гимназии состоялся XII открытый конкурс [ ... ]

Читать далее
Деловая игра
18 дек 2016 19:12

16 декабря 2016 сборные команды наших семи- и восьмиклассников [ ... ]

Читать далее