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

граф, на к-ром та или иная числовая характеристика принимает свое минимальное или максимальное значение. Обычно отыскиваются экстремальные значения нек-рой одной числовой характеристики при ограничениях на другие числовые характеристики и свойства. Часто задача состоит в описании множества соответствующих Г. э. Пусть, напр., зафиксированы целые положительные числа пи kи отыскивается наибольшее число ребер n-вершин-ного графа, не имеющего полных подграфов с вершинами. Установлено, что это число равно

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

На Г. э. изучаемые числовые характеристики достигают своего глобального экстремума. Так наз. критические графы могут рассматриваться как локально оптимальные. Пусть заданы нек-рое свойство.

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

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

Лит.:[1] Харари Ф., Теория графов, пер. с англ., М., 1973; [2] Зыков А. А., Теория конечных графов, [в. 1], Новосиб., 1969; [3] Тuran P., "Mat. Fiz. Lapok", 1941, V. 48, p. 436-52. А. А. Сапоженко.