Так можно ли обойти все Кенигсбергские мосты, проходя только один раз через каждый из этих мостов?

  Первые попытки выполнения задания.

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

Построение  модели.

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

  Изображение 1.

Элемент памяти триггер — это логическое устройство, способное хранить 1 бит информации.

  Изображение 2.

  Изображение 3. 

  Изображение железных дорог.

Изображение 4.  Схема движения городского транспорта г. Ухта.

Изображение 5.  Сетевой  график строительства.

Изображение 6. 

Карта звездного неба.

НЕ нашли? Не то? Что вы ищете?

  Изображение 7.  Генеалогического дерева знаменитого дворянского рода .

Каждый ученик записывает свое определение графа.

  Далее работая в группах, учащиеся из различных источников информации (книги на информационном столе, информационно-телекоммуникационная сеть «Интернет») находят определения графа, сравнивают их и выбирают на их взгляд наиболее точное.  Используя полученную теоретическую информацию о графах, учащиеся  составляют «конспект». Каждая группа демонстрирует свой «конспект» через документ - камеру, а представитель группы комментирует результат работы, ребята из других групп дополняют при необходимости свои конспекты.

Пример «конспекта».

Графы – фигуры (или схемы), состоящие из множества точек, называемых

вершинами, и связывающих эти точки отрезков прямых и дуг, называемыми реб-

рами графа.

Количество рёбер, выходящих из вершины графа, называется степенью вершины. Вершина графа, имеющая нечётную степень, называется нечетной, а чётную степень – чётной.

Нечетные вершины: D,

Четные вершины:A, B,C, E,G, H,I.

Графы имеют свойства. Если граф можно нарисовать одним росчерком, т, е,

пройти его весь непрерывным движением, проходя по каждой ветви один и толь-

ко один раз (одним маршрутом)- граф называется уникурсальным (или эйлеро-

вым). Уникурсальный от латинского слова «unus» – один, «cursus» – путь.

Если возможен обход всей сети одним маршрутом, то она называется уни-

курсальной сетью, а маршрут – уникурсальным обходом.

Условия существования уникурсального обхода, обоснованные Эйлером и

названные им правилами, очень просты:

1.Сеть, не имеющая нечетных узлов, допускает замкнутый уникурсальный

обход с началом в любой точке сети.

2.Сеть, имеющая два и только два нечетных узла, обходится уникурсально,

если начать движение с одного нечетного узла и закончить его в другом.

3.Сеть, имеющая больше двух нечетных узлов, нельзя полностью обойти

одним маршрутом – сеть не уникурсальна.

Изучив необходимый теоретический материал, учащиеся придумывают геометрическую модель задачи о Кенигсбергских моста.

На модели земельные участки, разъединенные рукавами реки, точки А, В,

С, D - вершины (узлы), а мосты как бы вытянуты в линии a, b, c, d, e, f, g – ветви (или ребра), соединяющими два последовательных узла.

Решение построенной модели.

Из данной геометрической модели мостов  видно, что сеть имеет 4 узла, в каждом сходится не-

четное число ребер (линий) – все узлы нечетные. Следовательно, по правилу 3 сеть не уникурсальна. Требуемого маршрута прогулки по 7 мостам города Кенигсберга не существует.

Продолжая работать в группах, учащиеся из различных источников информации (книги на информационном столе, информационно-телекоммуникационная сеть «Интернет») находят другие логические задачи, которые так же можно решить, используя свойства графов. Выбранные задачи ребята решают и наиболее интересными обмениваются.

Задачи:

В некоторой местности через протоки переброшено 15 мостов.

Можно ли обойти все мосты, пройдя по каждому из них только один раз?

У вас на индивидуальных карточках изображен план подземелья, в одной из комнат которого скрыты богатства рыцаря. Чтобы безопасно проникнуть в эту комнату, надо, войти через определенные ворота в одну из крайних комнат подземелья, пройти последовательно через все 29 дверей, выключая сигнализацию тревоги. Проходить дважды через одни и те же двери нельзя. Определить номер комнаты в которой скрыты сокровища и ворота через которые нужно войти?

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

 

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

Можно ли фигуру, изображенную на рисунке, нарисовать одним росчерком, без повторения линий?

   

Аркадий, Борис. Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Сколько всего рукопожатий было сделано? В государстве 100 городов, из каждого выходит 2 дороги, кроме столицы, откуда выходит 5 дорог и города Горный, откуда выходит одна единственная дорога. Сколько всего дорог в государстве? Доказать, что в государстве из предыдущей задачи  можно из столицы доехать (как-нибудь, возможно, с несколькими пересадками в разных городах), до города Горный. Между девятью планетами солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам: Земля – Меркурий; Плутон – Венера; Земля – Плутон; Плутон – Меркурий; Меркурий – Вене; Уран – Нептун; Нептун – Сатурн; Сатурн – Юпитер; Юпитер – Марс и Марс – Уран. Можно ли долететь на рейсовых ракетах с Земли до Марса? На остров Коневец завезли 13 телефонов. Настоятель хочет организовать такую схему телефонной связи, чтобы соединить каждый телефон ровно с 7-ю другими. Удастся ли ему это? Насыщенным углеводородом называется соединение углевода С, имеющего валентность 4, и водорода Н, имеющего валентность 1, в котором при заданном числе атомов углерода содержится наибольшее число атомов водорода. Найдите формулу насыщенного углеводорода, содержащего n атомов углерода.

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

Домашнее задание:

Составить алгоритм для решения задач с помощью графов.  Придумать и решить свою логическую задачу. Подготовить презентацию. Предлагаемые темы:

  «Графы в информатике»

«Графы в программировании»

«Графы и их применение в архитектуре»

«Графы в компьютерных сетях»

«Графы в жизни человека»

Электронные ресурсы:

http://festival.1september. ru/articles/416943/

http://sernam. ru/book_e_math. php? id=33

http://nsportal. ru/ap/library/drugoe/2011/11/05/grafy

http://5fan. ru/wievjob. php? id=1158


Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4