Походження графів

Багато задач зводяться до розгляду сукупності об'єктів, істотні властивості яких описуються зв'язками між ними. Наприклад, дивлячись на карту автомобільних доріг, можна цікавитися тільки тим, чи є зв'язок між деякими населеними пунктами, не звертаючи уваги на конфігурацію і якість дороги, відстань і інші подробиці. При вивченні електричних ланцюгів на перший план може виступати характер з'єднань різних його компонентів — резисторів, конденсаторів, джерел і т.п. Органічні молекули утворюють структури, характерними властивостями яких є зв'язки між атомами. Інтерес можуть представляти різні зв'язки і відношення між людьми, подіями, станами і взагалі між будь-якими об'єктами. У подібних випадках зручно розглянуті об'єкти зображувати крапками, називаними вершинами, а зв'язки між ними — лініями (довільної конфігурації), називаними ребрами. Множина вершин V, зв'язки між якими визначені множиною ребер , називають графом і позначають G = (V, Е).

Перша робота з графів була опублікована двадцятилітнім Леонардом Ейлером у 1736 р., коли він працював у Російській Академії наук. Вона містила вирішення задачі про кенигсбергські мости (мал.7): чи можна зробити прогулянку в такий спосіб, щоб вийшовши з будь-якого місця міста, повернутися в нього, пройшовши в точності один раз по кожному мосту?

Мал. 3.1. До задачі про кенигсбергські мости: а – план міста; б – граф.

Ясно, що за умовою задачі не має значення, як проходить шлях по частинам суші на який розташований м. Кенігсберг (нині Калінінград), тому їх можна представити вершинами. А так як зв'язки між цими частинами здійснюються тільки через сім мостів, то кожний із них зображується ребром, що з'єднує відповідні вершини. У результаті одержуємо граф, зображений на мал. 7, б. Ейлер дав негативну відповідь на поставлене питання. Більш того, він довів, що подібний маршрут є тільки для такого графа, кожна з вершин якого зв'язана з парним числом ребер.

З тих пір потік задач із застосуванням графів наростав подібно сніжній лавині. Поряд із численними головоломками й іграми на графах, розглядалися важливі практичні проблеми, багато з який вимагали тонких математичних методів. Вже в середині минулого століття Кірхгоф застосував графи для аналізу електричних ланцюгів, а Келі досліджував важливий клас графів для виявлення і перерахування ізомерів насичених вуглеводнів. Однак теорія графів як математична дисципліна сформувалася тільки до середини тридцятих років нашого сторіччя завдяки роботам багатьох дослідників, найбільша заслуга серед який належить Д. Кенигу. Значний внесок у теорію графів внесли радянські вчені Л. С. Понтрягін, А. А. Зиков, В. М. Визинг і ін.

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