ТолВИКИ - Вклад участника [ru]

Обсуждение:Семинар ДООМ "Электронный обучающий ресурс"

2007-12-05T19:00:22Z

Егорчева Светлана Валентиновна:

Добрый день. Я с большим интересов просмотрела Вашу работу. На своих уроках я стараюсь применить новые методы и формы обучения. Ваша работа подсказала мне как сделать занятия математикой еще более увлекательными и интересными. Большое Вам спасибо.
--[[Участник:Пенкина Любовь Ивановна|Пенкина Любовь Ивановна]] 13:23, 13 ноября 2007 (UZT)

Уважаемая Елена!
Очень полезная и удачная работа. Со своей командой мы проходили тренажер и детям очень нравится. Нужно пройти еще раз, чтобы дети поняли, что их знания улучшились. За эту возможность я Вам благодарна!!!!

Руководитель команд 062, 063
--[[Участник:Коннова Елена|Коннова Елена]] 23:15, 20 ноября 2007

Здравствуйте. Большое спасибо за электронный обучающий курс.Очень интересная, яркая работа. Учащиеся будут с удовольствием заниматься по этому тренажеру.--[[Участник:Егорчева Светлана Валентиновна|Егорчева Светлана Валентиновна]] 00:00, 6 декабря 2007 (UZT)

Обсуждение:Семинар ДООМ. Интеллектуальная игра "Умники и умницы"

2007-12-05T18:49:47Z

Егорчева Светлана Валентиновна:

Здравствуйте. Игра понравилась. Очень большой материал использован в процессе подготовки игры: и из истории графов, и великие математики, удачно подобраны задачи.--[[Участник:Егорчева Светлана Валентиновна|Егорчева Светлана Валентиновна]] 23:47, 5 декабря 2007 (UZT)

Обсуждение:Семинар ДООМ. Интеллектуальная игра "Умники и умницы"

2007-12-05T18:47:22Z

Егорчева Светлана Валентиновна: Новая: Здравствуйте. Игра понравилась. Очень большой материал использован в процессе подготовки игры.--~~~~

Здравствуйте. Игра понравилась. Очень большой материал использован в процессе подготовки игры.--[[Участник:Егорчева Светлана Валентиновна|Егорчева Светлана Валентиновна]] 23:47, 5 декабря 2007 (UZT)

Обсуждение:Семинар ДООМ "Игра ЧТО? ГДЕ? КОГДА?"

2007-12-05T18:44:06Z

Егорчева Светлана Валентиновна:

Интересная игра «Что? Где? Когда?», можно проводить в любом классе, этой разработкой воспользуется любой из нас с Вашего разрешения --[[Участник:Трифонова В.А.|Трифонова В.А.]] 23:40, 5 декабря 2007 (UZT)

Здравствуйте. Хорошая игра "Что?Где?Когда?.Интересные стихи,хорошо подобраны задачи для игроков.--[[Участник:Егорчева Светлана Валентиновна|Егорчева Светлана Валентиновна]] 23:44, 5 декабря 2007 (UZT)

Обсуждение:Семинар ДООМ "Можно ли не ломая проволоки изготовить каркас куба?"

2007-12-05T18:37:49Z

Егорчева Светлана Валентиновна: Новая: Здравствуйте. Методически правильная, полная разработка урока.Интересная историческая справка, что ...

Здравствуйте.
Методически правильная, полная разработка урока.Интересная историческая справка, что несомнено привлечет внимание учащихся.Все ясно и понятно. Спасибо за урок.
--[[Участник:Егорчева Светлана Валентиновна|Егорчева Светлана Валентиновна]] 23:37, 5 декабря 2007 (UZT)

Обсуждение:Семинар ДООМ. Решение комбинаторных задач

2007-12-05T18:14:01Z

Егорчева Светлана Валентиновна:

Здравствуйте.

Познакомилась с Вашей статьей.
Хотелось бы добавить несколько слов. по поводу решения задачи 2.
Разумно одновременно с приведенным решением познакомить детей с другим, который позволяет решить задачу для большого числа участников турнира.

Каждая из К команд встречалась с К-1 соперниками, всего К(К-1) встреч. Но при этом каждую встречу мы посчитали по два раза, значит на самом деле встреч в 2 раза меньше. Ответ: К(К-1):2.

Аналогично для 1 задачи

Впрочем, для малого числа команд переборный метод нагляднее.
'''''[[Участник:Коннова Елена|Коннова Елена]] 23:29, 27 ноября 2007 (UZT)'''''

Содержание плана урока отвечает поставленной цели. Учитель продумал каждую структурную часть занятия, отобрал приемы и методы работы. Подбор задач очень интересный, позволяет развивать навыки абстрактного и логического мышления. Замечательный урок, очень доступный, познавательный.
РЕПЛИКУ составила учитель математики БОЛОНИНА ЛЮДМИЛА АЛЕКСАНДРОВНА команды id_022 г. Казань школа №113 на урок Хазовой Людмилы Моде (команды многогранник).
--[[Участник:Егорчева Светлана Валентиновна|Егорчева Светлана Валентиновна]] 23:14, 5 декабря 2007 (UZT)

Обсуждение:Семинар ДООМ Решение вероятностных задач с помощью построения «древа» исходов.

2007-12-05T18:04:32Z

Егорчева Светлана Валентиновна: Новая: Содержание урока построено на высоком уровне. При решении задач учителем удачно выбраны формы графа, ...

Содержание урока построено на высоком уровне. При решении задач учителем удачно выбраны формы графа, составлены ветви, соответствующие определенным условиям, что позволяет обходиться без громоздких решений. Урок насыщен элементами нового материала, интересными задачами, развивающими любознательность.
РЕПЛИКУ составила учитель математики БОЛОНИНА ЛЮДМИЛА АЛЕКСАНДРОВНА команды id_022,г. Казань школа №113 на урок Москевич Ларисы Вячеславны (команды 061)
--[[Участник:Егорчева Светлана Валентиновна|Егорчева Светлана Валентиновна]] 23:04, 5 декабря 2007 (UZT)

Участник:Трифонова Валентина Артемьевна

2007-12-05T17:51:46Z

Егорчева Светлана Валентиновна:

'''Город:''' Казань, Республика Татарстан

'''Место работы:''' [муниципальное общеобразовательное учреждение общеобразовательная школа № 113],

'''Должность:''' учитель математики'''

<br>[[Семинар ДООМ "Основные понятия теории графов."]]
<br>[[Семинар ДООМ "Решение задач на применение теории графов"]]

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

Участник:Трифонова Валентина Артемьевна

2007-12-05T17:50:19Z

Егорчева Светлана Валентиновна:

'''Город:''' Казань, Республика Татарстан

'''Место работы:''' [муниципальное общеобразовательное учреждение общеобразовательная школа № 113],

'''Должность:''' учитель математики'''

<br>[[Семинар ДООМ"Основные понятия теории графов."]]
<br>[[Семинар ДООМ"Решение задач на применение теории графов"]]

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

Участник:Трифонова Валентина Артемьевна

2007-12-05T17:48:37Z

Егорчева Светлана Валентиновна:

'''Город:''' Казань, Республика Татарстан

'''Место работы:''' [муниципальное общеобразовательное учреждение общеобразовательная школа № 113],

'''Должность:''' учитель математики'''

<br>[[Семинар ДООМ"Основные понятия теории графов."]]
<br>[[Семинар ДООМ"Решение задач на применеие теории графов."]]

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

Участник:Трифонова Валентина Артемьевна

2007-12-05T17:47:15Z

Егорчева Светлана Валентиновна:

'''Город:''' Казань, Республика Татарстан

'''Место работы:''' [муниципальное общеобразовательное учреждение общеобразовательная школа № 113],

'''Должность:''' учитель математики'''

<br>[[Семинар ДООМ "Основные понятия теории графов"]]
<br>[[Семинар ДООМ. Основные понятия теории графов]]

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

Участник:Болонина Людмила Александровна

2007-12-05T17:44:30Z

Егорчева Светлана Валентиновна:

'''Город:''' Казань, Республика Татарстан

'''Место работы:''' [муниципальное общеобразовательное учреждение общеобразовательная школа № 113],

'''Должность:''' учитель математики'''

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

<br>[[Семинар ДООМ "Из опыта изучения элементов теории графов."]]
<br>[[Семинар ДООМ "Применение графов к решению логических задач."]]
<br>[[Семинар ДООМ. Цепи. Головоломки.]]

Участник:Болонина Людмила Александровна

2007-12-05T17:43:15Z

Егорчева Светлана Валентиновна:

'''Город:''' Казань, Республика Татарстан

'''Место работы:''' [муниципальное общеобразовательное учреждение общеобразовательная школа № 113],

'''Должность:''' учитель математики'''

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

<br>[[Семинар ДООМ. "Из опыта изучения элементов теории графов"]]
<br>[[Семинар ДООМ. "Применение графов к решению логических задач".]]
<br>[[Семинар ДООМ. Цепи. Головоломки.]]

Дистанционный методический семинар ДООМ

2007-12-05T17:41:50Z

Егорчева Светлана Валентиновна: /* Участники семинара */

'''Уважаемые педагоги, локальные координаторы команд-участниц ДООМ'''! Отдельные заявки на участие в семинаре «Теория графов в школьном курсе математики и информатики» присылать не нужно.

== Как стать Участником семинара ==

'''I. Руководители команд (локальные координаторы) должны зарегистрироваться в ТолВики под своим реальным именем (для не зарегистрировавшихся ранее). Для этого нужно:

* В верхнем правом углу любой страницы нажать ссылку '''Представиться системе'''.
* На вопрос "Вы ещё не зарегистрировались?" кликнуть '''Создать учётную запись'''.
* В появившихся формах введите Имя участника – то имя, под которым вы будете отображаться на сайте (желательно в формате - Фамилия Имя Отчество), пароль - сочетание знаков, которое необходимо для каждого последующего входа в систему.
* Заполните также поле '''Ваше настоящее имя'''. Это будет способствовать комфортному общению и сделает более удобной работу участников.

<center>[[Изображение:Reg_lk_doom.jpg]] <br>
Рис. 1.
</center>

* Затем нажмите '''Зарегистрировать нового участника'''.
* Заполните (не обязательно) '''Личную страницу участника''' методического семинара (см. пример [[Участник:Васильева Александра|Васильева Александра]]).

'''II. Создать статью Семинар ДООМ YYY (где YYY название (тема) статьи). Для этого:

* Введите в окно '''Поиск''' в левой части экрана на странице ТолВики '''имя статьи''', которую Вы хотите написать, и нажмите кнопку '''Перейти'''. Внимание! Название статьи обязательно должно начинаться со слов «'''Семинар ДООМ'''». Если такая статья уже есть, то система предложит Вам ее для чтения и правки (если это не Ваша статья, измените название статьи, создаваемой Вами, и повторите действия, начиная с п. II.).
* Если такой статьи еще нет, то появится ссылка '''Создать страницу''', окрашенная в красный цвет.
* Нажав ссылку, Вы окажетесь в окне редактирования будущей статьи. В верхней части окна редактирования будет надпись с названием вашей статьи: '''Редактирование:Название статьи'''. Внимание! Ваша статья уже названа, и поэтому не нужно еще раз писать название внутри статьи.
* В окне редактирования поместите Вашу статью. Внимание! В начале статьи под ее названием '''обязательно укажите автора и Идентификационный номер команды'''. (Если '''Личная страница участника''', полученная при регистрации, была Вами заполнена, сделайте на нее ссылку с имени автора (например, <nowiki>[[Участник:Васильева Александра]]</nowiki>), а с '''Личной страницы участника''' ссылку на статью (т.е. на Личной странице, поместить запись <nowiki>[[Семинар ДООМ YYY]]</nowiki>, где YYY – название (тема) статьи)).
* Нажмите кнопку '''Предварительный просмотр'''. Экран будет разделен на два окна. В одном окне отображается текст в том виде, как он будет выглядеть на сайте, а второе окно – это окно редактирования. Вносите изменения во втором окне, нажимая периодически кнопку Предварительный просмотр, в первом - отслеживайте внесённые правки.
* '''Обязательно''' в конце статьи следует указать в двойных квадратных скобках (через двоеточие, без пробелов) одну или несколько категорий, в которых разместится Ваша статья. Например, '''[[Категория:Проект ДООМ]]'''.
* Статья будет считаться незаконченной, если в ней отсутствуют внутренние и внешние ссылки.
* Нажмите кнопку '''Записать страницу'''.
* Для перехода в режим правки нажмите вверху вкладку «'''Править'''».

'''III. Разместите на сайте проекта ДООМ в разделе «Дистанционный методический семинар» внутреннюю ссылку на свою статью в следующем формате: ФИО автора, (Идентификационный номер команды), название статьи (если Вы являетесь автором нескольких статей, просто перечислите их). Для этого нужно:

* Нажать на ссылку [править] в разделе "Участники семинара".

<center>[[Изображение:Prav_sem_doom.jpg]]<br>
Рис. 2.</center>

* Записать ФИО автора, затем название статьи в двойных квадратных скобках (например, Васильева Александра Сергеевна, 777, <nowiki>[[Семинар ДООМ YYY]]</nowiki>).
* Нажать Записать страницу.
* Если название статьи будет красного цвета, значит, Вы сделали что-то неправильно. Проверьте себя, внесите исправления и повторите попытку.

'''Внимание!'''
Свои отзывы, комментарии и реплики на статьи других участников семинара нужно оставлять на странице обсуждаемой статьи во вкладке '''«Обсуждение».''' Для этого:
* Откройте статью, заинтересовавшую вас (на сайте проекта ДООМ в разделе «Дистанционный методический семинар»), затем вкладку '''«Обсуждение», «Править»''' и впишите нужный текст.
* Нажмите кнопку '''«Ваша подпись и момент времени»''' на панели визуального редактора, чтобы подписать свою работу.
* Нажмите кнопку '''Записать страницу'''.

'''Не забывайте''' представляться при работе в ТолВики. Для этого нужно выполнять следующие действия:
* В правом верхнем углу экрана выбрать ссылку [[Служебная:Userlogin|Представиться системе]].
* В окнах "Ваше имя участника" и "Ваш пароль" ввести логин и пароль, выбранные при регистрации.
* Щелкнуть по кнопке "Представиться системе".

== Участники семинара ==

# [[Участник:Пенкина Любовь Ивановна|Пенкина Любовь Ивановна]],005,[[Семинар ДООМ. Знакомство с графами (5 класс)]],[[Семинар ДООМ. Интеллектуальная игра "Умники и умницы"]]

# [[Участник:Иванова Елена|Иванова Елена Андреевна]], 025,[[Семинар ДООМ "Электронный обучающий ресурс"]]
# [[Участник:Москевич Лариса Вячеславовна|Москевич Лариса Вячеславовна]], 061,[[Семинар ДООМ: Первая встреча с графом.]],[[Семинар ДООМ Решение вероятностных задач с помощью построения «древа» исходов.]]
# [[Участник:Октысюк Ульяна Святославовна|Октысюк Ульяна Святославовна]], 069, [[Семинар ДООМ урок математики "Графы"]]
# [[Участник:Янина Ирина Владимировна|Янина Ирина Владимировна]], 053, [[Семинар ДООМ. Решение комбинаторных задач с помощью графов]], [[Семинар ДООМ. Сетевой график]]
# [[Участник:Круглова Валентина Николаевна|Круглова Валентина Николаевна]], 006, [[Семинар ДООМ "Игра ЧТО? ГДЕ? КОГДА?"]]
# [[Участник:Хазова Людмила Модестовна|Хазова Людмила Модестовна]], [[Участник:Многогранник 041|041]], [[Семинар ДООМ. Использование графов при решении задач]], [[Семинар ДООМ. Решение комбинаторных задач]], [[Семинар ДООМ. Графы при решении задач]]
# [[Участник:Лесных Марина Владимировна|Лесных Марина Владимировна]], [[Участник:Следопыт 071|071]],[[Участник:Метеор 027|027]], [[Семинар ДООМ. Впечатление о проекте]]
# [[Участник:Коннова Елена|Коннова Елена Генриевна]],[[Участник:Альтаир 062|062]], [[Участник:Форсаж 063|063]], [[Семинар ДООМ Некоторые уточнения для лучшего взаимопонимания]], [[Семинар ДООМ Элективный курс Графы]], [[Семинар ДООМ Материалы для курса Графы]]
# [[Участник:Егорчева Светлана Валентиновна|Егорчева Светлана Валентиновна]],022,[[Семинар ДООМ "Основы графики Паскаля"]]
# [[Участник:Невзорова Марина Евгеньевна|Невзорова Марина Евгеньевна]],002,[[Семинар ДООМ Уникурсальные кривые (фигуры)]]
# [[Участник:Болонина Людмила Александровна|Болонина Людмила Александровна]],022,[[Семинар ДООМ "Из опыта изучения элементов теории графов."]],022,[[Семинар ДООМ "Применение графов к решению логических задач."]],022,[[Семинар ДООМ. Цепи. Головоломки.]]
# [[Участник:Трифонова Валентина Артемьевна|Трифонова Валентина Артемьевна]],022,[[Семинар ДООМ "Основные понятия теории графов."]],022,[[Семинар ДООМ "Решение задач на применение теории графов"]]
# [[Участник:Шувалова Юлия Григорьевна|Шувалова Юлия Григорьевна]],[[Участник:Львы_40|040]],[[Семинар ДООМ "Можно ли не ломая проволоки изготовить каркас куба?"]],[[Семинар ДООМ "Математическое исследование "Кенигсбергские мосты"]], [[Семинар ДООМ "Задачи по теме "Можно ли не ломая проволоки изготовить каркас куба?"]]
# [[Участник:Стрельцова Марина Витальевна|Стрельцова Марина Витальевна]],[[Участник:Львы_40|040]],[[Семинар ДООМ "Математический КВН"]]

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

Участник:Трифонова Валентина Артемьевна

2007-12-05T17:29:39Z

Егорчева Светлана Валентиновна:

Участник:Болонина Людмила Александровна

2007-12-05T17:26:35Z

Егорчева Светлана Валентиновна:

'''Город:''' Казань, Республика Татарстан

'''Место работы:''' [муниципальное общеобразовательное учреждение общеобразовательная школа № 113],

'''Должность:''' учитель математики'''

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

<br>[[Семинар ДООМ. Из опыта изучения элементов теории графов]]
<br>[[Семинар ДООМ. Применение графов к решению логических задач.]]
<br>[[Семинар ДООМ. Цепи. Головоломки.]]

Участник:Болонина Людмила Александровна

2007-12-05T17:25:23Z

Егорчева Светлана Валентиновна:

'''Город:''' Казань, Республика Татарстан

'''Место работы:''' [муниципальное общеобразовательное учреждение общеобразовательная школа № 113],

'''Должность:''' учитель математики'''

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

<br>[[Семинар ДООМ. Из опыта изучения элементов теории графов]]
<br>[[Семинар ДООМ. Из опыта изучения элементов теории графов]]
<br>[[Семинар ДООМ. Цепи. Головоломки.]]

Семинар ДООМ. Цепи. Головоломки.

2007-12-05T17:22:31Z

Егорчева Светлана Валентиновна:

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

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

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

'''Цели:'''

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Семинар ДООМ. Цепи. Головоломки.

2007-12-05T17:21:37Z

Егорчева Светлана Валентиновна:

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

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

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

'''Цели:'''

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Семинар ДООМ. Цепи. Головоломки.

2007-12-05T17:20:42Z

Егорчева Светлана Валентиновна:

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

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

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

'''Цели:'''

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Семинар ДООМ. Цепи. Головоломки.

2007-12-05T17:19:31Z

Егорчева Светлана Валентиновна:

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

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

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

'''Цели:'''

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Семинар ДООМ. Цепи. Головоломки.

2007-12-05T17:18:21Z

Егорчева Светлана Валентиновна:

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

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

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

'''Цели:'''

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Дистанционный методический семинар ДООМ

2007-12-05T17:14:51Z

Егорчева Светлана Валентиновна: /* Участники семинара */

'''Уважаемые педагоги, локальные координаторы команд-участниц ДООМ'''! Отдельные заявки на участие в семинаре «Теория графов в школьном курсе математики и информатики» присылать не нужно.

== Как стать Участником семинара ==

'''I. Руководители команд (локальные координаторы) должны зарегистрироваться в ТолВики под своим реальным именем (для не зарегистрировавшихся ранее). Для этого нужно:

* В верхнем правом углу любой страницы нажать ссылку '''Представиться системе'''.
* На вопрос "Вы ещё не зарегистрировались?" кликнуть '''Создать учётную запись'''.
* В появившихся формах введите Имя участника – то имя, под которым вы будете отображаться на сайте (желательно в формате - Фамилия Имя Отчество), пароль - сочетание знаков, которое необходимо для каждого последующего входа в систему.
* Заполните также поле '''Ваше настоящее имя'''. Это будет способствовать комфортному общению и сделает более удобной работу участников.

<center>[[Изображение:Reg_lk_doom.jpg]] <br>
Рис. 1.
</center>

* Затем нажмите '''Зарегистрировать нового участника'''.
* Заполните (не обязательно) '''Личную страницу участника''' методического семинара (см. пример [[Участник:Васильева Александра|Васильева Александра]]).

'''II. Создать статью Семинар ДООМ YYY (где YYY название (тема) статьи). Для этого:

* Введите в окно '''Поиск''' в левой части экрана на странице ТолВики '''имя статьи''', которую Вы хотите написать, и нажмите кнопку '''Перейти'''. Внимание! Название статьи обязательно должно начинаться со слов «'''Семинар ДООМ'''». Если такая статья уже есть, то система предложит Вам ее для чтения и правки (если это не Ваша статья, измените название статьи, создаваемой Вами, и повторите действия, начиная с п. II.).
* Если такой статьи еще нет, то появится ссылка '''Создать страницу''', окрашенная в красный цвет.
* Нажав ссылку, Вы окажетесь в окне редактирования будущей статьи. В верхней части окна редактирования будет надпись с названием вашей статьи: '''Редактирование:Название статьи'''. Внимание! Ваша статья уже названа, и поэтому не нужно еще раз писать название внутри статьи.
* В окне редактирования поместите Вашу статью. Внимание! В начале статьи под ее названием '''обязательно укажите автора и Идентификационный номер команды'''. (Если '''Личная страница участника''', полученная при регистрации, была Вами заполнена, сделайте на нее ссылку с имени автора (например, <nowiki>[[Участник:Васильева Александра]]</nowiki>), а с '''Личной страницы участника''' ссылку на статью (т.е. на Личной странице, поместить запись <nowiki>[[Семинар ДООМ YYY]]</nowiki>, где YYY – название (тема) статьи)).
* Нажмите кнопку '''Предварительный просмотр'''. Экран будет разделен на два окна. В одном окне отображается текст в том виде, как он будет выглядеть на сайте, а второе окно – это окно редактирования. Вносите изменения во втором окне, нажимая периодически кнопку Предварительный просмотр, в первом - отслеживайте внесённые правки.
* '''Обязательно''' в конце статьи следует указать в двойных квадратных скобках (через двоеточие, без пробелов) одну или несколько категорий, в которых разместится Ваша статья. Например, '''[[Категория:Проект ДООМ]]'''.
* Статья будет считаться незаконченной, если в ней отсутствуют внутренние и внешние ссылки.
* Нажмите кнопку '''Записать страницу'''.
* Для перехода в режим правки нажмите вверху вкладку «'''Править'''».

'''III. Разместите на сайте проекта ДООМ в разделе «Дистанционный методический семинар» внутреннюю ссылку на свою статью в следующем формате: ФИО автора, (Идентификационный номер команды), название статьи (если Вы являетесь автором нескольких статей, просто перечислите их). Для этого нужно:

* Нажать на ссылку [править] в разделе "Участники семинара".

<center>[[Изображение:Prav_sem_doom.jpg]]<br>
Рис. 2.</center>

* Записать ФИО автора, затем название статьи в двойных квадратных скобках (например, Васильева Александра Сергеевна, 777, <nowiki>[[Семинар ДООМ YYY]]</nowiki>).
* Нажать Записать страницу.
* Если название статьи будет красного цвета, значит, Вы сделали что-то неправильно. Проверьте себя, внесите исправления и повторите попытку.

'''Внимание!'''
Свои отзывы, комментарии и реплики на статьи других участников семинара нужно оставлять на странице обсуждаемой статьи во вкладке '''«Обсуждение».''' Для этого:
* Откройте статью, заинтересовавшую вас (на сайте проекта ДООМ в разделе «Дистанционный методический семинар»), затем вкладку '''«Обсуждение», «Править»''' и впишите нужный текст.
* Нажмите кнопку '''«Ваша подпись и момент времени»''' на панели визуального редактора, чтобы подписать свою работу.
* Нажмите кнопку '''Записать страницу'''.

'''Не забывайте''' представляться при работе в ТолВики. Для этого нужно выполнять следующие действия:
* В правом верхнем углу экрана выбрать ссылку [[Служебная:Userlogin|Представиться системе]].
* В окнах "Ваше имя участника" и "Ваш пароль" ввести логин и пароль, выбранные при регистрации.
* Щелкнуть по кнопке "Представиться системе".

== Участники семинара ==

# [[Участник:Пенкина Любовь Ивановна|Пенкина Любовь Ивановна]],005,[[Семинар ДООМ. Знакомство с графами (5 класс)]],[[Семинар ДООМ. Интеллектуальная игра "Умники и умницы"]]

# [[Участник:Иванова Елена|Иванова Елена Андреевна]], 025,[[Семинар ДООМ "Электронный обучающий ресурс"]]
# [[Участник:Москевич Лариса Вячеславовна|Москевич Лариса Вячеславовна]], 061,[[Семинар ДООМ: Первая встреча с графом.]],[[Семинар ДООМ Решение вероятностных задач с помощью построения «древа» исходов.]]
# [[Участник:Октысюк Ульяна Святославовна|Октысюк Ульяна Святославовна]], 069, [[Семинар ДООМ урок математики "Графы"]]
# [[Участник:Янина Ирина Владимировна|Янина Ирина Владимировна]], 053, [[Семинар ДООМ. Решение комбинаторных задач с помощью графов]], [[Семинар ДООМ. Сетевой график]]
# [[Участник:Круглова Валентина Николаевна|Круглова Валентина Николаевна]], 006, [[Семинар ДООМ "Игра ЧТО? ГДЕ? КОГДА?"]]
# [[Участник:Хазова Людмила Модестовна|Хазова Людмила Модестовна]], [[Участник:Многогранник 041|041]], [[Семинар ДООМ. Использование графов при решении задач]], [[Семинар ДООМ. Решение комбинаторных задач]], [[Семинар ДООМ. Графы при решении задач]]
# [[Участник:Лесных Марина Владимировна|Лесных Марина Владимировна]], [[Участник:Следопыт 071|071]],[[Участник:Метеор 027|027]], [[Семинар ДООМ. Впечатление о проекте]]
# [[Участник:Коннова Елена|Коннова Елена Генриевна]],[[Участник:Альтаир 062|062]], [[Участник:Форсаж 063|063]], [[Семинар ДООМ Некоторые уточнения для лучшего взаимопонимания]], [[Семинар ДООМ Элективный курс Графы]], [[Семинар ДООМ Материалы для курса Графы]]
# [[Участник:Егорчева Светлана Валентиновна|Егорчева Светлана Валентиновна]],022,[[Семинар ДООМ "Основы графики Паскаля"]]
# [[Участник:Невзорова Марина Евгеньевна|Невзорова Марина Евгеньевна]],002,[[Семинар ДООМ Уникурсальные кривые (фигуры)]]
# [[Участник:Болонина Людмила Александровна|Болонина Людмила Александровна]],022,[[Семинар ДООМ "Из опыта изучения элементов теории графов."]],022,[[Семинар ДООМ "Применение графов к решению логических задач."]],022,[[Семинар ДООМ "Цепи. Головоломки."]]
# [[Участник:Трифонова Валентина Артемьевна|Трифонова Валентина Артемьевна]],022,[[Семинар ДООМ "Основные понятия теории графов."]],022,[[Семинар ДООМ "Решение задач на применение теории графов"]]
# [[Участник:Шувалова Юлия Григорьевна|Шувалова Юлия Григорьевна]],[[Участник:Львы_40|040]],[[Семинар ДООМ "Можно ли не ломая проволоки изготовить каркас куба?"]],[[Семинар ДООМ "Математическое исследование "Кенигсбергские мосты"]], [[Семинар ДООМ "Задачи по теме "Можно ли не ломая проволоки изготовить каркас куба?"]]
# [[Участник:Стрельцова Марина Витальевна|Стрельцова Марина Витальевна]],[[Участник:Львы_40|040]],[[Семинар ДООМ "Математический КВН"]]

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

Файл:Rrr5.gif

2007-12-05T17:10:22Z

Егорчева Светлана Валентиновна:

Файл:Rrr4.gif

2007-12-05T17:09:15Z

Егорчева Светлана Валентиновна:

Файл:Rrr3.gif

2007-12-05T17:08:25Z

Егорчева Светлана Валентиновна:

Файл:Rrr2.gif

2007-12-05T17:06:52Z

Егорчева Светлана Валентиновна:

Файл:Rrr1.gif

2007-12-05T17:05:51Z

Егорчева Светлана Валентиновна:

Семинар ДООМ. Цепи. Головоломки.

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 классе.

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

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

2007-12-05T15:05:41Z

Егорчева Светлана Валентиновна:

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

2007-12-05T15:00:44Z

Егорчева Светлана Валентиновна:

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

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

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

'''Цели:'''

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2007-12-05T14:52:33Z

Егорчева Светлана Валентиновна:

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

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

'''Цели:'''

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2007-12-05T14:10:57Z

Егорчева Светлана Валентиновна:

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

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

'''Цели:'''

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

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

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

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

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

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

<pre>Такую фигуру, состоящую из точек и линий, связывающих эти точки, называют графом. Точки А, В, С, D называют вершинами графа, а линии, которые соединяют вершины - ребрами графа. На рис. 2 из вершин B, С, D выходят по 3 ребра, а из вершины А -5 ребер. Вершины, из которых выходит нечетное число ребер, называют нечетными вершинами, а вершины, из которых выхо¬дит четное количество ребер, - четными.</pre>
Решая задачу про кенигсбергские мосты, Эйлер установил, в частности, '''свойства графа:'''

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

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

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

<pre>В задаче о семи кенигсбергских мостах все четыре вершины соответствующего графа нечетные, т.е. нельзя пройти по всем мостам один раз и закончить.путь там, где он был начат.
Широко известны в популярной литературе задачи, в которых предлагается выйти из лабиринтов. Эти задачи можно решить, используя правило Тарри: построение цепи, проходящей вдоль всех ребер графа в точности по одному разу в каждом направлении. Рассмотрим задачу на проведение эйлеровских линий без повторений и без отрыва карандаша от бумаги.</pre>

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

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

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

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

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

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

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

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

2007-12-05T14:05:57Z

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

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

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

'''Цели:'''

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

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

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

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

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

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

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

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

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

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

Семинар ДООМ "Применение графов к решению логических задач."

2007-12-05T13:44:53Z

Егорчева Светлана Валентиновна:

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

''Краткое изложение факультативного занятия на тему:''

'''«Применение графов к решению логических задач»'''

'''Цель:''' разобрать закономерности решения логических задач с помощью графов.

'''Ход занятия:'''

'''1)''' Объяснение учителем.

'''2)''' Решение логических задач с помощью графов.

'''3)''' Подведение итогов.

'''4)''' Домашнее задание.

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

'''Задача 1.'''

Из трех человек, стоящих рядом, один всегда говорит правду (правдивый), другой всегда лжет (лжец), а третий, смотря по обстоятельствам, говорит правду или ложь («дипломат»). У стоящего слева спросили: «Кто стоит рядом с тобой?» Он ответил: «Правдолюб». Стоящему в центре, задали вопрос: «Кто ты?», и он ответил: «Я дипломат». Когда у стоящего справа спросили: «Кто стоит рядом с тобой?», он ответил: «Лжец». Кто где стоял?
Если в данной задаче ребро графа будет соответствовать месту, занимаемому тем или иным человеком, то нам могут представиться следующие возможности.

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

'''Решение:'''

Рассмотрим первую возможность. Если «правдолюб» стоит слева, то рядом с ним, судя по его ответу, находится «правдолюб». У нас же стоит лжец. Рассмотрев таким образом все остальные возможности, мы придем к выводу, что расстановка «дипломат», «лжец», «правдолюб» удовлетворяет задаче. Действительно, если «правдолюб» стоит справа, то, по его ответу, рядом с ним «лжец», что выполняется. Стоящий в центре заявляет, что он «дипломат», и следовательно, лжет, а стоящий справа также лжет. Таким образом все условия задачи выполнены. В качестве задачи второго типа можно предложить следующую.

'''Задача 2.'''

В пяти корзинах лежали яблоки пяти разных сортов. Яблоки первого сорта лежат в корзинах Г и Д; яблоки второго сорта - в корзинах А. Б, Г; в корзинах А, Б, В имеются яблоки пятого сорта, в корзине В имеются к тому же яблоки четвертого сорта, а в корзине Д-третьего. Пронумеруйте каждую корзину так, чтобы в корзине №1 были яблоки первого сорта (хотя бы одно); в корзине № 2-второго и т.д.

'''Решение:''' Составим граф:

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

''' Ответ:''' №1-Г; №2-А или №2-Б; №3-Д; №4-В; №5-Б или №5-А
Возникает вопрос: так ли уж нужны были графы в этой задаче? Разве нельзя прийти к решению логическим путем? Можно, но графы придали условия наглядность, упростили решение.

'''Задача 3.'''

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

'''Решение:'''

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

Решение этой задачи достигается построением следующего графа, где каждая вершина обозначает соответствующую газету и соответственно 5 подписчиков, а каждое ребро будет соответствовать одному подписчику.
Суть метода решения этой и подобных ей задач состоит в установлении связей между множеством вершин и множеством ребер графа.
Следовательно, в данной задаче предприниматели выписывают шесть наименований газет. Всего предпринимателей:
6*(6-1)/2=15 чел.
Полезно решать логические задачи разными методами. Например, следующую задачу можно решить способом логических квадратов и с помощью графов.

'''Задача 3.'''

Три ученицы - Аня, Валя. Катя - участвовали в новогоднем бале - маскараде. Одна из них была в красном костюме, другая - в белом, третья - в синем. Если сказать, что Аня была в красном, Валя – не в красном, и Катя –не в синем, то одно из этих утверждений будет верным, а два других –неверными. В каком костюме была каждая из учениц?

'''Решение:'''

Логический квадрат для этого случая имеет вид:

Аня Валя Катя
Красное 0 1 0
Белое 0 0 1
Синее 1 0 0

Графы для этой задачи имеют вид.

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

И в том, и в другом случае получаем ответ: Валя была в красном платье, Катя – в белом и Аня - в синем.
Ребята оценивают достоинства и недостатки каждого из этих способов.

'''3.''' Подведение итогов.

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

Разбирается дело Брауна, Джонса и Смита. Один из них совершил преступление. В процессе расследования каждый из них сделал два заявления.

Браун: «Я не сделал этого. Джонс не делал этого».

Джонс: «Браун не делал этого. Смит сделал это».

Смит: «Я не делал этого. Браун сделал это».

Было установлено, что один из них дважды солгал; другой дважды сказал правду, третий раз солгал, раз сказал правду. Кто совершил преступление?

Факультативное занятие составила Болонина Л.А. команды 022, г. Казани. для учащихся 7 класса..

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

Семинар ДООМ "Из опыта изучения элементов теории графов."

2007-12-05T13:35:47Z

Егорчева Светлана Валентиновна:

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

'''Из опыта изучения элементов теории графов на факультативных занятиях в 7 классах.'''

'''Цель занятий''' – познакомить с основными понятиями теории графов в определенной последовательности

и показать применение метода к решению различных задач прикладного и занимательного характера.

'''''Проводимый в школе факультатив был рассчитан на 11 часов и строился по следующему плану:'''''

'''1.''' Введение понятия графа. Знакомство с биографией Леонарда Эйлера. (2 часа)

'''2.''' Основные виды графов Связность, цепи, головоломки. (2 часа)

'''3.''' Применение графов к решению логических задач. (3 часа)

'''4.''' Плоские графы. Изоморфные графы. Проблема 4-х красок. (2 часа)

'''5.''' Отношения и графы. (1 час)

'''6.''' Контрольная работа (1 час)

<pre>Учащиеся знакомятся со многими новыми понятиями и определениями, на многочисленных примерах были проиллюстрированы эти

понятия и свойства. Школьники проявляют большой интерес к теории при ее приложении в игровых ситуациях.

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

свойств, играют важную роль в овладении теорией. Занятия имеют большую эффективность, если проходят в форме

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

От занятия к занятию учащиеся все свободнее овладевали языком теории графов, нередко вносили интересные предложения по

решению задач. С большим интересом школьники отнеслись к решению логических задач, которые, как и многие другие задачи

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

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

потом оценить достоинства и недостатки каждого из них.

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

решению задач, помогает им свободнее пользоваться различными языковыми средствами математики.</pre>

''В основу программы была положена книга О. Оре'' '''«Графы и их применение», «Теория графов».'''

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

Семинар ДООМ "Из опыта изучения элементов теории графов."

2007-12-05T13:33:32Z

Егорчева Светлана Валентиновна:

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

'''Из опыта изучения элементов теории графов на факультативных занятиях в 7 классах.'''

'''Цель занятий''' – познакомить с основными понятиями теории графов в определенной последовательности и показать применение метода к решению различных задач прикладного и занимательного характера.

'''''Проводимый в школе факультатив был рассчитан на 11 часов и строился по следующему плану:'''''

'''1.''' Введение понятия графа. Знакомство с биографией Леонарда Эйлера. (2 часа)

'''2.''' Основные виды графов Связность, цепи, головоломки. (2 часа)

'''3.''' Применение графов к решению логических задач. (3 часа)

'''4.''' Плоские графы. Изоморфные графы. Проблема 4-х красок. (2 часа)

'''5.''' Отношения и графы. (1 час)

'''6.''' Контрольная работа (1 час)

<pre>Учащиеся знакомятся со многими новыми понятиями и определениями, на многочисленных примерах были проиллюстрированы эти

понятия и свойства. Школьники проявляют большой интерес к теории при ее приложении в игровых ситуациях.

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

свойств, играют важную роль в овладении теорией. Занятия имеют большую эффективность, если проходят в форме

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

От занятия к занятию учащиеся все свободнее овладевали языком теории графов, нередко вносили интересные предложения по

решению задач. С большим интересом школьники отнеслись к решению логических задач, которые, как и многие другие задачи

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

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

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

решению задач, помогает им свободнее пользоваться различными языковыми средствами математики.</pre>

''В основу программы была положена книга О. Оре'' '''«Графы и их применение», «Теория графов».'''
[[Категория:Проект ДООМ]]

Семинар ДООМ "Из опыта изучения элементов теории графов."

2007-12-05T13:31:33Z

Егорчева Светлана Валентиновна:

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

'''Из опыта изучения элементов теории графов на факультативных занятиях в 7 классах.'''

'''Цель занятий''' – познакомить с основными понятиями теории графов в определенной последовательности и показать применение метода к решению различных задач прикладного и занимательного характера.

'''''Проводимый в школе факультатив был рассчитан на 11 часов и строился по следующему плану:'''''

'''1.''' Введение понятия графа. Знакомство с биографией Леонарда Эйлера. (2 часа)

'''2.''' Основные виды графов Связность, цепи, головоломки. (2 часа)

'''3.''' Применение графов к решению логических задач. (3 часа)

'''4.''' Плоские графы. Изоморфные графы. Проблема 4-х красок. (2 часа)

'''5.''' Отношения и графы. (1 час)

'''6.''' Контрольная работа (1 час)

Учащиеся знакомятся со многими новыми понятиями и определениями, на многочисленных примерах были проиллюстрированы эти понятия и свойства. Школьники проявляют большой интерес к теории при ее приложении в игровых ситуациях. Необходимо постоянно показывать практическое применение графов. Разнообразные упражнения, вскрывающие суть понятий и свойств, играют важную роль в овладении теорией. Занятия имеют большую эффективность, если проходят в форме непосредственной беседы учителя с учениками. На каждом занятии в той или иной форме проводилось повторение материала. От занятия к занятию учащиеся все свободнее овладевали языком теории графов, нередко вносили интересные предложения по решению задач. С большим интересом школьники отнеслись к решению логических задач, которые, как и многие другие задачи курса, носили занимательный характер. У ребят были трудности при выборе формы графа, ведь не всегда просто составить ветви, соответствующие определенным условиям. Учащимся предлагалось одну и ту же задачу решить различными способами, а потом оценить достоинства и недостатки каждого из них.
Теория графов вызывает интерес у учащихся, развивает у них навыки абстрактного и логического мышления, творческий подход к решению задач, помогает им свободнее пользоваться различными языковыми средствами математики.
''В основу программы была положена книга О. Оре'' '''«Графы и их применение», «Теория графов».'''
[[Категория:Проект ДООМ]]

Семинар ДООМ "Из опыта изучения элементов теории графов."

2007-12-05T13:30:07Z

Егорчева Светлана Валентиновна:

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

'''Из опыта изучения элементов теории графов на факультативных занятиях в 7 классах.'''

'''Цель занятий''' – познакомить с основными понятиями теории графов в определенной последовательности и показать применение метода к решению различных задач прикладного и занимательного характера.

'''''Проводимый в школе факультатив был рассчитан на 11 часов и строился по следующему плану:'''''

'''1.''' Введение понятия графа. Знакомство с биографией Леонарда Эйлера. (2 часа)

'''2.''' Основные виды графов Связность, цепи, головоломки. (2 часа)

'''3.''' Применение графов к решению логических задач. (3 часа)

'''4.''' Плоские графы. Изоморфные графы. Проблема 4-х красок. (2 часа)

'''5.''' Отношения и графы. (1 час)

'''6.''' Контрольная работа (1 час)

Учащиеся знакомятся со многими новыми понятиями и определениями, на многочисленных примерах были проиллюстрированы эти понятия и свойства. Школьники проявляют большой интерес к теории при ее приложении в игровых ситуациях. Необходимо постоянно показывать практическое применение графов. Разнообразные упражнения, вскрывающие суть понятий и свойств, играют важную роль в овладении теорией. Занятия имеют большую эффективность, если проходят в форме непосредственной беседы учителя с учениками. На каждом занятии в той или иной форме проводилось повторение материала. От занятия к занятию учащиеся все свободнее овладевали языком теории графов, нередко вносили интересные предложения по решению задач. С большим интересом школьники отнеслись к решению логических задач, которые, как и многие другие задачи курса, носили занимательный характер. У ребят были трудности при выборе формы графа, ведь не всегда просто составить ветви, соответствующие определенным условиям. Учащимся предлагалось одну и ту же задачу решить различными способами, а потом оценить достоинства и недостатки каждого из них.

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

В основу программы была положена книга О. Оре «Графы и их применение», «Теория графов».
[[Категория:Проект ДООМ]]

Семинар ДООМ "Из опыта изучения элементов теории графов."

2007-12-02T18:55:34Z

Егорчева Светлана Валентиновна:

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

'''Из опыта изучения элементов теории графов на факультативных занятиях в 7 классах.'''

'''Цель занятий''' – познакомить с основными понятиями теории графов в определенной последовательности и показать применение метода к решению различных задач прикладного и занимательного характера.

'''''Проводимый в школе факультатив был рассчитан на 11 часов и строился по следующему плану:'''''

'''1.''' Введение понятия графа. Знакомство с биографией Леонарда Эйлера. (2 часа)

'''2.''' Основные виды графов Связность, цепи, головоломки. (2 часа)

'''3.''' Применение графов к решению логических задач. (3 часа)

'''4.''' Плоские графы. Изоморфные графы. Проблема 4-х красок. (2 часа)

'''5.''' Отношения и графы. (1 час)

'''6.''' Контрольная работа (1 час)

Учащиеся знакомятся со многими новыми понятиями и определениями, на многочисленных примерах были проиллюстрированы эти понятия и свойства. Школьники проявляют большой интерес к теории при ее приложении в игровых ситуациях. Необходимо постоянно показывать практическое применение графов. Разнообразные упражнения, вскрывающие суть понятий и свойств, играют важную роль в овладении теорией. Занятия имеют большую эффективность, если проходят в форме непосредственной беседы учителя с учениками. На каждом занятии в той или иной форме проводилось повторение материала. От занятия к занятию учащиеся все свободнее овладевали языком теории графов, нередко вносили интересные предложения по решению задач. С большим интересом школьники отнеслись к решению логических задач, которые, как и многие другие задачи курса, носили занимательный характер. У ребят были трудности при выборе формы графа, ведь не всегда просто составить ветви, соответствующие определенным условиям. Учащимся предлагалось одну и ту же задачу решить различными способами, а потом оценить достоинства и недостатки каждого из них.
Теория графов вызывает интерес у учащихся, развивает у них навыки абстрактного и логического мышления, творческий подход к решению задач, помогает им свободнее пользоваться различными языковыми средствами математики.

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

Семинар ДООМ "Из опыта изучения элементов теории графов."

2007-12-02T18:53:58Z

Егорчева Светлана Валентиновна:

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

'''Из опыта изучения элементов теории графов на факультативных занятиях в 7 классах.'''

'''Цель занятий''' – познакомить с основными понятиями теории графов в определенной последовательности и показать применение метода к решению различных задач прикладного и занимательного характера.

'''''Проводимый в школе факультатив был рассчитан на 11 часов и строился по следующему плану:'''''

'''1.''' Введение понятия графа. Знакомство с биографией Леонарда Эйлера. 2 часа

'''2.''' Основные виды графов Связность, цепи, головоломки. 2 часа

'''3.''' Применение графов к решению логических задач. 3 часа

'''4.''' Плоские графы. Изоморфные графы. Проблема 4-х красок. 2 часа

'''5.''' Отношения и графы. 1 час

'''6.''' Контрольная работа 1 час

Учащиеся знакомятся со многими новыми понятиями и определениями, на многочисленных примерах были проиллюстрированы эти понятия и свойства. Школьники проявляют большой интерес к теории при ее приложении в игровых ситуациях. Необходимо постоянно показывать практическое применение графов. Разнообразные упражнения, вскрывающие суть понятий и свойств, играют важную роль в овладении теорией. Занятия имеют большую эффективность, если проходят в форме непосредственной беседы учителя с учениками. На каждом занятии в той или иной форме проводилось повторение материала. От занятия к занятию учащиеся все свободнее овладевали языком теории графов, нередко вносили интересные предложения по решению задач. С большим интересом школьники отнеслись к решению логических задач, которые, как и многие другие задачи курса, носили занимательный характер. У ребят были трудности при выборе формы графа, ведь не всегда просто составить ветви, соответствующие определенным условиям. Учащимся предлагалось одну и ту же задачу решить различными способами, а потом оценить достоинства и недостатки каждого из них.
Теория графов вызывает интерес у учащихся, развивает у них навыки абстрактного и логического мышления, творческий подход к решению задач, помогает им свободнее пользоваться различными языковыми средствами математики.

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

Семинар ДООМ "Применение графов к решению логических задач."

2007-12-02T18:50:53Z

Егорчева Светлана Валентиновна:

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

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

'''Задача 1.'''

Из трех человек, стоящих рядом, один всегда говорит правду (правдивый), другой всегда лжет (лжец), а третий, смотря по обстоятельствам, говорит правду или ложь («дипломат»). У стоящего слева спросили: «Кто стоит рядом с тобой?» Он ответил: «Правдолюб». Стоящему в центре, задали вопрос: «Кто ты?», и он ответил: «Я дипломат». Когда у стоящего справа спросили: «Кто стоит рядом с тобой?», он ответил: «Лжец». Кто где стоял?
Если в данной задаче ребро графа будет соответствовать месту, занимаемому тем или иным человеком, то нам могут представиться следующие возможности.

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

'''Решение:'''

Рассмотрим первую возможность. Если «правдолюб» стоит слева, то рядом с ним, судя по его ответу, находится «правдолюб». У нас же стоит лжец. Рассмотрев таким образом все остальные возможности, мы придем к выводу, что расстановка «дипломат», «лжец», «правдолюб» удовлетворяет задаче. Действительно, если «правдолюб» стоит справа, то, по его ответу, рядом с ним «лжец», что выполняется. Стоящий в центре заявляет, что он «дипломат», и следовательно, лжет, а стоящий справа также лжет. Таким образом все условия задачи выполнены. В качестве задачи второго типа можно предложить следующую.

'''Задача 2.'''

В пяти корзинах лежали яблоки пяти разных сортов. Яблоки первого сорта лежат в корзинах Г и Д; яблоки второго сорта - в корзинах А. Б, Г; в корзинах А, Б, В имеются яблоки пятого сорта, в корзине В имеются к тому же яблоки четвертого сорта, а в корзине Д-третьего. Пронумеруйте каждую корзину так, чтобы в корзине №1 были яблоки первого сорта (хотя бы одно); в корзине № 2-второго и т.д.

'''Решение:''' Составим граф:

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

''' Ответ:''' №1-Г; №2-А или №2-Б; №3-Д; №4-В; №5-Б или №5-А
Возникает вопрос: так ли уж нужны были графы в этой задаче? Разве нельзя прийти к решению логическим путем? Можно, но графы придали условия наглядность, упростили решение.

'''Задача 3.'''

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

'''Решение:'''

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

Решение этой задачи достигается построением следующего графа, где каждая вершина обозначает соответствующую газету и соответственно 5 подписчиков, а каждое ребро будет соответствовать одному подписчику.
Суть метода решения этой и подобных ей задач состоит в установлении связей между множеством вершин и множеством ребер графа.
Следовательно, в данной задаче предприниматели выписывают шесть наименований газет. Всего предпринимателей:
6*(6-1)/2=15 чел.
Полезно решать логические задачи разными методами. Например, следующую задачу можно решить способом логических квадратов и с помощью графов.

'''Задача 3.'''

Три ученицы - Аня, Валя. Катя - участвовали в новогоднем бале - маскараде. Одна из них была в красном костюме, другая - в белом, третья - в синем. Если сказать, что Аня была в красном, Валя – не в красном, и Катя –не в синем, то одно из этих утверждений будет верным, а два других –неверными. В каком костюме была каждая из учениц?

'''Решение:'''

Логический квадрат для этого случая имеет вид:

Аня Валя Катя
Красное 0 1 0
Белое 0 0 1
Синее 1 0 0

Графы для этой задачи имеют вид.

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

И в том, и в другом случае получаем ответ: Валя была в красном платье, Катя – в белом и Аня - в синем.
Ребята оценивают достоинства и недостатки каждого из этих способов.

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

Файл:R444.gif

2007-12-02T18:46:07Z

Егорчева Светлана Валентиновна:

Файл:R333.gif

2007-12-02T18:45:25Z

Егорчева Светлана Валентиновна:

Файл:R222.gif

2007-12-02T18:44:23Z

Егорчева Светлана Валентиновна:

Файл:R111.gif

2007-12-02T18:43:53Z

Егорчева Светлана Валентиновна:

Семинар ДООМ "Основные понятия теории графов."

2007-12-02T18:34:13Z

Егорчева Светлана Валентиновна:

[[участник: Трифонова Валентина Артемьевна, 022.]]

'''ЦЕЛИ:'''

познакомиться с определением графов и его сопутствующими понятиями ;

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

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

<h2><font color="A52A2A">'''ХОД УРОКА:'''</font></h2>

''Рассмотрим следующую задачу:''

<pre>Между планетами введено космическое сообщение по следующим маршрутам:

З-К, П-В, З-П, П-К, У-М, М-С, С-Ю, Ю-М, М-У. Можно ли добраться с З до М?</pre>

'''РЕШЕНИЕ:'''

Попробуем решить эту задачу графически, изобразим схему-чертеж маршрутов, где точками обозначим

названия пунктов З, К, П, В и т.д, а отрезками - их соединяющие маршруты. Получается следующий чертеж: (рис.1)

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

(рис.1)

Глядя на него можно ответить, что от З до М добраться нельзя.

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

<h5><font color="A52A2A">'''ОПРЕДЕЛЕНИЕ:

ГРАФОМ называются схемы, состоящие из точек (вершины графов) и соединяющих эти точки отрезков, прямых или кривых (ребра графов)'''.</font></h5>

Приведите примеры, где в жизни мы встречаемся с графами? (схемы маршрутов рейсовых автобусов, городской метрополитен, элементы электрических цепей и т.д.)
Графы упрощают решение многих логических задач, экономических, физических и других.
Графы имеют разные виды: их можно изобразить в виде геометрической фигуры, прямоугольника, окружности, овала, в виде дерева, в виде леса, в виде плоской фигуры.
Рассмотрим процесс соединения вершин графа ребрами.
Схема, состоящая из изолированных вершин, несоединенных ребрами, называется нулевым графом. Графы, в которых не построены все возможные ребра, называется неполным. Графы, в которых построены все возможные ребра , называется полным. В полном графе число ребер равно: n(n-1)\2, где n-число вершин графа. Каждая вершина в графе имеет свою степень. Степенью вершины графа называется число, соответствующее количеству ребер графа, исходящих из данной вершины. Вершина называется четной, если степень этой вершины четная и нечетной, если она нечетная.

<h4><font color="blue">'''Сформулируем некоторые закономерности, присущие определенным графам:'''</font> </h4>

'''1)''' Степени вершин полного графа одинаковы, и каждая из них на 1 меньше числа вершин этого графа.

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

'''3)''' Если степени всех вершин графа равны, то граф называется однородным.

'''4)''' Число нечетных вершин любого графа четно.

'''5)''' Невозможно начертить граф с нечетным числом нечетных вершин.

'''6)''' Если все вершины графа четные, то можно не отрывая карандаш от бумаги, проведя по каждому ребру только один раз, начертить этот граф, причем движение можно начать с любой вершины. Такой граф называется уникурсальным.

'''7)''' Граф, имеющий две нечетные вершины, можно начертить, не отрывая карандаша от бумаги, начав движение с одной из нечетных вершин.

'''8)''' Граф, имеющий более двух нечетных вершин, невозможно начертить, не отрывая карандаша от бумаги.

<h4><font color="blue">'''Разберем еще некоторые понятия, необходимые для решения задач, используя графы.'''</font></h4>

<h5><font color="A52A2A">'''Путем'''</font></h5>в графе от одной вершины до другой называется такая последовательность ребер, соединяющих вершины, что никакое ребро при движении не повторяется дважды.

<h5><font color="A52A2A">'''Циклом'''</font></h5>называется путь, в котором начало и конец совпадают. Если все вершины графа имеют разную степень, то такой цикл называется элементарным. Если цикл, включает в себя все ребра по одному разу, то цикл называется Эйлеровой линией.
Две вершины графа называются связными, если в графе существует путь с концами в этих вершинах. Если такого пути нет , то граф несвязный.

<h5><font color="A52A2A">'''Деревом'''</font></h5>называется любой связный граф , не имеющий циклов. Для каждой пары вершин дерева существует единственный путь, их соединяющий.
(рис.2)

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

''Рассмотрим задачу, которую легко можно решить, используя теорию графов.''

'''ЗАДАЧА.'''

<pre>Красный, синий, желтый и зеленый карандаши лежат в четырех коробках по одному.

Цвет карандаша отличается от цвета коробки. Известно, что зеленый карандаш лежит в синей коробке,

а красный не лежит в желтой. В какой коробке лежит каждый карандаш?</pre>

'''РЕШЕНИЕ:'''

<pre>обозначим точками карандаши и коробки. Сплошная линия будет обозначать, что карандаш лежит в соответствующей коробке,

пунктирная – не лежит.(рис 4). Затем достраиваем граф по следующему правилу: т.к. в коробке лежит только один карандаш,

то из каждой точки должны выходить одна сплошная и три пунктирные линии. (рис5), который и дает решение задачи.</pre>

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

''Для следующей задачи постройте граф, соответствующей решению задачи.''

'''ЗАДАЧА.'''

<pre>В первенстве по теннису принимали участие 6 ребят: Андрей, Борис, Виктор, Галина, Дмитрий и Елена.

Первенство проводилось по круговой схеме: каждый из участников играет с каждым из остальных один раз.

Некоторые игры уже проведены: Андрей играл с Борисом, Галиной и Еленой, Виктор с Галиной, Дмитрием и Еленой.

Сколько пар проведено и сколько еще осталось?</pre>

'''РЕШЕНИЕ:'''

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

<pre> Изобразим данные задачи в виде схемы. Участники – это точки,

сплошные линии – это сыгранные партии, пунктирные линии – это несыгранные партии. Следовательно ,

проведено 7 игр, осталось провести – 8 игр.</pre>

'''ДОМАШНЕЕ ЗАДАНИЕ:'''

Решите с помощью графов.

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

<pre>В семье четверо детей, им - 5, 8, 13, 15 лет, а зовут их Таня, Юра, Света и Лена.

Одна девочка ходит в детский сад, Таня старше Юры, а сумма лет Тани и Светы делится на три.

Сколько лет Лене?

'''Ответ:''' Юре – 8 лет, Тане – 13 лет, Свете -5 лет, Лене – 15 лет. </pre>

Урок составила Трифонова В.А. команды 022, г. Казани. Этот урок можно провести как в 5, так и в 11 классах, так как он вводит ребят в теорию графов.

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

Семинар ДООМ "Основные понятия теории графов."

2007-12-02T18:33:11Z

Егорчева Светлана Валентиновна:

[[участник: Трифонова Валентина Артемьевна, 022.]]

'''ЦЕЛИ:'''

познакомиться с определением графов и его сопутствующими понятиями ;

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

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

<h2><font color="A52A2A">'''ХОД УРОКА:'''</font></h2>

''Рассмотрим следующую задачу:''

<pre>Между планетами введено космическое сообщение по следующим маршрутам:

З-К, П-В, З-П, П-К, У-М, М-С, С-Ю, Ю-М, М-У. Можно ли добраться с З до М?</pre>

'''РЕШЕНИЕ:'''

Попробуем решить эту задачу графически, изобразим схему-чертеж маршрутов, где точками обозначим

названия пунктов З, К, П, В и т.д, а отрезками - их соединяющие маршруты. Получается следующий чертеж: (рис.1)

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

(рис.1)

Глядя на него можно ответить, что от З до М добраться нельзя.

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

<h5><font color="A52A2A">'''ОПРЕДЕЛЕНИЕ: ГРАФОМ называются схемы, состоящие из точек (вершины графов) и соединяющих эти точки отрезков, прямых или кривых (ребра графов).</font></h5>

Приведите примеры, где в жизни мы встречаемся с графами? (схемы маршрутов рейсовых автобусов, городской метрополитен, элементы электрических цепей и т.д.)
Графы упрощают решение многих логических задач, экономических, физических и других.
Графы имеют разные виды: их можно изобразить в виде геометрической фигуры, прямоугольника, окружности, овала, в виде дерева, в виде леса, в виде плоской фигуры.
Рассмотрим процесс соединения вершин графа ребрами.
Схема, состоящая из изолированных вершин, несоединенных ребрами, называется нулевым графом. Графы, в которых не построены все возможные ребра, называется неполным. Графы, в которых построены все возможные ребра , называется полным. В полном графе число ребер равно: n(n-1)\2, где n-число вершин графа. Каждая вершина в графе имеет свою степень. Степенью вершины графа называется число, соответствующее количеству ребер графа, исходящих из данной вершины. Вершина называется четной, если степень этой вершины четная и нечетной, если она нечетная.

<h4><font color="blue">'''Сформулируем некоторые закономерности, присущие определенным графам:'''</font> </h4>

'''1)''' Степени вершин полного графа одинаковы, и каждая из них на 1 меньше числа вершин этого графа.

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

'''3)''' Если степени всех вершин графа равны, то граф называется однородным.

'''4)''' Число нечетных вершин любого графа четно.

'''5)''' Невозможно начертить граф с нечетным числом нечетных вершин.

'''6)''' Если все вершины графа четные, то можно не отрывая карандаш от бумаги, проведя по каждому ребру только один раз, начертить этот граф, причем движение можно начать с любой вершины. Такой граф называется уникурсальным.

'''7)''' Граф, имеющий две нечетные вершины, можно начертить, не отрывая карандаша от бумаги, начав движение с одной из нечетных вершин.

'''8)''' Граф, имеющий более двух нечетных вершин, невозможно начертить, не отрывая карандаша от бумаги.

<h4><font color="blue">'''Разберем еще некоторые понятия, необходимые для решения задач, используя графы.'''</font></h4>

<h5><font color="A52A2A">'''Путем'''</font></h5>в графе от одной вершины до другой называется такая последовательность ребер, соединяющих вершины, что никакое ребро при движении не повторяется дважды.

<h5><font color="A52A2A">'''Циклом'''</font></h5>называется путь, в котором начало и конец совпадают. Если все вершины графа имеют разную степень, то такой цикл называется элементарным. Если цикл, включает в себя все ребра по одному разу, то цикл называется Эйлеровой линией.
Две вершины графа называются связными, если в графе существует путь с концами в этих вершинах. Если такого пути нет , то граф несвязный.

<h5><font color="A52A2A">'''Деревом'''</font></h5>называется любой связный граф , не имеющий циклов. Для каждой пары вершин дерева существует единственный путь, их соединяющий.
(рис.2)

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

''Рассмотрим задачу, которую легко можно решить, используя теорию графов.''

'''ЗАДАЧА.'''

<pre>Красный, синий, желтый и зеленый карандаши лежат в четырех коробках по одному.

Цвет карандаша отличается от цвета коробки. Известно, что зеленый карандаш лежит в синей коробке,

а красный не лежит в желтой. В какой коробке лежит каждый карандаш?</pre>

'''РЕШЕНИЕ:'''

<pre>обозначим точками карандаши и коробки. Сплошная линия будет обозначать, что карандаш лежит в соответствующей коробке,

пунктирная – не лежит.(рис 4). Затем достраиваем граф по следующему правилу: т.к. в коробке лежит только один карандаш,

то из каждой точки должны выходить одна сплошная и три пунктирные линии. (рис5), который и дает решение задачи.</pre>

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

''Для следующей задачи постройте граф, соответствующей решению задачи.''

'''ЗАДАЧА.'''

<pre>В первенстве по теннису принимали участие 6 ребят: Андрей, Борис, Виктор, Галина, Дмитрий и Елена.

Первенство проводилось по круговой схеме: каждый из участников играет с каждым из остальных один раз.

Некоторые игры уже проведены: Андрей играл с Борисом, Галиной и Еленой, Виктор с Галиной, Дмитрием и Еленой.

Сколько пар проведено и сколько еще осталось?</pre>

'''РЕШЕНИЕ:'''

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

<pre> Изобразим данные задачи в виде схемы. Участники – это точки,

сплошные линии – это сыгранные партии, пунктирные линии – это несыгранные партии. Следовательно ,

проведено 7 игр, осталось провести – 8 игр.</pre>

'''ДОМАШНЕЕ ЗАДАНИЕ:'''

Решите с помощью графов.

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

<pre>В семье четверо детей, им - 5, 8, 13, 15 лет, а зовут их Таня, Юра, Света и Лена.

Одна девочка ходит в детский сад, Таня старше Юры, а сумма лет Тани и Светы делится на три.

Сколько лет Лене?

'''Ответ:''' Юре – 8 лет, Тане – 13 лет, Свете -5 лет, Лене – 15 лет. </pre>

Урок составила Трифонова В.А. команды 022, г. Казани. Этот урок можно провести как в 5, так и в 11 классах, так как он вводит ребят в теорию графов.

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

Семинар ДООМ "Основные понятия теории графов."

2007-12-02T18:30:08Z

Егорчева Светлана Валентиновна:

[[участник: Трифонова Валентина Артемьевна, 022.]]

'''ЦЕЛИ:'''

познакомиться с определением графов и его сопутствующими понятиями ;

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

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

<h2><font color="A52A2A">'''ХОД УРОКА:'''</font></h2>

''Рассмотрим следующую задачу:''

<pre>Между планетами введено космическое сообщение по следующим маршрутам:

З-К, П-В, З-П, П-К, У-М, М-С, С-Ю, Ю-М, М-У. Можно ли добраться с З до М?</pre>

'''РЕШЕНИЕ:'''

Попробуем решить эту задачу графически, изобразим схему-чертеж маршрутов, где точками обозначим

названия пунктов З, К, П, В и т.д, а отрезками - их соединяющие маршруты. Получается следующий чертеж: (рис.1)

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

(рис.1)

Глядя на него можно ответить, что от З до М добраться нельзя.

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

<pre>ОПРЕДЕЛЕНИЕ: ГРАФОМ называются схемы, состоящие из точек (вершины графов) и соединяющих эти точки отрезков,

прямых или кривых (ребра графов).</pre>

Приведите примеры, где в жизни мы встречаемся с графами? (схемы маршрутов рейсовых автобусов, городской метрополитен, элементы электрических цепей и т.д.)
Графы упрощают решение многих логических задач, экономических, физических и других.
Графы имеют разные виды: их можно изобразить в виде геометрической фигуры, прямоугольника, окружности, овала, в виде дерева, в виде леса, в виде плоской фигуры.
Рассмотрим процесс соединения вершин графа ребрами.
Схема, состоящая из изолированных вершин, несоединенных ребрами, называется нулевым графом. Графы, в которых не построены все возможные ребра, называется неполным. Графы, в которых построены все возможные ребра , называется полным. В полном графе число ребер равно: n(n-1)\2, где n-число вершин графа. Каждая вершина в графе имеет свою степень. Степенью вершины графа называется число, соответствующее количеству ребер графа, исходящих из данной вершины. Вершина называется четной, если степень этой вершины четная и нечетной, если она нечетная.

<h4><font color="blue">'''Сформулируем некоторые закономерности, присущие определенным графам:'''</font> </h4>

'''1)''' Степени вершин полного графа одинаковы, и каждая из них на 1 меньше числа вершин этого графа.

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

'''3)''' Если степени всех вершин графа равны, то граф называется однородным.

'''4)''' Число нечетных вершин любого графа четно.

'''5)''' Невозможно начертить граф с нечетным числом нечетных вершин.

'''6)''' Если все вершины графа четные, то можно не отрывая карандаш от бумаги, проведя по каждому ребру только один раз, начертить этот граф, причем движение можно начать с любой вершины. Такой граф называется уникурсальным.

'''7)''' Граф, имеющий две нечетные вершины, можно начертить, не отрывая карандаша от бумаги, начав движение с одной из нечетных вершин.

'''8)''' Граф, имеющий более двух нечетных вершин, невозможно начертить, не отрывая карандаша от бумаги.

<h4><font color="blue">'''Разберем еще некоторые понятия, необходимые для решения задач, используя графы.'''</font></h4>

<h5><font color="A52A2A">'''Путем'''</font></h5>в графе от одной вершины до другой называется такая последовательность ребер, соединяющих вершины, что никакое ребро при движении не повторяется дважды.

<h5><font color="A52A2A">'''Циклом'''</font></h5>называется путь, в котором начало и конец совпадают. Если все вершины графа имеют разную степень, то такой цикл называется элементарным. Если цикл, включает в себя все ребра по одному разу, то цикл называется Эйлеровой линией.
Две вершины графа называются связными, если в графе существует путь с концами в этих вершинах. Если такого пути нет , то граф несвязный.

<h5><font color="A52A2A">'''Деревом'''</font></h5>называется любой связный граф , не имеющий циклов. Для каждой пары вершин дерева существует единственный путь, их соединяющий.
(рис.2)

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

''Рассмотрим задачу, которую легко можно решить, используя теорию графов.''

'''ЗАДАЧА.'''

<pre>Красный, синий, желтый и зеленый карандаши лежат в четырех коробках по одному.

Цвет карандаша отличается от цвета коробки. Известно, что зеленый карандаш лежит в синей коробке,

а красный не лежит в желтой. В какой коробке лежит каждый карандаш?</pre>

'''РЕШЕНИЕ:'''

<pre>обозначим точками карандаши и коробки. Сплошная линия будет обозначать, что карандаш лежит в соответствующей коробке,

пунктирная – не лежит.(рис 4). Затем достраиваем граф по следующему правилу: т.к. в коробке лежит только один карандаш,

то из каждой точки должны выходить одна сплошная и три пунктирные линии. (рис5), который и дает решение задачи.</pre>

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

''Для следующей задачи постройте граф, соответствующей решению задачи.''

'''ЗАДАЧА.'''

<pre>В первенстве по теннису принимали участие 6 ребят: Андрей, Борис, Виктор, Галина, Дмитрий и Елена.

Первенство проводилось по круговой схеме: каждый из участников играет с каждым из остальных один раз.

Некоторые игры уже проведены: Андрей играл с Борисом, Галиной и Еленой, Виктор с Галиной, Дмитрием и Еленой.

Сколько пар проведено и сколько еще осталось?</pre>

'''РЕШЕНИЕ:'''

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

<pre> Изобразим данные задачи в виде схемы. Участники – это точки,

сплошные линии – это сыгранные партии, пунктирные линии – это несыгранные партии. Следовательно ,

проведено 7 игр, осталось провести – 8 игр.</pre>

'''ДОМАШНЕЕ ЗАДАНИЕ:'''

Решите с помощью графов.

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

<pre>В семье четверо детей, им - 5, 8, 13, 15 лет, а зовут их Таня, Юра, Света и Лена.

Одна девочка ходит в детский сад, Таня старше Юры, а сумма лет Тани и Светы делится на три.

Сколько лет Лене?

'''Ответ:''' Юре – 8 лет, Тане – 13 лет, Свете -5 лет, Лене – 15 лет. </pre>

Урок составила Трифонова В.А. команды 022, г. Казани. Этот урок можно провести как в 5, так и в 11 классах, так как он вводит ребят в теорию графов.

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

Семинар ДООМ "Основные понятия теории графов."

2007-12-02T18:28:09Z

Егорчева Светлана Валентиновна:

[[участник: Трифонова Валентина Артемьевна, 022.]]

'''ЦЕЛИ:'''

познакомиться с определением графов и его сопутствующими понятиями ;

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

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

<h2><font color="A52A2A">'''ХОД УРОКА:'''</font></h2>

''Рассмотрим следующую задачу:''

<pre>Между планетами введено космическое сообщение по следующим маршрутам:

З-К, П-В, З-П, П-К, У-М, М-С, С-Ю, Ю-М, М-У. Можно ли добраться с З до М?</pre>

'''РЕШЕНИЕ:'''

Попробуем решить эту задачу графически, изобразим схему-чертеж маршрутов, где точками обозначим

названия пунктов З, К, П, В и т.д, а отрезками - их соединяющие маршруты. Получается следующий чертеж: (рис.1)

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

(рис.1)

Глядя на него можно ответить, что от З до М добраться нельзя.

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

<pre>ОПРЕДЕЛЕНИЕ: ГРАФОМ называются схемы, состоящие из точек (вершины графов) и соединяющих эти точки отрезков,

прямых или кривых (ребра графов).</pre>

Приведите примеры, где в жизни мы встречаемся с графами? (схемы маршрутов рейсовых автобусов, городской метрополитен, элементы электрических цепей и т.д.)
Графы упрощают решение многих логических задач, экономических, физических и других.
Графы имеют разные виды: их можно изобразить в виде геометрической фигуры, прямоугольника, окружности, овала, в виде дерева, в виде леса, в виде плоской фигуры.
Рассмотрим процесс соединения вершин графа ребрами.
Схема, состоящая из изолированных вершин, несоединенных ребрами, называется нулевым графом. Графы, в которых не построены все возможные ребра, называется неполным. Графы, в которых построены все возможные ребра , называется полным. В полном графе число ребер равно: n(n-1)\2, где n-число вершин графа. Каждая вершина в графе имеет свою степень. Степенью вершины графа называется число, соответствующее количеству ребер графа, исходящих из данной вершины. Вершина называется четной, если степень этой вершины четная и нечетной, если она нечетная.

<h4><font color="blue">'''Сформулируем некоторые закономерности, присущие определенным графам:'''</font> </h4>

'''1)''' Степени вершин полного графа одинаковы, и каждая из них на 1 меньше числа вершин этого графа.

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

'''3)''' Если степени всех вершин графа равны, то граф называется однородным.

'''4)''' Число нечетных вершин любого графа четно.

'''5)''' Невозможно начертить граф с нечетным числом нечетных вершин.

'''6)''' Если все вершины графа четные, то можно не отрывая карандаш от бумаги, проведя по каждому ребру только один раз, начертить этот граф, причем движение можно начать с любой вершины. Такой граф называется уникурсальным.

'''7)''' Граф, имеющий две нечетные вершины, можно начертить, не отрывая карандаша от бумаги, начав движение с одной из нечетных вершин.

'''8)''' Граф, имеющий более двух нечетных вершин, невозможно начертить, не отрывая карандаша от бумаги.

<h4><font color="blue">'''Разберем еще некоторые понятия, необходимые для решения задач, используя графы.'''</font></h4>

<h5><font color="A52A2A">'''Путем'''</font></h5>в графе от одной вершины до другой называется такая последовательность ребер, соединяющих вершины, что никакое ребро при движении не повторяется дважды.

<h5><font color="A52A2A">'''Циклом'''</font></h5>называется путь, в котором начало и конец совпадают. Если все вершины графа имеют разную степень, то такой цикл называется элементарным. Если цикл, включает в себя все ребра по одному разу, то цикл называется Эйлеровой линией.
Две вершины графа называются связными, если в графе существует путь с концами в этих вершинах. Если такого пути нет , то граф несвязный.

<h5><font color="A52A2A">'''Деревом'''</font></h5>называется любой связный граф , не имеющий циклов. Для каждой пары вершин дерева существует единственный путь, их соединяющий.
(рис.2)

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

(рис.2)
''Рассмотрим задачу, которую легко можно решить, используя теорию графов.''

'''ЗАДАЧА.'''

<pre>Красный, синий, желтый и зеленый карандаши лежат в четырех коробках по одному.

Цвет карандаша отличается от цвета коробки. Известно, что зеленый карандаш лежит в синей коробке,

а красный не лежит в желтой. В какой коробке лежит каждый карандаш?</pre>

'''РЕШЕНИЕ:'''

<pre>обозначим точками карандаши и коробки. Сплошная линия будет обозначать, что карандаш лежит в соответствующей коробке,

пунктирная – не лежит.(рис 4). Затем достраиваем граф по следующему правилу: т.к. в коробке лежит только один карандаш,

то из каждой точки должны выходить одна сплошная и три пунктирные линии. (рис5), который и дает решение задачи.

[[Изображение:risss4.gif]]</pre>

''Для следующей задачи постройте граф, соответствующей решению задачи.''

'''ЗАДАЧА.'''

<pre>В первенстве по теннису принимали участие 6 ребят: Андрей, Борис, Виктор, Галина, Дмитрий и Елена.

Первенство проводилось по круговой схеме: каждый из участников играет с каждым из остальных один раз.

Некоторые игры уже проведены: Андрей играл с Борисом, Галиной и Еленой, Виктор с Галиной, Дмитрием и Еленой.

Сколько пар проведено и сколько еще осталось?</pre>

'''РЕШЕНИЕ:'''

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

<pre> Изобразим данные задачи в виде схемы. Участники – это точки,

сплошные линии – это сыгранные партии, пунктирные линии – это несыгранные партии. Следовательно ,

проведено 7 игр, осталось провести – 8 игр.</pre>

'''ДОМАШНЕЕ ЗАДАНИЕ:'''

Решите с помощью графов.

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

<pre>В семье четверо детей, им - 5, 8, 13, 15 лет, а зовут их Таня, Юра, Света и Лена.

Одна девочка ходит в детский сад, Таня старше Юры, а сумма лет Тани и Светы делится на три.

Сколько лет Лене?

'''Ответ:''' Юре – 8 лет, Тане – 13 лет, Свете -5 лет, Лене – 15 лет. </pre>

Урок составила Трифонова В.А. команды 022, г. Казани. Этот урок можно провести как в 5, так и в 11 классах, так как он вводит ребят в теорию графов.

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

Семинар ДООМ "Основные понятия теории графов."

2007-12-02T18:25:38Z

Егорчева Светлана Валентиновна:

[[участник: Трифонова Валентина Артемьевна, 022.]]

'''ЦЕЛИ:'''

познакомиться с определением графов и его сопутствующими понятиями ;

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

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

<h2><font color="A52A2A">'''ХОД УРОКА:'''</font></h2>

''Рассмотрим следующую задачу:''

<pre>Между планетами введено космическое сообщение по следующим маршрутам:

З-К, П-В, З-П, П-К, У-М, М-С, С-Ю, Ю-М, М-У. Можно ли добраться с З до М?</pre>

'''РЕШЕНИЕ:'''

Попробуем решить эту задачу графически, изобразим схему-чертеж маршрутов, где точками обозначим

названия пунктов З, К, П, В и т.д, а отрезками - их соединяющие маршруты. Получается следующий чертеж: (рис.1)

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

(рис.1)

Глядя на него можно ответить, что от З до М добраться нельзя.

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

<pre>ОПРЕДЕЛЕНИЕ: ГРАФОМ называются схемы, состоящие из точек (вершины графов) и соединяющих эти точки отрезков,

прямых или кривых (ребра графов).</pre>

Приведите примеры, где в жизни мы встречаемся с графами? (схемы маршрутов рейсовых автобусов, городской метрополитен, элементы электрических цепей и т.д.)
Графы упрощают решение многих логических задач, экономических, физических и других.
Графы имеют разные виды: их можно изобразить в виде геометрической фигуры, прямоугольника, окружности, овала, в виде дерева, в виде леса, в виде плоской фигуры.
Рассмотрим процесс соединения вершин графа ребрами.
Схема, состоящая из изолированных вершин, несоединенных ребрами, называется нулевым графом. Графы, в которых не построены все возможные ребра, называется неполным. Графы, в которых построены все возможные ребра , называется полным. В полном графе число ребер равно: n(n-1)\2, где n-число вершин графа. Каждая вершина в графе имеет свою степень. Степенью вершины графа называется число, соответствующее количеству ребер графа, исходящих из данной вершины. Вершина называется четной, если степень этой вершины четная и нечетной, если она нечетная.

<h4><font color="blue">'''Сформулируем некоторые закономерности, присущие определенным графам:'''</font> </h4>

'''1)''' Степени вершин полного графа одинаковы, и каждая из них на 1 меньше числа вершин этого графа.

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

'''3)''' Если степени всех вершин графа равны, то граф называется однородным.

'''4)''' Число нечетных вершин любого графа четно.

'''5)''' Невозможно начертить граф с нечетным числом нечетных вершин.

'''6)''' Если все вершины графа четные, то можно не отрывая карандаш от бумаги, проведя по каждому ребру только один раз, начертить этот граф, причем движение можно начать с любой вершины. Такой граф называется уникурсальным.

'''7)''' Граф, имеющий две нечетные вершины, можно начертить, не отрывая карандаша от бумаги, начав движение с одной из нечетных вершин.

'''8)''' Граф, имеющий более двух нечетных вершин, невозможно начертить, не отрывая карандаша от бумаги.

<h4><font color="blue">'''Разберем еще некоторые понятия, необходимые для решения задач, используя графы.'''</font></h4>

<h5><font color="A52A2A">'''Путем'''</font></h5>в графе от одной вершины до другой называется такая последовательность ребер, соединяющих вершины, что никакое ребро при движении не повторяется дважды.

<h5><font color="A52A2A">'''Циклом'''</font></h5>называется путь, в котором начало и конец совпадают. Если все вершины графа имеют разную степень, то такой цикл называется элементарным. Если цикл, включает в себя все ребра по одному разу, то цикл называется Эйлеровой линией.
Две вершины графа называются связными, если в графе существует путь с концами в этих вершинах. Если такого пути нет , то граф несвязный.

<h5><font color="A52A2A">'''Деревом'''</font></h5>называется любой связный граф , не имеющий циклов. Для каждой пары вершин дерева существует единственный путь, их соединяющий.
(рис.2)

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

(рис.2)
''Рассмотрим задачу, которую легко можно решить, используя теорию графов.''

'''ЗАДАЧА.'''

<pre>Красный, синий, желтый и зеленый карандаши лежат в четырех коробках по одному.

Цвет карандаша отличается от цвета коробки. Известно, что зеленый карандаш лежит в синей коробке,

а красный не лежит в желтой. В какой коробке лежит каждый карандаш?</pre>

'''РЕШЕНИЕ:'''

<pre>обозначим точками карандаши и коробки. Сплошная линия будет обозначать, что карандаш лежит в соответствующей коробке,

пунктирная – не лежит.(рис 4). Затем достраиваем граф по следующему правилу: т.к. в коробке лежит только один карандаш,

то из каждой точки должны выходить одна сплошная и три пунктирные линии. (рис5), который и дает решение задачи.

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

(рис. 4) (рис.5)<pre>

''Для следующей задачи постройте граф, соответствующей решению задачи.''

'''ЗАДАЧА.'''

<pre>В первенстве по теннису принимали участие 6 ребят: Андрей, Борис, Виктор, Галина, Дмитрий и Елена.

Первенство проводилось по круговой схеме: каждый из участников играет с каждым из остальных один раз.

Некоторые игры уже проведены: Андрей играл с Борисом, Галиной и Еленой, Виктор с Галиной, Дмитрием и Еленой.

Сколько пар проведено и сколько еще осталось?</pre>

'''РЕШЕНИЕ:'''

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

(рис.6)<pre> Изобразим данные задачи в виде схемы. Участники – это точки,

сплошные линии – это сыгранные партии, пунктирные линии – это несыгранные партии. Следовательно ,

проведено 7 игр, осталось провести – 8 игр.</pre>

'''ДОМАШНЕЕ ЗАДАНИЕ:'''

Решите с помощью графов.

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

<pre>В семье четверо детей, им - 5, 8, 13, 15 лет, а зовут их Таня, Юра, Света и Лена.

Одна девочка ходит в детский сад, Таня старше Юры, а сумма лет Тани и Светы делится на три.

Сколько лет Лене?

'''Ответ:''' Юре – 8 лет, Тане – 13 лет, Свете -5 лет, Лене – 15 лет. </pre>

Урок составила Трифонова В.А. команды 022, г. Казани. Этот урок можно провести как в 5, так и в 11 классах, так как он вводит ребят в теорию графов.

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