VI Международная студенческая научная конференция Студенческий научный форум - 2014

Пусть — список фиксированных «запрещенных» подграфов. Требуется вычислить величину — наибольшее возможное число ребер в -вершинном графе, не содержащем в себе в качестве подграфа например, фиксированного графа или ни одного графа из списка запрещенных подграфов .

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

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

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

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

Рис. 1 -Полный двудольный граф не имеет треугольников.

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

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

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

Пример.Рассмотрим граф на множестве вершин, т.е. 9-ти вершин. Теорема Турана нам дает:

_{Из теоремы 2 следует, что}

Полный граф из вершин содержит ,(Рис.2 ) следовательно:.

Рис. 2–Полный граф

Тогда (рис. 3) .

Рис. 3-Трехдольный полный граф с максимальным количеством ребер без

список использованной литературы

1. Баранов В. И., Стечкин Б. С. Экстремальные комбинаторные задачи и их приложения. — М.: ФИЗМАТЛИТ, 2004. - 240с.

2. Stasys Jukna. Extremal Combinatorics. Springer- Verlag Berlin Heidelberg 2001, 2011.

3. О.И. Мельников. Теория графов в занимательных задачах.- М.: Книжный дом «ЛИБРИКОМ», 2013.-240с.