Теория графов в жизни и деятельности людей. Примеры использования

Творческая задача

По дисциплине «Дискретная математика»

По теме:

Теория графов в жизни и деятельности людей. Примеры использования.»

Содержание

Основы теории графов 2

История возникновения теории графов 3

Виды графов 4-8

Использование в жизни и деятельности 9-19

Теоретическая составляющая 9-13

Пример использования графов на решения задач

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

                         История возникновения теории графов

Родоначальником теории графов считается Леонард Эйлер. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи Кенигсбергских мостах, ставшей впоследствии одной из классических задач теории графов.

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

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