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

Вопросы укладки графа на плоскости и других поверхностях имеют свое начало в трудах Л. Эйлера, который установил, что для любого полиэдра, имеющего V вершин, Е ребер и F граней, справедливо равенство

V - Е + F = 2.

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

Через будем обозначать произвольный граф на множестве вершин , а через — граф на некотором множестве из вершин; таким образом, .

Введем следующие обозначения для специальных видов графов:

— полный граф на вершинах, т. е. ;

— полный двудольный граф на двух подмножествах вершин (долях) по р и q вершин в каждой доле соответственно; таким образом, если , то ;

Принцип Дирихле. Если — наименьшее целое при котором в каждом разбиении этого на частей найдется часть, не меньшая чем , то

.

Принцип ящиков. При любом размещении предметов по ящикам найдется ящик с по крайней мере двумя предметами.

Пусть Х некоторое множество из элементов, и семейство подмножеств.

Связь между арифметическим и геометрическим средними чисел. Для любых неотрицательных чисел справедливо следующее неравенство:

Свойства независимости множества. Пусть нам задано множество и . Множества независимы тогда и только тогда, когда ни один из них не является подмножеством другого, т.е.:

Теорема Эйлера (1736).В любом графе сумма степеней его вершин равна удвоенному количеству его ребер, и следовательно, четное число:

.

Следствие 1.для любого .

Следствие 2.

Неравенство Коши-Шварца.Дляи действительных чисел справедливо: .

Исторически первым экстремальным результатом о графах явилась следующая теорема ().

Пусть задано некоторое конечное непустое множество и семейство различных подмножеств элементов из .

Определение.Элементы множества называются вершинами гиперграфа, элементы множества называются гиперребрами гиперграфа, а пара , т.е. множество вершин и множество гиперребер, гиперграфом.

Гиперграфом на множестве вершин называется любое подмножество множества , так что элементами гиперграфа

-6-

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

однородный гиперграф или граф: все ребра имеют мощность, равную

Граф является частным случаем гиперграфов. Граф –это такой гиперграф, у которого каждое гиперребро содержит ровно две вершины.

Например: Пусть .

Т.е. вершинами такого графа является кратные к числа.

Пусть , тогда

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

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

Теорема Мантеля (1907). Если граф на вершинах содержит больше чем ребер, то он содержит треугольник.

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

.

С другой стороны, используя неравенство Коши-Шварца и теорему Эйлера мы получаем:

.

Эти два неравенства означают, что , что противоречит условию.

-7-

2)Второе доказательство. Пусть -граф на множестве из вершин и предположим, что не имеет треугольников.

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

В множестве встречается каждое ребро графа . Подсчет концы ребер в соответствии ее конечных вершин в получаем: . Из неравенства средних вытекает:

.

Теорема доказана.

Экстремальная конструкция единственна и представляет собой двудольный граф с (по возможности) равными долями, т. е. по и или в первой и второй доле соответственно. В свою очередь, непосредственная проверка удостоверяет, что .

Теорема Турана

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

Например, треугольники 3-клика. Теорема Мантеля говорит, что, если граф на множестве из вершин не имеет 3-клика то он имеет не более ребра. А что будет если ?

На этот вопрос отвечает фундаментальная теорема Пола Турана, которая инициировала экстремальную комбинаторику.

Теорема Турана. Если граф на множестве из вершин не имеет кликов, , то

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

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

Поскольку каждая пара точек в соединены ребром, то содержит ребер. Пусть число ребер соединяющих вершины из и -число ребер между вершинами из множестви _. Используя индукцию, будем иметь:

.

Так как не содержит кликов, то является смежным не более чем вершина, и мы получаем

Подводя итоги и используя тождество

Получаем

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

Для фиксированного графа F вычислить наибольшее возможное число ребер в п-вершинном графе, не содержащем в себе этого графа F в качестве подграфа.

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

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

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

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

Код для цитирования: Скопировать