Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Теорема
Пусть . Тогда
Доказательство 1) Пусть , - одноцветные классы, . Следовательно, Но - независимые множества в G. Следовательно, - клики в , а значит . В свою очередь . Имеем . 2) Известно, что среднее геометрическое не превосходит среднего арифметического:
3) Доказательство проведем индукцией по р. База индукции Если р=1, то . Шаг индукции Пусть для всех графов с (р-1) вершинами. Рассмотрим граф Gс р вершинами, где v– произвольная вершина этого графа. Очевидно, что и . Пусть d(v) - степень вершины v. Тогда в графе степень вершины v: . Имеем . Действительно, и, если бы , то вершину v можно было бы раскрасить в любой из свободных цветов и получить раскраску графа G. Аналогично, . Таким образом . 4) Имеем (опять используем то, что среднее арифметическое больше среднего геометрического). Отсюда .
|