Главная /
Приёмы доказательств в теории графов /
Какой метод использован при доказательстве следующей теоремы? Теорема. Двудольный граф не содержит циклов нечётной длины. Доказательство. Любому циклу двудольного графа соответствует последовательность вида a(1)b(1)a(2)b(2)…a(1), где a(i) и b(i) - вершины
Какой метод использован при доказательстве следующей теоремы?
Теорема. Двудольный граф не содержит циклов нечётной длины.
Доказательство. Любому циклу двудольного графа соответствует последовательность вида a(1)b(1)a(2)b(2)…a(1), где a(i) и b(i) - вершины первой и второй долей. Указанная последовательность содержит нечётное число элементов, что соответствует чётной длине цикла.
вопросПравильный ответ:
Доказательство по индукции
Конструктивное доказательство
Метод резолюции
Метод натурального исчисления
Сложность вопроса
86
Сложность курса: Приёмы доказательств в теории графов
72
Оценить вопрос
Комментарии:
Аноним
Если бы не данные решения - я бы не справился c этими тестами intuit.
08 фев 2017
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # Установив взаимно однозначное соответствие с сочетаниями 3 из 10 объектов, определить число треугольников, содержащихся в помеченном графе K10.
- # Установив взаимно однозначное соответствие с сочетаниями 4 из 11 объектов, определить число графов K4 , содержащихся в помеченном графе K11.
- # Сколько помеченных 3,2-графов (двудольных графов с 3 и 2 вершинами в первой и второй долях)?
- # При каком значении X последовательность 4,X,2,1,1 является разбиением простого графа?
-
#
Укажите матрицу, соответствующую двудольному графу:
![]()
