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