Пошук найкоротшого шляху
3

Вступ

 

Інтерес до проблем теорії графів відродився близько середини минулого століття і був зосереджений головним чином в Англії. Малося багато причин для такого пожвавлення вивчення графів. Природничі науки зробили свій вплив на це завдяки дослідженням електричних ланцюгів, моделей кристалів і структур молекул.

Розвиток формальної логіки призвів до вивчення бінарних відносин у формі графів. Велика кількість популярних головоломок подавалося формулюванню безпосередньо в термінах графів, і це призводило до розуміння, що багато задач такого роду містять деякий математичне ядро, важливість якого виходить за рамки конкретного питання.

Найбільш знаменита серед цих завдань – проблема чотирьох фарб, в перше поставлена перед математиками Де Морганом близько 1850 року. Жодна проблема не викликала таких численних і дотепних робіт в галузі теорії графів. Завдяки своїй простоті формулюванні і дратівливій невловимості вона до цих пір залишається потужним стимулом для досліджень різних властивостей графів.

ХХ століття було свідком неухильного розвитку теорії графів, яка за останні десять-двадцять років вступила в новий період інтенсивних розробок. У цьому процесі явно помітно вплив запитів нових областей: теорії ігор і програмування, теорії передачі повідомлень,електричних мереж і контактних ланцюгів, а також проблем психології і біології.