ГРАФ ЕКСТРЕМАЛЬНИЙ

ГРАФ ЕКСТРЕМАЛЬНИЙ - граф, на якому та чи інша числова характеристика приймає своє мінімальне або максимальне значення. Зазвичай знаходяться екстремальні значення деякої однієї числової характеристики при обмеженнях на інші числові характеристики і властивості. Часто завдання полягає в описі безлічі відповідних Р. е. Нехай, напр., зафіксовані цілі позитивні числа n і k і знаходиться найбільше число ребер n-вершинного графа, що не має повних підграф з k+1 вершинами. Встановлено, що це число дорівнює

де n = k [n / k] + r. При цьому єдиним з точністю до ізоморфізму Р. е. є повний k-дольний граф, потужності часток до-рого відрізняються лише на одиницю (див. [3]).

На Р. е. Чисельні характеристики, що вивчаються, досягають свого глобального екстремуму. Так зв. критичні графи можна як локально оптимальні. Нехай задані деяка властивість А і набір одномісних операцій O1, . Os над графами. Граф G, що має властивість А, зв. критичним за якістю А щодо операцій O1, . Os, якщо після застосування будь-якої з цих операцій виходить граф, що не володіє властивістю А. При цьому передбачається, що безліч графів, що не мають властивості А, замкнуто щодо операцій, що розглядаються. Як властивості А розглядаються такі властивості графа, як бути зв'язковим, плоским, k-хроматичним і т. п., а як операції - операції видалення та додавання вершини або ребра, стягування ребра та ін.

Напр., граф Петерсена (див. рис.) є критичним за властивістю мати реберне хроматичне число, що дорівнює 4 щодо операції видалення ребра. Повний п'ятивершинний граф К5 і повний дводольний граф K3,3 (див. Граф плоский, рис. 1), кожна частка якого має три вершини, є критичнимиза властивістю не бути плоским щодо операцій видалення ребра, стягування ребра, видалення вершини.

При вивченні властивостей та характеристик графів виявляється корисним вивчення їх критичних підграфів, тобто підграфів, які мають ті чи інші властивості та є мінімальними (максимальними) за включенням. Приклади таких подграф - компоненти зв'язності (k-зв'язності), остовні дерева. Екстремальні та критич. графи служать: для опису класів графів, що володіють заданими властивостями та числовими характеристиками; для встановлення взаємозв'язку між різними властивостями та числовими характеристиками; для перевірки наявності тієї чи іншої властивості графа.

Літ.: [l] Xарарі Ф., Теорія графів, пров. з англ., М., 1973; [2] Зиков А. А., Теорія кінцевих графів, [ст. 1], Новосиб., 1969; [3] Turin P., «Mat. Fiz. Lapok», 1941, v. 48, p. 436-52.

Математична енциклопедія. Т. 1 (А – Г). ред. колегія: І. М. Виноградов (глав ред) [та ін] - М., «Радянська Енциклопедія», 1977, 1152 стб. з ілл.