Історія виникнення і розвиток теорії графів

Зародившись при розв'язуванні головоломок і цікавих задач, теорія графів нині стала потужним засобом розв'язування задач широкого спектру проблем. У теоретико-графових термінах формулюється значна кількість задач, пов'язаних з дискретними об'єктами. В деякій мірі через теорію графів відбувається проникнення математичних методів в науку і техніку. Слово «граф» з'явилося в математичній літературі порівняно недавно. Тим часом поняття графа використовується дуже часто не тільки в математиці, але і повсякденному житті під різними назвами: схема, діаграма, карта, лабіринт тощо. Теорія графів на даний час бурхливо розвивається, її результати застосо­вують, проектуючи різноманітні електронні пристрої, вивчаючи автомати, у програмуванні, фізиці, хімії, біології, економіці, статистиці та багатьох інших галузях діяльності людини.

Початок теорії графів як математичної дисципліни прийнято повязувати з Ейлером, який знайшов умову існування циклу у зв’язному графі в його знаменитому міркуванні про Кенігсбергські мости. Ось переказ уривка з листа Ейлера від 13 березня 1736 року: ”Мені було запропоновано задачу про острів, розташований в місті Кенігсберг, що оточене річкою, через яку перекинуто 7 мостів. Чи може хто-небудь безперервно обійти їх, проходячи тільки один раз через кожен міст? І тут же мені було повідомлено, що ніхто ще до цих пір не зміг це виконати, але ніхто і не довів, що це неможливо. Питання це, хоч і банальне, здалося мені, проте, гідне уваги того, що для його вирішення недостатні ні геометрія, ні алгебра, ні комбінаторне мистецтво. Після довгих роздумів я знайшов правило, засноване на цілком переконливому доказі, за допомогою якого можна у всіх задачах такого роду визначити, чи може бути здійснений такий обхід через певне число як завгодно розташованих мостів або не може“. Кенігсбергські мости схематично можна зобразити так:

Рис. 1. Схематичне зображенняКенігсбергських мостів

Правило Ейлера:

1. У графові, що не має вершин непарних степенів, існує обхід всіх ребер (причому кожне ребро проходиться в точності один раз) з початком в будь-якій вершині графа.

2. У графові, що має дві і лише дві вершини з непарними степенями, існує обхід з початком в одній вершині з непарним степенем і кінцем в іншій.

3. У графі, що має більше двох вершин з непарним степенем, такого обходу не існує.

Проте стаття Ейлера 1736 року була єдиною протягом майже ста років. Інтерес до проблем теорії графів відродився в середині 19-го сторіччя і був зосереджений головним чином в Англії. Було багато причин для такого пожвавлення вивчення графів: природничі науки зробили свій вплив завдяки дослідженням електричних ланцюгів, моделей кристалів і структур молекул. Розвиток формальної логіки привів до вивчення бінарних відношень у формі графів. У 1847 році інженер-електрик Г. Кіргоф розробив теорію дерев для дослідження електричних ланцюгів, а математик А. Келі у 1857 році описав будову вуглеводів за допомогою трьох типів дерев. Г. Кірхгоф при складанні повної системи рівнянь для струмів і напруги в електричній схемі запропонував по суті представляти таку схему графом і знаходити в цьому графові остовні дерева, за допомогою яких виділяються лінійно незалежні системи контурів. Велике число популярних головоломок подавалося формулюванням безпосередньо в термінах графів, і це приводило до розуміння, що багато задач такого роду містять деяке математичне ядро, важливість якого виходить за рамки конкретного питання. Найбільш знаменита серед цих задач – проблема чотирьох фарб, вперше поставлена перед математиком Де Морганом близько 1850 року. 20-те століття було свідком неухильного розвитку теорії графів, яка вступила в новий період інтенсивних розробок. У цьому процесі явно помітний вплив запитів нових областей: теорії ігор і програмування, теорії передачі повідомлень, електричних мереж і контактних ланцюгів, а також проблем психології і біології.

Існує ще один вид задач, пов'язаних з теорією графів. Мова йде про задачі, у яких потрібно відшукати шлях, що проходить через усі вершини, причому не більше одного разу через кожну. Цикл, що проходить через кожну вершину один і лише один раз, носить назву гамільтонового циклу (на честь Уїльяма Роуена Гамільтона, знаменитого ірландського математика, який у 1859 році сформулював задачу на прикладі графа додекаедра).

Починаючи з 30-х років XIX століття, популярність графів і кількість праць з чистої теорії графів та її засто­сувань неухильно зростає. За допомогою графа моделю­ються будь-які схеми, в яких виділяються більш прості частини (вершини) і зв'язки між ними (ребра). Не дивно, що графи зустрічаються у дослідженнях з соціології, пси­хології, економіки, теорії ігор, логіки, програмування, тео­рії ймовірностей (ланцюги Маркова), квантової механіки (діаграми Фейнмана), хімії (структура молекул), статистич­ної механіки, кристалофізики, медицини (нервові, судинні та інші мережі), електро- і радіотехніки, лінгвістики, теорії розкладів, з транспортних мереж і течій, вентиляційних ме­реж та ін.

У 20 ст. задачі, пов'язані з графами, почали виникати не лише у фізиці, хімії, електротехніці, біології, економіці, соціології тощо, але й усередині математики, у таких розділах, як топологія, алгебра, теорія ймовірності, теорія чисел. У 20-30-х роках 20 ст. з'явилися перші результати, що відносяться до вивчення властивостей зв'язності, планарностi, симетрії графів, які привели до формування ряду нових напрямів в теорії графів.

Термін «граф» уперше зявився в книзі угорського математика Д. Кеніга «Theorie der endlichen und unendlichen Graphen», що вийшла у 1936 році.

Значно розширилися дослідження з теорії графів у кінці 40-х - початку 50-х років, перш за все через розвиток кібернетики і обчислювальної техніки. Завдяки розвитку обчислювальної техніки, вивченню складних кібернетичних систем, зріс інтерес до теорії графів, а проблематика теорії графів істотним чином збагатилася. Крім того, використання ЕОМ дозволило вирішувати конкретні завдання, що виникають на практиці, пов'язані з великим об'ємом обчислень. Для ряду екстремальних задач теорії графів були розроблені методи їх розв’язання, наприклад, один з таких методів дозволяє розв’язувати задачі про побудову максимального потоку через мережу

Поиск по сайту: