Одним росчерком
В работе исследуются задачи , которые можно решать с использованием основ теории графов : задачи вида "одним росчерком" (вычерчивание фигур одной непрерывной линией) и задачи с лабиринтами.
Скачать:
| Вложение | Размер |
|---|---|
 referat._balashova_s.docx | 1.37 МБ |
 odnim_roscherkom._balashova_sofya.pptx | 1.44 МБ |
Предварительный просмотр:
Предварительный просмотр:
Подписи к слайдам:
Готовясь к олимпиадам по математике, мы решали задачи с такой формулировкой: «Начертите фигуру, не отрывая карандаша от бумаги и не проводя никакую линию дважды». Самая известная из этих задач – «Открытый конверт». Можно ли решить эти задачи не перебором, а другим, более быстрым, способом?
Цель работы: знакомство с простейшими математическими моделями. Задачи: выяснить, какие фигуры можно вычертить одним росчерком, а какие нельзя; понять, чем обусловлено такое различие фигур; узнать признаки, позволяющие установить заранее, поддаётся ли фигура вырисовыванию одним росчерком, и если поддаётся, то с какой точки следует начинать черчение; определить, существует ли другой класс задач, которые решаются аналогичным способом.
История вопроса
Задаче о кёнигсбергских мостах посвятил целое исследование великий швейцарский математик Леонард Эйлер. Результат этой работы он отправил в Петербургскую Академию наук в 1736 году. История вопроса Выстроив достаточно сложный алгоритм, Эйлер получил отрицательный ответ в задаче о мостах.
Для решения задачи о мостах Эйлер ввёл следующие определения: Граф – совокупность множества вершин и множества связей между ними (рёбер). Степень вершины – число рёбер, соединяющихся в данной вершине. Если степень вершины – чётное число, то такая вершина называется чётной . Если степень вершины – нечётное число, то вершина называется нечётной . Основные определения
В ходе рассуждений Эйлер пришёл к следующим выводам: не может существовать граф, у которого нечётное число нечётных вершин ; если все вершины графа чётные , то можно , не отрывая карандаша от бумаги, начертить граф ; при этом можно начинать от любой вершины графа и закончить его в той же вершине; граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.
На упрощённой схеме части города ( графе ) мостам соответствуют линии ( рёбра графа: a, b, c, d, e, f, g ), а частям города — точки соединения линий ( вершины графа: A, B, C, D ) . Задача о мостах
Граф мостов Кёнигсберга имел четыре нечётные вершины, следовательно, невозможно начертить его одним росчерком, то есть не получится пройти по всем мостам, не проходя ни по одному из них дважды. 3 3 3 5
Благодаря Леонарду Эйлеру существует общий прием решения подобных задач: преобразовать рисунок в граф (определить его вершины и рёбра); определить степень каждой вершины; посчитать количество нечётных вершин; сделать выводы: а) заданный обход возможен, если - все вершины чётные (его можно начать с любой вершины); - две вершины нечётные (его нужно начать с одной из нечётных вершин); б) заданный обход невозможен, если нечётных вершин больше двух; указать начало и конец пути.
Варианты задач Холодова О. А. Юным умникам и умницам. 2 класс Часть 2, стр. 30 (занятие 28) 4 4 4 4 2 2 2 2
Варианты задач Холодова О. А. Юным умникам и умницам. 3 класс Часть 2, стр. 25 (занятие 28) 3 3 2 4 4
Варианты задач Холодова О. А. Юным умникам и умницам. 2 класс Часть 1, стр. 20 (занятие 7) 3 3 3 3
Хотите попробовать?
Кроме задач такого вида этим способом можно решать задачи с лабиринтом . Можно ли обойти все данные комнаты, пройдя через каждую дверь ровно один раз и выйти на улицу через комнату 1 или 10? С какой комнаты надо начинать?
Пусть комнаты – вершины графа, а двери – ребра. Проверим степени вершин: Решение: Только две вершины имеют нечетную степень. Начать движение можно из комнаты 10, а закончить в комнате 8, либо наоборот.
Но, чтобы выйти на улицу (из комнаты 10), надо начинать из комнаты 8. В этом случае пройдём все двери один раз и попадём в комнату 10, но окажемся внутри комнаты, а не снаружи: Решение:
А это наши задачи! Задача 1 Можно ли в вотчине деда Мороза из въездных ворот попасть в Дом Деда Мороза, обойдя все тропинки ровно один раз?
Задача 2 Перед Новым годом Дед Мороз решил проверить порядок в комнатах 2 этажа своего дома. Вход на 2 этаж только один – через Комнату мастериц 1. Может ли Дед Мороз обойти все комнаты 2 этажа, проходя через каждую дверь только один раз, и попасть в свой рабочий кабинет? А это наши задачи!
Теория графов нашла очень широкое применение. Например, её используют при изучении транспортных и коммуникационных систем, в частности, для поиска и передачи данных в Интернете. Практическое применение теории графов
Великий математик Леонард Эйлер создал целое направление науки, решая задачу о семи мостах Кёнигсберга. Итоги работы:
Теперь мы умеем создавать простейшие математические модели для решения задач определенного вида. Существуют группы задач, которые можно решать с использованием графов. Чтобы определить, возможно ли начертить фигуру одним росчерком, достаточно определить степени вершин графа и сделать соответствующие выводы. Итоги работы:
ИСТОЧНИКИ: Перельман Я. И. , Одним росчерком – Ленинград: 1940. — 18 с. Материалы курса «Теория графов в занимательных историях». Преподаватель Огнева М. В. http://school.sgu.ru/course/view.php?id=45 Автор шаблона – Стрелкова Наталия Владимировна, http://infoteka.intergu.ru/query/about.asp?id=52755&r=222238488822384633715820 http://ru.wikipedia.org/wiki/%D0%AD%D0%B9%D0%BB%D0%B5%D1%80,_%D0%9B%D0%B5%D0%BE%D0%BD%D0%B0%D1%80%D0%B4 http://festival.1september.ru/articles/313706/ http :// www . poznovatelno . ru / opit / roscherk /162. html http://www.kakprosto.ru/kak-74625-kak-narisovat-figuru-ne-otryvaya-ruki http://worldofchildren.ru/to-kids/zadachi-i-golovolomki/1505-ne-otryvaya-karandasha http://www.liveinternet.ru/users/tatiana_khachko/post140113552/ http://sobolevala.narod.ru/u51.gif http://mmmf.msu.ru/archive/19992000/bugaenko/pic13.gif http://www.vpkla.ru/bolhovitinov.files/image222.jpg http://www.ynasveselo.ru/images/stories/picture/r06.jpg http://www.liveinternet.ru/users/vl866911/post254869616/ http://www.smayli.ru/data/smiles/komputeri-191.gif
Учимся рисовать горный пейзаж акварелью
Астрономический календарь. Октябрь, 2018
Как выглядело бы наше небо, если вместо Луны были планеты Солнечной Системы?
Лесная сказка о том, как согреться холодной осенью
Рукавичка