Графів теорія, розділ кінцевої математики, особливістю якого є геометричний підхід до вивчення об'єктів. Основне поняття теорії — граф. Граф задається безліччю вершин (крапок) і безліччю ребер (зв'язків), що сполучають деякі (а може бути, і все) пари вершин. При цьому пари вершин можуть з'єднуватися декількома ребрами. Приклади графів: безліч міст (вершини графа), наприклад Московської області, і сполучаючі їх дороги (ребра графа); елементи електричної схеми і дроту, що сполучають їх. На мал. 1 змальований граф, вершинами якого є станції міського метрополітену, а ребрами — дороги, що сполучають сусідні станції (одне із завдань: вказати який-небудь маршрут від станції А до станції В ). Граф називається орієнтованим, якщо на ребрах задана орієнтація, тобто вказаний порядок проходження вершин. Нарешті, в Р. т. вивчаються графи, в яких ребрам приписані які-небудь ваги (або символи), а також графи, в яких виділені особливі вершини, називаються полюсами. Приклади: діаграма станів автомата, мережа ж.-д.(железнодорожний) доріг з вказівкою на дугах їх довжин або пропускних спроможностей. На мал. 2 приведена схема автомобільних доріг між Москвою і Таліном; треба, наприклад, вибрати маршрут мінімальної загальної довжини дороги з Москви в Талін (ці два міста — полюси мережі); порівняння двох маршрутів Москва — Ленінград — Талін і Москва — Вітебськ — Рига — Талін показує, що дорога через Ленінград коротша (1049 км. ).
Одній з перших робіт по Р. т. можна рахувати роботу Л. Ейлера (1736), що відноситься до вирішення головоломок і математичних розважальних завдань. Перші глибокі результати були отримані в 1-ій половині 20 ст у зв'язку з вирішенням завдань побудови електричних ланцюгів і підрахунку хімічних речовин з різними типами молекулярних з'єднань. Проте широкий розвиток Р. т. отримала лише з 50-х рр. у зв'язку із становленням кібернетики і розвитком обчислювальної техніки, коли Р. т. істотно збагатилася і новим матеріалом, і новими підходами і коли почалося систематичне вивчення графів з різних точок зору (структурною, інформаційною і т. д.). Саме в цей час формулювалися проблематика і методи Р. т. Р. т. знаходить вживання в теорії програмування і при побудові обчислювальних машин, у вивченні фізичних, хімічних і технологічних процесів, у вирішенні завдань планерування, в лінгвістичних і соціологічних дослідженнях і так далі Р. т. має тісні зв'язки як з класичними, так і з новими розділами математики; це — топологія, алгебра, комбінаторний аналіз, теорія чисел, теорія мінімізації булевих функцій. Р. т. включає велике число всіляких завдань. Одні з них групуються в окремі напрями, інші стоять більш ізольовано. Серед розділів Р. т., що склалися, слід зазначити завдання, що відносяться до аналізу графів, визначення різних характеристик їх будови, наприклад з'ясування зв'язності графа: чи можна з будь-якої вершини попасти в будь-яку; підрахунок графів або їх частин, що володіють заданими властивостями, наприклад підрахунок кількості дерев із заданим числом ребер (дерево — неорієнтований граф без циклів); рішення транспортних завдань, пов'язаних з перевезеннями вантажів по мережі. Вирішений ряд завдань по синтезу графів із заданими властивостями, наприклад побудова графа із заданими мірами вершин (міра вершини — число ребер, що виходять з неї). Має прикладне і теоретичне значення завдання про з'ясування можливості розташування графа на плоскості без самопересеченій його ребер (тобто чи є даний граф плоским), завдання про розбиття графа на мінімальне число плоских графів. Для деяких завдань Р. т. (вище були приведені далеко не все) були розроблені методи їх рішення. Серед них: метод Пойя перерахування і підрахунку графів із заданими властивостями, теорема і алгоритм Форда — Фалкерсона для вирішення транспортного завдання, «угорський» алгоритм рішення задачі про призначення і так далі Майже всі завдання теорії кінцевих графів (практично цікаві саме графи з кінцевим числом вершин) можуть бути вирішені шляхом перебору великого числа варіантів (т.з. повний перебір) тому для них потрібна побудова ефективних алгоритмів і використання швидкодіючих обчислювальних машин. Такими завданнями є: завдання про розфарбовування вершин графа, завдання про визначення ідентичності двох графів, комівояжера завдання . Є завдання, що вимагають принципової відповіді, наприклад завдання про розфарбовування плоских графів, завдання про відновлення графа по його підграфах.
Літ.: Берж До., Теорія графів і її вживання, пер.(переведення) з франц.(французький), М., 1962; Оре О., Графи і їх вживання, пер.(переведення) з англ.(англійський), М., 1965; Зиков А. А., Теорія кінцевих графів. I, Новосибірськ, 1969.
