Главная /
Приёмы доказательств в теории графов /
Какой метод использован при доказательстве следующей теоремы? Теорема. Не существует графа без петель и кратных рёбер, вершины которого имеют попарно различные степени. Доказательство. Предположим, что n вершин графа имеют попарно различные степени. Таким
Какой метод использован при доказательстве следующей теоремы?
Теорема. Не существует графа без петель и кратных рёбер, вершины которого имеют попарно различные степени.
Доказательство. Предположим, что n вершин графа имеют попарно различные степени. Таким образом, граф содержит вершины степеней 0, 1,…, n-1. Наличие вершин степени 0 и n-1 даёт противоречие.
вопросПравильный ответ:
Доказательство по индукции
Доказательство от противного
Метод резолюции
Метод натурального исчисления
Сложность вопроса
74
Сложность курса: Приёмы доказательств в теории графов
72
Оценить вопрос
Комментарии:
Аноним
спасибо за ответ
13 фев 2016
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # Какой метод использован при доказательстве следующей теоремы? Теорема. Двудольный граф не содержит циклов нечётной длины. Доказательство. Любому циклу двудольного графа соответствует последовательность вида a(1)b(1)a(2)b(2)…a(1), где a(i) и b(i) - вершины первой и второй долей. Указанная последовательность содержит нечётное число элементов, что соответствует чётной длине цикла.
- # Доказательство теоремы Дирака осуществляется методом:
- # В комнате, в которой нет света, разбросано бесконечное число носков 3 цветов. Какое минимальное количество носков, взятых из комнаты, достаточно для составления пары 1 цвета?
- # Всем помеченным деревьям на n вершинах могут быть поставлены в соответствие различные наборы из n-2 натуральных чисел. Наоборот, каждый из указанных наборов соответствует вполне определённому дереву. Каково количество помеченных деревьев на 5 вершинах?
- # Определить X, если последовательность 9,X,7,3,3,3,2,2,2,2 является разбиением простого графа. Рекомендация: использовать критерий Гавела-Хакими более 1 раза, при необходимости упорядочивая образующиеся последовательности.