ЭКСТРЕМАЛЬНЫЕ ЗАДАЧИ в теории графов

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

в схему: заданы некоторые графы требуется найти наибольшее ребер, какое может содержать -вершинный граф в который не вложим по крайней мере один из исходных (граф К вложим в L, если в L существует часть, изоморфная К); кроме того, требуется описать мн-во всех графов, экстремальных для

Наибольший вклад в разработку методов решения задач указанного типа внесли венгер. математики. Первую такую задачу поставил и решил в 1940 П. Туран. Он доказал, что при любом натуральном единственным экстремальным -вершияным графом для полного графа является граф описываемый следующим образом: пусть — остаток от деления на ; разобьем вершин графа на непересекающихся подмн-в, из которых содержат по вершин, а остальные подмн-в — по вершин; две вершины смежны тогда и только тогда, когда они принадлежат различным подмн-вам. Подсчитано, что к-во ребер графа равно

Как правило, определить экстрем, граф его ребер удается лишь при достаточно больших значениях . В связи с этим многие авторы исследовали предельные свойства экстрем. графов. Доказано, что если миним. из хроматических чисел графов экстрем. граф для этих графов, то Здесь ребер графа К, с — положительная константа, зависящая от Этот результат значительно усиливает следующая теорема. Пусть граф экстремальный для графов Если для всех хроматическое число причем для некоторой раскраски графа при помощи цветов цветом «1» окрашено вершин, то

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

Миним. информацию предельные теоремы дают при . В этом случае ключевой, но еще не решенной задачей является задача отыскания экстрем, графа для полного двудольного графа с к-вом вершин в каждой доле t. Установлено, что к-во ребер такого графа не превосходит некоторая константа), однако хорошие нижние оценки при произвольном t неизвестны.

Для решения некоторых экстрем, задач при больших значениях существует т. н. метод прогрессивной индукции, основанный на использовании предельных теорем. В частности, доказана следующая теорема. Для того, чтобы граф был экстремальным для графов начиная с некоторого необходимо и достаточно, чтобы и для некоторого в графе существовало ребро, удаление которого уменьшало бы хроматическое число графа. При этих условиях граф при достаточно большом является единственным экстрем, графом.

Лит.: 3ыков А. А. О некоторых свойствах линейных комплексов. «Математический сборник. Новая серия», 1949, т. 24, № 2; Ершов А. П., Корпухин Г. И. Об оценках хроматического числа связных графов. «Доклады АН СССР», 1962, т. 142, № 2; Визинг В. Г. О числе ребер в графе с данным радиусом. «Доклады АН СССР», 1967, т. 173, № 6; Тuг А п P. On the theory of graphs. «Colloquium mathematicum», 1954, у. 3, M 1; Simоnоуits M. A method for solving extremal problems in graph theory, stability problems. В кя.: Theory craphs. Budapest, 1968. М. К. Гольдберг.