Главная /
Приёмы доказательств в теории графов /
В комнате, в которой нет света, разбросано бесконечное число носков 3 цветов. Какое минимальное количество носков, взятых из комнаты, достаточно для составления пары 1 цвета?
В комнате, в которой нет света, разбросано бесконечное число носков 3 цветов. Какое минимальное количество носков, взятых из комнаты, достаточно для составления пары 1 цвета?
вопросПравильный ответ:
4
Сложность вопроса
78
Сложность курса: Приёмы доказательств в теории графов
72
Оценить вопрос
Комментарии:
Аноним
Я провалил зачёт, почему я не углядел этот великолепный сайт с решениями с тестами intuit до сессии
26 сен 2018
Аноним
Если бы не опубликованные подсказки - я бы не смог решить c этими тестами интуит.
27 ноя 2015
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # Какой метод использован при доказательстве следующей теоремы? Теорема. Не существует графа без петель и кратных рёбер, вершины которого имеют попарно различные степени. Доказательство. Предположим, что n вершин графа имеют попарно различные степени. Таким образом, граф содержит вершины степеней 0, 1,…, n-1. Наличие вершин степени 0 и n-1 даёт противоречие.
- # Какой метод использован при доказательстве следующей теоремы? Теорема. Любое дерево на n >= 2 вершинах содержит 2 висячие вершины. Доказательство. Рассмотрим цепь наибольшей длины, обратившись к любой из её концевых вершин (A). Если степень A отлична от 1, то существует вершина B, смежная с A и отличная от вершины, смежной с A в цепи. Если B не принадлежит цепи, то цепь не максимальна, что противоречит условию. С другой стороны, B не содержится в цепи, так как это ведёт к образованию цикла в дереве.
- # Установив взаимно однозначное соответствие с сочетаниями 2 из 15 объектов, определить число рёбер графа K15.
- # Всем помеченным деревьям на n вершинах могут быть поставлены в соответствие различные наборы из n-2 натуральных чисел. Наоборот, каждый из указанных наборов соответствует вполне определённому дереву. Каково количество помеченных деревьев на 5 вершинах?
- # При каком значении X последовательность 4,3,3,3,X является разбиением простого графа?