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

ГРАФ ЭКСТРЕМАЛЬНЫЙ - граф, на к-ром та или иная числовая характеристика принимает свое минимальное или максимальное значение. Обычно отыскиваются экстремальные значения нек-рой одной числовой характеристики при ограничениях на другие числовые характеристики и свойства. Часто задача состоит в описании множества соответствующих Г. э. Пусть, напр., зафиксированы целые положительные числа n и k и отыскивается наибольшее число ребер n-вершинного графа, не имеющего полных подграфов с k+1 вершинами. Установлено, что это число равно

где n = k[n/k] + r. При этом единственным с точностью до изоморфизма Г. э. является полный k-дольный граф, мощности долей к-рого отличаются не более чем на единицу (см. [3]).

На Г. э. изучаемые числовые характеристики достигают своего глобального экстремума. Так наз. критические графы могут рассматриваться как локально оптимальные. Пусть заданы нек-рое свойство А и набор одноместных операций O₁, ..., O_s над графами. Граф G, обладающий свойством А, наз. критическим по свойству А относительно операций O₁, ..., O_s, если после применения любой из этих операций получается граф, не обладающий свойством А. При этом предполагается, что множество графов, не обладающих свойством А, замкнуто относительно рассматриваемых операций. В качестве свойства А рассматриваются такие свойства графа, как быть связным, плоским, k-хроматическим и т. п., а в качестве операций - операции удаления и добавления вершины или ребра, стягивания ребра и др.

Напр., граф Петерсена (см. рис.) является критическим по свойству иметь реберное хроматическое число, равное 4, относительно операции удаления ребра. Полный пятивершинный граф К₅ и полный двудольный граф K_3,3 (см. Граф плоский, рис. 1), каждая доля к-рого имеет три вершины, являются критическими по свойству не быть плоским относительно операций удаления ребра, стягивания ребра, удаления вершины.

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

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

А. А. Сапоженко.

Источники:

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