Лекции_по_ДМ

История и применение

Начало теории графов как математической дисциплины было положено Эйлером в его знаменитом рассуждении о кенигсбергских мостах (1736 г.) Однако, она не находила применения в течение почти 100 лет. Интерес к теории возник благодаря исследованиям электрических сетей, моделей кристаллов и структур молекул. В 1847 г. Кирхгофом была разработана теория деревьев, которая послужила важным аналитическим средством для исследования электрических цепей. Законы Кирхгофа для напряжений и токов в цепи полностью определяются контурами и сечениями графа этой цепи и не зависят от природы используемых элементов. Поэтому тщательное изучение понятий контура, сечения и дерева графа дало толчок многим открытиям в теории цепей и, кроме того, внесло большой вклад в теорию графов.

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

Содержание