Математика. Элементарные понятия теории графов.

Элементарные понятия теории графов

Основной объект теории графов — граф и его обобщения. Началом теории графов считается 1736 год, когда вышла в свет статья Л. Эйлера с его знаменитыми рассуждениями о Кенигсбергских мостах.

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