Граф экстремальный

граф, на к-ром та или иная числовая характеристика принимает свое минимальное или максимальное значение. Обычно отыскиваются экстремальные значения нек-рой одной числовой характеристики при ограничениях на другие числовые характеристики и свойства. Часто задача состоит в описании множества соответствующих Г. э. Пусть, напр., зафиксированы целые положительные числа пи kи отыскивается наибольшее число ребер n-вершин-ного графа, не имеющего полных подграфов с [img: http://localhost:8080/file/010429-22.jpg] вершинами. Установлено, что это число равно [img: http://localhost:8080/file/010429-23.jpg] где При этом единственным с точностью до изоморфизма [img: http://localhost:8080/file/010429-24.jpg] Г. э. является полный k-дольный граф, мощности долей к-рого отличаются не более чем на единицу (см. [3]). На Г. э. изучаемые числовые характеристики достигают своего глобального экстремума. Так наз. критические графы могут рассматриваться как локально оптимальные. Пусть заданы нек-рое свойство. [img: http://localhost:8080/file/010429-27.jpg] Аи набор одноместных операций [img: http://localhost:8080/file/010429-25.jpg] над графами. Граф G, обладающий свойством А, наз. критическим по свойству Аотносительно операций [img: http://localhost:8080/file/010429-26.jpg] если после применения любой из этих операций получается граф, не обладающий свойством А. При этом предполагается, что множество графов, не обладающих свойством А, замкнуто относительно рассматриваемых операций. В качестве свойства Арассматриваются такие свойства графа, как быть связным, плоским, k-хроматическим и т. п., а в качестве операций - операции удаления и добавления вершины или ребра, стягивания ребра и др. Напр., граф Петерсена (см. рис.) является критическим по свойству иметь реберное хроматическое число, равное 4, относительно операции удаления ребра. Полный пятивершинный граф [img: http://localhost:8080/file/010429-28.jpg] и полный двудольный граф [img: http://localhost:8080/file/010429-29.jpg] (см. Граф плоский, рис. 1), каждая доля к-рого имеет три вершины, являются критическими по свойству не быть плоским относительно операций удаления ребра, стягивания ребра, удаления вершины. При изучении свойств и характеристик графов оказывается полезным изучение их критических подграфов, т. е. подграфов, обладающих теми или иными свойствами и являющихся минимальными (максимальными) по включению. Примеры таких подграфов - компоненты связности (k-связности), остовные деревья. Экстремальные и критич. графы служат: для описания классов графов, обладающих заданными свойствами и числовыми характеристиками; для установления взаимосвязи между различными свойствами и числовыми характеристиками; для проверки наличия того или иного свойства графа.