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