Применение теории графов «Чтоб мудро жизнь прожить Знать надобно немало…» О. Хайям




НазваниеПрименение теории графов «Чтоб мудро жизнь прожить Знать надобно немало…» О. Хайям
Дата конвертации23.02.2013
Размер445 b.
ТипПрезентации


Применение теории графов


«Чтоб мудро жизнь прожить Знать надобно немало…» О.Хайям

  • Цель:

  • Познакомиться с одним из разделов дискретной математики

  • Задачи:

  • Создать мотивационную базу для изучения самого молодого раздела современной математики;

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

  • помочь учащимся отойти от математических штампов;

  • показать красоту этого метода.



История вопроса

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



Основные понятия

  • При решении задачи о Кенигсбергских мостах Эйлер поступил следующим образом: он "сжал" сушу в точки, а мосты "вытянул" в линии. Такую фигуру, состоящую из точек и линий, связывающих эти точки, называют ГРАФОМ.

  • Точки А, В, С, D называют ВЕРШИНАМИ графа, а линии, которые соединяют вершины, - РЕБРАМИ графа.

  • На нашем рисунке из вершин В, С и D выходит по три ребра, а из вершины А - пять ребер. Вершины, из которых выходит нечетное число ребер, называются НЕЧЕТНЫМИ вершинами, а вершины, из которых выходит четное число ребер, называются ЧЕТНЫМИ.



Свойства графов

  • Решая задачу про Кенигсбергские мосты, Эйлер установил, в частности, следующие три СВОЙСТВА графа:

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

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

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

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



Свойства графов

  • Кроме трех свойств графа, которые установил Эйлер, решая задачу про Кенигсбергские мосты, он вывел еще два СВОЙСТВА:

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

  • 5) Если в графе имеются нечетные вершины, то наименьшее число росчерков, которыми можно нарисовать граф, равно половине числа нечетных вершин этого графа.

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





Другие примеры графов







Задача

  • В городе проводилось совещание врачей. От каждой поликлиники были приглашены 4 врача. Каждый из приглашенных работал в 2 поликлиниках и представлял на этом совещании обе поликлиники. Любая возможная комбинация двух поликлиник имело на этом совещании одного и только одного представителя. Сколько поликлиник в городе? Сколько врачей было приглашено на совещание?



Спасибо за внимание!

  • Спасибо за внимание!



Похожие:

Применение теории графов «Чтоб мудро жизнь прожить Знать надобно немало…» О. Хайям iconОсновные понятия теории графов граф и его свойства примеры графов
Степени вершин полного графа одинаковы, и каждая из них на 1 меньше числа вершин этого графа
Применение теории графов «Чтоб мудро жизнь прожить Знать надобно немало…» О. Хайям iconИстория квантовой механики Общая теория относительности
«Есть только два способа прожить жизнь: «Есть только два способа прожить жизнь: Первый будто чудес не существует. Второй будто кругом...
Применение теории графов «Чтоб мудро жизнь прожить Знать надобно немало…» О. Хайям iconИсследование по элективному курсу «начальные понятия теории графов» ученика 9 класса «Б» моу сош №1 подковырова игоря учитель математики папкова мария юрьевна
Проектное исследование по элективному курсу «начальные понятия теории графов» ученика 9 класса «Б» моу сош №1 подковырова игоря учитель...
Применение теории графов «Чтоб мудро жизнь прожить Знать надобно немало…» О. Хайям iconОсновные понятия теории графов
Графами были названы схемы, состоящие из точек и соединяющих эти точки отрезков прямых или кривых
Применение теории графов «Чтоб мудро жизнь прожить Знать надобно немало…» О. Хайям iconТеория графов Теория графов – обширный самостоятельный раздел дискретной математики
...
Применение теории графов «Чтоб мудро жизнь прожить Знать надобно немало…» О. Хайям iconПрименение методов статистики и теории вероятностей в трубопроводном транспорте

Применение теории графов «Чтоб мудро жизнь прожить Знать надобно немало…» О. Хайям iconРешение задач Алгоритм Крускала
Родоначальником теории графов принято считать математика Леонарда Эйлера (1707-1783). Через город протекает река Преголя. Она делится...
Применение теории графов «Чтоб мудро жизнь прожить Знать надобно немало…» О. Хайям iconТрудности в жизни детей
Жизнь прожить, не поле перейти. Очень верная пословица. Не правда ли? Сколько в жизни бывает
Применение теории графов «Чтоб мудро жизнь прожить Знать надобно немало…» О. Хайям iconТы педагог – тебе все интересно! Много школ хороших и разных
Учить детей, что может быть прекрасней? Всего себя работе отдавать, и раскрывать мораль крыловской басни, Чтоб параллели жизни знать...
Применение теории графов «Чтоб мудро жизнь прожить Знать надобно немало…» О. Хайям iconВ настоящее время проблема загрязнения водной среды является очень актуальной, т к. сейчас люди начинают забывать всем известное выражение «вода это жизнь»
«вода это жизнь». Без воды человек не может прожить более трех суток, но, даже понимая всю важность роли воды в его жизни, он все...
Разместите кнопку на своём сайте:
hnu.docdat.com


База данных защищена авторским правом ©hnu.docdat.com 2012
обратиться к администрации
hnu.docdat.com
Главная страница