Лекция «Теория графов» (9 класс, математика)
ЛЕКЦИЯ
«ИСТОРИЯ ВОЗНИКНОВЕНИЯ ТЕОРИИ ГРАФОВ».
Оборудование: мультимедийный проектор.
Цели: выяснить, что такое граф; обнаружить связь теории графов с решением головоломок; изучить теорию возникновения графов; провести параллель между теорией графов и другими математическими теориями.
Ход занятия:
I. ОРГАНИЗАЦИОННЫЙ МОМЕНТ.
II. ТЕОРИЯ.
Сегодня наша задача – выяснить, что такое граф.
Вспомним, что такое график. График – это ломаная или кривая линия, наглядно показывающая изменение роста, движение, изменение температуры тогда как граф - это схема, состоящая из точек и соединяющих их дуг или стрелок (ненаправленный и направленный граф). Если построить в координатной плоскости граф, то одному значению абсциссы соответствует несколько значений ординат, а для графика это неприемлемо.
Если вы любите решать олимпиадные задачи, то, наверное, не раз составляли таблицы, изображали объекты точками, соединяли их отрезками или стрелками, подмечали закономерности у полученных рисунков, выполняли над точками и отрезками операции, не похожие на арифметические, алгебраические или на преобразования в геометрии. То есть вам приходилось строить математический аппарат специально для решения задачи. А это означает, что вы открывали для себя начала теории графов.
Исторически сложилось так, что теория графов зародилась двести с лишним лет назад именно в ходе решения головоломок. Очень долго она находилась в стороне от главных направлений исследований ученых, была в царстве математики на положении Золушки, чьи дарования раскрылись в полной мере лишь тогда, когда она оказалась в центре общего внимания.
Первая работа по теории графов, принадлежащая известному швейцарскому математику Л. Эйлеру, появилась в 1736 г. Толчок к развитию теория графов получила на рубеже ХIX и ХХ столетий, когда резко возросло число работ в области топологии и комбинаторики, с которыми ее связывают самые тесные узы родства. Графы стали использоваться при построении схем электрических цепей и молекулярных схем. Как отдельная математическая дисциплина теория графов была впервые представлена в работе венгерского математика Кенига в 30-е годы ХХ столетия.
В последнее время графы и связанные с ними методы исследований органически пронизывают на разных уровнях едва ли не всю современную математику. Теория графов рассматривается как одна из ветвей топологии; непосредственное отношение она имеет также к алгебре и к теории чисел. Графы эффективно используются в теории планирования и управления, теории расписаний, социологии, математической лингвистике, экономике, биологии, медицине, географии. Широкое применение находят графы в таких областях, как программирование, теория конечных автоматов, электроника, в решении вероятностных и комбинаторных задач, нахождении максимального потока в сети, кратчайшего расстояния, максимального паросочетания, проверки планарности графа и др. Как особый класс можно выделить задачи оптимизации на графах. Математические развлечения и головоломки тоже являются частью теории графов, например, знаменитая проблема четырех красок, интригующая математиков и по сей день. Теория графов быстро развивается, находит все новые приложения и ждет молодых исследователей.
III. ЗАКРЕПЛЕНИЕ МАТЕРИАЛА.
Многие логические задачи можно довольно просто решать построением графов. Графы придают условиям задач наглядность, упрощают решение и выявляют сходство задач.
Задача про контуры.
построить в тетрадях фигуры без отрыва карандаша:
Ответ: первый и четвертый контуры нельзя построить без отрыва карандаша от бумаги.
Задача про спортивный зал. В спортивном зале собрались Витя, Петя, Сережа, Коля и Максим. Каждый из них знаком только с двумя другими. Кто с кем знаком?
Решение:
Задача про жителей пяти домов.
Жители пяти домов поссорились друг с другом и, чтобы не встречаться у своих гаражей, решили, что хозяин каждого дома будет ходить к своему гаражу по своей тропинке.
Удастся ли им это сделать?
Решение: да.
Задача про завтрак.
В кафе завтракали трое. Двое ели сосиски, двое – винегрет, а двое – виноград. Тот, кто не ел сосисок, не ел и винегрет. Тот, кто не ел виноград, не ел и винегрет. Что ел на завтрак каждый?
Ответ: один не ел ничего, а двое других – все три блюда.
Задача про трех внуков.
Для Вани, Коли и Миши бабушка испекла три пирога – с рисом, с капустой и с яблоками. Двое из внуков не любят пирог с капустой, двое с рисом и двое – с яблоками. Миша не любит пирог с яблоками и не ест с капустой, Ваня не любит с капустой. Кто что ест?
Ответ: Миша ест пирог с рисом, Коля с капустой, а Ваня – с яблоками.
Задача Сэма Ллойда про калитки трех цветов. Во дворе, который окружен высоким забором, находятся три домика: красный, желтый и синий. В заборе есть три калитки: красная, желтая и синяя. От красного домика проведите дорожку к красной калитке, от желтого домика — к желтой калитке, от синего — к синей так, чтобы эти дорожки не пересекались.
Решение:
Задача про игрушки.
Купленные в подарок игрушки (пистолет, сумочку, куклу и машину) уложили в четыре коробки по одной игрушке в каждую. Требуется узнать, что положено в каждую коробку, если известно следующее: машина и пистолет не в красной коробке; коробка с сумочкой находится между синей коробкой и коробкой с куклой; в зеленой коробке не сумочка и не машинка; желтая и зеленая коробки находятся около коробки с пистолетом. Постройте граф.
Ответ: пистолет – в синей, сумочка – в красной, кукла – в зеленой, машинка – в желтой коробках.
IV. ДОМАШНЕЕ ЗАДАНИЕ.
Проектное задание: придумайте задачу, которую можно решить построением графа.
V. ИТОГИ ЗАНЯТИЯ.
Анкетирование учащихся.
АНКЕТА 1
Что такое теория графов? (Выскажите свое понимание).
Нравится ли Вам заниматься теорией графов? (Да, нет). Почему?
Какие задачи теории графов Вам известны?
Какие имена, связанные с теорией графов, Вы знаете?
Назовите известные Вам математические теории.
Какие из известных Вам математических теорий, на Ваш взгляд, связаны с теорией графов?
Как Вы считаете, оказала ли теория графов влияние на другие математические теории ХХ века?
Почему Вы выбрали именно этот элективный курс?
