Семинар ДООМ. Решение задач на применение теории графов. - История изменений

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

2008-01-10T11:04:18Z

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

2007-12-05T15:05:41Z

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

2007-12-05T15:00:44Z

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

2007-12-05T14:52:33Z

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

2007-12-05T14:10:57Z

Егорчева Светлана Валентиновна: Новая: '''Урок №1.''' ''Тема:'' '''Цепи. Головоломки.''' '''Цели:''' познакомиться со свойствами графов; разобрать ...

2007-12-05T14:05:57Z

Новая: '''Урок №1.''' ''Тема:'' '''Цепи. Головоломки.''' '''Цели:''' познакомиться со свойствами графов; разобрать ...

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

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

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

'''Цели:'''

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

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

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

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

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

Вы, наверное, знаете, что есть такой город Калинин¬град, раньше он назывался Кенигсберг. Через город протекает ре¬ка Преголя. Она делится на два рукава и огибает остров. В XVIII ве¬ке в городе было семь мостов, расположенных так, как показано. Рассказывают, что однажды житель города спросил у своего знакомого, сможет ли он пройти по всем мостам так, чтобы на каждом из них побывать только один раз и вернуться к тому месту, откуда началась прогулка. Многие горожане заинтересова¬лись этой задачей, однако придумать решение никто не смог. Этот вопрос привлек внимание ученых разных стран. Разрешить проб¬лему удалось известному математику Леонарду Эйлеру. Причем, он не только решил эту конкретную зада¬чу, но придумал общий метод реше¬ния подобных задач. Эйлер посту¬пил следующим образом: он «сжал» сушу в точки, а мосты «вытянул» в ли¬нии. В результате получилась фигура, изображенная на рис.

Такую фигуру, состоящую из точек и линий, связывающих эти точки, называют графом. Точки А, В, С, D называют вершинами графа, а линии, которые соединяют вершины - ребрами графа. На рис. 2 из вершин B, С, D выходят по 3 ребра, а из вершины А -5 ребер. Вершины, из которых выходит нечетное число ребер, называют нечетными вершинами, а вершины, из которых выхо¬дит четное количество ребер, - четными.
Решая задачу про кенигсбергские мосты, Эйлер установил, в частности, свойства графа:
• Если все вершины графа четные, то можно одним росчерком (т.е. не отрывая карандаша от бумаги и не проводя дважды по одной и той же линии) начертить граф. При этом движение можно начать с любой вершины и окончить в той же вершине.
• Граф с двумя нечетными вершинами тоже можно начертить одним росчерком. Движение надо начинать от любой нечет¬ной вершины, а заканчивать на другой нечетной вершине,
• Граф с более чем двумя нечетными вершинами невозможно начертить одним росчерком.
В задаче о семи кенигсбергских мостах все четыре вершины соответствующего графа нечетные, т.е. нельзя пройти по всем мостам один раз и закончить.путь там, где он был начат.
Широко известны в популярной литературе задачи, в которых предлагается выйти из лабиринтов. Эти задачи можно решить, используя правило Тарри: построение цепи, проходящей вдоль всех ребер графа в точности по одному разу в каждом направлении. Рассмотрим задачу на проведение эйлеровских линий без повторений и без отрыва карандаша от бумаги.
ЗАДАЧА: Начертить фигуру одной линией, не отрывая карандаша от бумаги и не .

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

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

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

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

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

@@ Строка 1: / Строка 1: @@
 '''Урок №1.'''
@@ Строка 41: / Строка 42: @@
 называют нечетными вершинами, а вершины, из которых выхо¬дит четное количество ребер, - четными.</pre>
-Решая задачу про кенигсбергские мосты, Эйлер установил, в частности, '''свойства графа:'''
+Решая задачу про кенигсбергские мосты, Эйлер установил, в частности,
 •    Если все вершины графа четные, то можно одним росчерком
@@ Строка 82: / Строка 85: @@
 Урок составила Болонина Л.А. команды 022, г. Казани. Этот урок проводился в 7 классе.

@@ Строка 1: / Строка 1: @@
 '''Урок №1.'''
@@ Строка 15: / Строка 14: @@
 '''Ход урока:'''
-<pre>Рассмотрим следующую головоломку:
+Рассмотрим следующую головоломку:
-Вы, наверное, знаете, что есть такой город Калининград, раньше он назывался Кенигсберг. Через город протекает ре¬ка Преголя. Она делится на два рукава и огибает остров. В XVIII ве¬ке в городе было семь мостов, расположенных так, как показано. Рассказывают, что однажды житель города спросил у своего знакомого, сможет ли он пройти по всем мостам так, чтобы на каждом из них побывать только один раз и вернуться к тому месту, откуда началась прогулка. Многие горожане заинтересова¬лись этой задачей, однако придумать решение никто не смог. Этот вопрос привлек внимание ученых разных стран. Разрешить проб¬лему удалось известному математику Леонарду Эйлеру. Причем, он не только решил эту конкретную зада¬чу, но придумал общий метод реше¬ния подобных задач. Эйлер посту¬пил следующим образом: он «сжал» сушу в точки, а мосты «вытянул» в ли¬нии. В результате получилась фигура, изображенная на рис. </pre>
+Вы, наверное, знаете, что есть такой город Калининград, раньше он назывался Кенигсберг. Через город протекает речка Преголя.
 Решая задачу про кенигсбергские мосты, Эйлер установил, в частности, '''свойства графа:'''
-•    Если все вершины графа четные, то можно одним росчерком (т.е. не отрывая карандаша от бумаги и не проводя дважды по одной и той же линии) начертить граф. При этом движение можно начать с любой вершины и окончить в той же вершине.
+•    Если все вершины графа четные, то можно одним росчерком
-•    Граф с двумя нечетными вершинами тоже можно начертить одним росчерком. Движение надо начинать от любой нечет¬ной вершины, а заканчивать на другой нечетной вершине.
+(т.е. не отрывая карандаша от бумаги и не проводя дважды по одной и той же линии)
 •    Граф с более чем двумя нечетными вершинами невозможно начертить одним росчерком.
-<pre>В задаче о семи кенигсбергских мостах все четыре вершины соответствующего графа нечетные, т.е. нельзя пройти по всем мостам один раз и закончить.путь там, где он был начат.
+<pre>В задаче о семи кенигсбергских мостах все четыре вершины соответствующего графа нечетные, т.е. нельзя
 Широко известны в популярной литературе задачи, в которых предлагается выйти из лабиринтов. Эти задачи можно решить, используя правило Тарри: построение цепи, проходящей вдоль всех ребер графа в точности по одному разу в каждом направлении. Рассмотрим задачу на проведение эйлеровских линий без повторений и  без отрыва карандаша от бумаги.</pre>
 '''ЗАДАЧА:'''

@@ Строка 19: / Строка 19: @@
 Вы, наверное, знаете, что есть такой город Калининград, раньше он назывался Кенигсберг. Через город протекает речка Преголя.
-Она делится на два рукава и огибает остров. В XVIII ве¬ке в городе было семь мостов, расположенных так, как показано.
+Она делится на два рукава и огибает остров. В XVIII веке в городе было семь мостов, расположенных так, как показано.
 Рассказывают, что однажды житель города спросил у своего знакомого, сможет ли он пройти по всем мостам так, чтобы на каждом
@@ Строка 29: / Строка 29: @@
   удалось известному математику Леонарду Эйлеру. Причем, он не только решил эту конкретную зада¬чу, но придумал общий метод
-  реше¬ния подобных задач. Эйлер посту¬пил следующим образом: он «сжал» сушу в точки, а мосты «вытянул» в ли¬нии.
+  решения подобных задач. Эйлер посту¬пил следующим образом: он «сжал» сушу в точки, а мосты «вытянул» в ли¬нии.
   В результате получилась фигура, изображенная на рис.
 <pre>Такую фигуру, состоящую из точек и линий, связывающих эти точки, называют графом. Точки А, В, С, D
@@ Строка 73: / Строка 76: @@
 Начертить фигуру одной линией, не отрывая карандаша от бумаги и не проводя дважды линий карандашом.
 При решении подобных задач необходимо помнить следующее положение. Для того, чтобы на графе имелась цепь, соединяющая А и В, содержащая все его ребра в точности по одному разу, необходимо и достаточно, чтобы А и В были единственными нечетными вершинами. (В нашем примере это вершины В и А).
 Многие известные головоломки могут быть изложены на языке теории графов. Так, решение широкоизвестной задачи о перевозке козы (К), волка (В) и капусты (к) можно представить в виде графа, изображенного на рисунке. Перевозчик  обозначен буквой (П).
 Из графа видно, что решение может быть получено двумя способами.
@@ Строка 83: / Строка 89: @@
 Задача: Можно ли с одного росчерка вычертить такую фигуру?
 Урок составила Болонина Л.А. команды 022, г. Казани. Этот урок проводился в 7 классе.
 [[Категория:Проект ДООМ]]