Семинар ДООМ. Цепи. Головоломки. - История изменений

Васильева Александра в 11:08, 10 января 2008

2008-01-10T11:08:43Z

Егорчева Светлана Валентиновна в 17:22, 5 декабря 2007

2007-12-05T17:22:31Z

Егорчева Светлана Валентиновна в 17:21, 5 декабря 2007

2007-12-05T17:21:37Z

Егорчева Светлана Валентиновна в 17:20, 5 декабря 2007

2007-12-05T17:20:42Z

Егорчева Светлана Валентиновна в 17:19, 5 декабря 2007

2007-12-05T17:19:31Z

Егорчева Светлана Валентиновна в 17:18, 5 декабря 2007

2007-12-05T17:18:21Z

Егорчева Светлана Валентиновна: Новая: участник: Болонина Людмила Александровна, 022. '''Урок №1.''' ''Тема:'' '''Цепи. Головоломки.''' '''Цели:''' п...

2007-12-05T16:55:09Z

Новая: участник: Болонина Людмила Александровна, 022. '''Урок №1.''' ''Тема:'' '''Цепи. Головоломки.''' '''Цели:''' п...

Новая страница

[[участник: Болонина Людмила Александровна, 022.]]

'''Урок №1.'''

''Тема:'' '''Цепи. Головоломки.'''

'''Цели:'''

познакомиться со свойствами графов;

разобрать закономерности проведения эйлеровых линий без повторений и без отрыва карандаша от бумаги;

показать решение головоломок на языке теории графов, привить интерес к математике.

'''Ход урока:'''

Рассмотрим следующую головоломку:

Вы, наверное, знаете, что есть такой город Калининград, раньше он назывался Кенигсберг. Через город протекает речка Преголя.

Она делится на два рукава и огибает остров. В XVIII веке в городе было семь мостов, расположенных так, как показано.

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

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

задачей, однако придумать решение никто не смог. Этот вопрос привлек внимание ученых разных стран. Разрешить проблему

удалось известному математику Леонарду Эйлеру. Причем, он не только решил эту конкретную зада¬чу, но придумал общий метод

решения подобных задач. Эйлер посту¬пил следующим образом: он «сжал» сушу в точки, а мосты «вытянул» в ли¬нии.

В результате получилась фигура, изображенная на рис.

[[Изображение:rrr1.gif]]

[[Изображение:rrr2.gif]]

<pre>Такую фигуру, состоящую из точек и линий, связывающих эти точки, называют графом. Точки А, В, С, D

называют вершинами графа, а линии, которые соединяют вершины - ребрами графа. На рис. 2

из вершин B, С, D выходят по 3 ребра, а из вершины А -5 ребер. Вершины, из которых выходит нечетное число ребер,

называют нечетными вершинами, а вершины, из которых выхо¬дит четное количество ребер, - четными.</pre>

Решая задачу про кенигсбергские мосты, Эйлер установил, в частности,

'''свойства графа:'''

• Если все вершины графа четные, то можно одним росчерком

(т.е. не отрывая карандаша от бумаги и не проводя дважды по одной и той же линии)

начертить граф. При этом движение можно начать с любой вершины и окончить в той же вершине.

• Граф с двумя нечетными вершинами тоже можно начертить одним росчерком.

Движение надо начинать от любой нечет¬ной вершины, а заканчивать на другой нечетной вершине.

• Граф с более чем двумя нечетными вершинами невозможно начертить одним росчерком.

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

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

Широко известны в популярной литературе задачи, в которых предлагается выйти из лабиринтов.

Эти задачи можно решить, используя правило Тарри: построение цепи, проходящей вдоль всех ребер графа в

точности по одному разу в каждом направлении. Рассмотрим задачу на проведение эйлеровских линий без повторений и

без отрыва карандаша от бумаги.</pre>

'''ЗАДАЧА:'''

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

[[Изображение:rrr3.gif]]

При решении подобных задач необходимо помнить следующее положение. Для того, чтобы на графе имелась цепь, соединяющая А и В, содержащая все его ребра в точности по одному разу, необходимо и достаточно, чтобы А и В были единственными нечетными вершинами. (В нашем примере это вершины В и А).
Многие известные головоломки могут быть изложены на языке теории графов. Так, решение широкоизвестной задачи о перевозке козы (К), волка (В) и капусты (к) можно представить в виде графа, изображенного на рисунке. Перевозчик обозначен буквой (П).

[[Изображение:rrr4.gif]]

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

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

Задача: Можно ли с одного росчерка вычертить такую фигуру?

[[Изображение:rrr5.gif]]

Урок составила Болонина Л.А. команды 022, г. Казани. Этот урок проводился в 7 классе.

[[Категория:Проект ДООМ]]

← Предыдущая		Версия 11:08, 10 января 2008
Строка 91:		Строка 91:
	Урок составила Болонина Л.А. команды 022, г. Казани. Этот урок проводился в 7 классе.		Урок составила Болонина Л.А. команды 022, г. Казани. Этот урок проводился в 7 классе.

−	[[Категория:Проект ДООМ]]	+	[[Категория:Проект ДООМ 2007-2008 (1 цикл)]]

← Предыдущая		Версия 17:20, 5 декабря 2007
Строка 56:		Строка 56:

	• Граф с двумя нечетными вершинами тоже можно начертить одним росчерком.		• Граф с двумя нечетными вершинами тоже можно начертить одним росчерком.
−
	Движение надо начинать от любой нечет¬ной вершины, а заканчивать на другой нечетной вершине.		Движение надо начинать от любой нечет¬ной вершины, а заканчивать на другой нечетной вершине.

@@ Строка 50: / Строка 50: @@
 <pre>•    Если все вершины графа четные, то можно одним росчерком
 (т.е. не отрывая карандаша от бумаги и не проводя дважды по одной и той же линии)
 начертить граф. При этом движение можно начать с любой вершины и окончить в той же вершине.

@@ Строка 49: / Строка 49: @@
 '''свойства графа:'''
-•    Если все вершины графа четные, то можно одним росчерком
+<pre>•    Если все вершины графа четные, то можно одним росчерком
 (т.е. не отрывая карандаша от бумаги и не проводя дважды по одной и той же линии)
@@ Строка 56: / Строка 56: @@
 •    Граф с двумя нечетными вершинами тоже можно начертить одним росчерком.
-  Движение надо начинать от любой нечет¬ной вершины, а заканчивать на другой нечетной вершине.
+  Движение надо начинать от любой нечетной вершины, а заканчивать на другой нечетной вершине.
-•    Граф с более чем двумя нечетными вершинами невозможно начертить одним росчерком.
+•    Граф с более чем двумя нечетными вершинами невозможно начертить одним росчерком.</pre>
 <pre>В задаче о семи кенигсбергских мостах все четыре вершины соответствующего графа нечетные, т.е. нельзя

@@ Строка 17: / Строка 17: @@
 Рассмотрим следующую головоломку:
-Вы, наверное, знаете, что есть такой город Калининград, раньше он назывался Кенигсберг. Через город протекает речка Преголя.
+<pre>Вы, наверное, знаете, что есть такой город Калининград, раньше он назывался Кенигсберг. Через город протекает речка Преголя.
 Она делится на два рукава и огибает остров. В XVIII веке в городе было семь мостов, расположенных так, как показано.
@@ Строка 31: / Строка 31: @@
   решения подобных задач. Эйлер посту¬пил следующим образом: он «сжал» сушу в точки, а мосты «вытянул» в ли¬нии.
-  В результате получилась фигура, изображенная на рис.
+  В результате получилась фигура, изображенная на рис. </pre>
 [[Изображение:rrr1.gif]]

@@ Строка 7: / Строка 7: @@
 '''Цели:'''
-познакомиться со свойствами графов;
+<pre>познакомиться со свойствами графов;
 разобрать закономерности проведения эйлеровых  линий без повторений и без отрыва карандаша от бумаги;
-показать решение головоломок на языке теории графов, привить интерес к математике.
+показать решение головоломок на языке теории графов, привить интерес к математике.</pre>
 '''Ход урока:'''