графів теорія

Гр а фов теорія, розділ кінцевої математики , Особливістю якого є геометричний підхід до вивчення об'єктів. Основне поняття теорії - граф. Граф задається безліччю вершин (точок) і безліччю ребер (зв'язків), що з'єднують деякі (а може бути, і все) пари вершин. При цьому пари вершин можуть з'єднуватися декількома ребрами. Приклади графів: безліч міст (вершини графа), наприклад Московської області, і що з'єднують їх дороги (ребра графа); елементи електричної схеми і дроти, що сполучають їх. На рис. 1 зображений граф, вершинами якого є станції міського метрополітену, а ребрами - шляхи, що з'єднують сусідні станції (одне із завдань: вказати будь-якої маршрут від станції А до станції В) .Граф називається орієнтованим, якщо на ребрах задана орієнтація, т. Е . зазначений порядок проходження вершин. Нарешті, в Г. т. Вивчаються графи, у яких ребрах приписані будь ваги (або символи), а також графи, в яких виділені особливі вершини, називаються полюсами. Приклади: діаграма станів автомата, мережа ж.-д. шляхів із зазначенням на дугах їх довжин або пропускних спроможностей. На рис. 2 приведена схема автомобільних доріг між Москвою і Таллінном; треба, наприклад, вибрати маршрут мінімальної загальної довжини шляху з Москви в Таллінн (ці два міста - полюси мережі); порівняння двох маршрутів Москва - Ленінград - Таллінн і Москва - Вітебськ - Рига - Таллінн показує, що шлях через Ленінград коротша (1049 км).

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

Мал. 2 до ст. Графів теорія.

Мал. 1 до ст. Графів теорія.