1. Главная
  2. Библиотека
  3. Информатика
  4. Пусть Докажите, что если в графе на n вершинах степень каждой вершины не меньше чем (n − k + 2), то граф обязательно содер...

Пусть Докажите, что если в графе на n вершинах степень каждой вершины не меньше чем (n − k + 2), то граф обязательно содержит простой цикл, длина которого не превосходит k.

«Пусть Докажите, что если в графе на n вершинах степень каждой вершины не меньше чем (n − k + 2), то граф обязательно содержит простой цикл, длина которого не превосходит k.»
  • Информатика

Условие:

Пусть

Докажите, что если в графе на n вершинах степень каждой вершины не меньше чем (n − k + 2), то граф обязательно содержит простой цикл, длина которого не превосходит k.

Решение:

то есть степень каждой вершины хотя бы 2, тогда если обозначить количество ребер в графе как m, а степень вершины v как dv, получаем

Отсюда получаем, что в нашем графе будет хотя бы один цикл. Действи...

Похожие задачи

Не нашел нужную задачу?

Воспользуйся поиском

AI помощники

Выбери предмет

E
S
А
Б
В
Г
Д
Е
Ж
З
И
К
Л
М
Н
О
П
Р
С
Т
У
Ф
Х
Ц
Ч
Э
Я