Лекция «Теория графов»

ЛЕКЦИЯ

«ИСТОРИЯ ВОЗНИКНОВЕНИЯ ТЕОРИИ ГРАФОВ».

Оборудование: мультимедийный проектор.

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

Ход занятия:

I. ОРГАНИЗАЦИОННЫЙ МОМЕНТ.

II. ТЕОРИЯ.

Сегодня наша задача – выяснить, что такое граф.

Вспомним, что такое график. График – это ломаная или кривая линия, наглядно показывающая изменение роста, движение, изменение температуры тогда как граф - это схема, состоящая из точек и соединяющих их дуг или стрелок (ненаправленный и направленный граф). Если построить в координатной плоскости граф, то одному значению абсциссы соответствует несколько значений ординат, а для графика это неприемлемо.

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

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

Первая работа по теории графов, принадлежащая известному швейцарскому математику Л. Эйлеру, появилась в 1736 г. Толчок к развитию теория графов получила на рубеже ХIX и ХХ столетий, когда резко возросло число работ в области топологии и комбинаторики, с которыми ее связывают самые тесные узы родства. Графы стали использоваться при построении схем электрических цепей и молекулярных схем. Как отдельная математическая дисциплина теория графов была впервые представлена в работе венгерского математика Кенига в 30-е годы ХХ столетия.

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

III. ЗАКРЕПЛЕНИЕ МАТЕРИАЛА.

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

Задача про контуры.

построить в тетрадях фигуры без отрыва карандаша:

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

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

Решение:

Ответ: Петя знаком с Максимом и Сережей, Коля – с Витей и Максимом, Сережа – с Петей и Витей.

Задача про жителей пяти домов.

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

Удастся ли им это сделать?

Решение: да.

Задача про завтрак.

В кафе завтракали трое. Двое ели сосиски, двое – винегрет, а двое – виноград. Тот, кто не ел сосисок, не ел и винегрет. Тот, кто не ел виноград, не ел и винегрет. Что ел на завтрак каждый?

Ответ: один не ел ничего, а двое других – все три блюда.

Задача про трех внуков.

Для Вани, Коли и Миши бабушка испекла три пирога – с рисом, с капустой и с яблоками. Двое из внуков не любят пирог с капустой, двое с рисом и двое – с яблоками. Миша не любит пирог с яблоками и не ест с капустой, Ваня не любит с капустой. Кто что ест?

Ответ: Миша ест пирог с рисом, Коля с капустой, а Ваня – с яблоками.

Задача Сэма Ллойда про калитки трех цветов. Во дворе, который окружен высоким забором, находятся три домика: красный, желтый и синий. В заборе есть три калитки: красная, желтая и синяя. От красного домика проведите дорожку к красной калитке, от желтого домика — к желтой калитке, от синего — к синей так, чтобы эти дорожки не пересекались.

Решение:

Задача про игрушки.

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

Ответ: пистолет – в синей, сумочка – в красной, кукла – в зеленой, машинка – в желтой коробках.

IV. ДОМАШНЕЕ ЗАДАНИЕ.

Проектное задание: придумайте задачу, которую можно решить построением графа.

V. ИТОГИ ЗАНЯТИЯ.

Анкетирование учащихся.

АНКЕТА 1

Что такое теория графов? (Выскажите свое понимание).

Нравится ли Вам заниматься теорией графов? (Да, нет). Почему?

Какие задачи теории графов Вам известны?

Какие имена, связанные с теорией графов, Вы знаете?

Назовите известные Вам математические теории.

Какие из известных Вам математических теорий, на Ваш взгляд, связаны с теорией графов?