Главная / Алгоритмы и дискретные структуры / Приёмы доказательств в теории графов

Приёмы доказательств в теории графов - ответы на тесты Интуит

Правильные ответы выделены зелёным цветом.
Все ответы: Курс рассчитан на заинтересованного теорией графов слушателя. На примере доказательств ряда важных теорем демонстрируются основные методы получения результатов в данной области.
Смотрите также:
Математика

Какой метод использован при доказательстве следующей теоремы?

Теорема. Не существует графа без петель и кратных рёбер, вершины которого имеют попарно различные степени.

Доказательство. Предположим, что n вершин графа имеют попарно различные степени. Таким образом, граф содержит вершины степеней 0, 1,…, n-1. Наличие вершин степени 0 и n-1 даёт противоречие.

(1) Доказательство по индукции
(2) Доказательство от противного
(3) Метод резолюции
(4) Метод натурального исчисления
Необходимое условие теоремы Холла есть непосредственное следствие принципа:
(1) Ле Шателье
(2) Перечисления
(3) Дирихле
(4) Паули
В комнате, в которой нет света, разбросано бесконечное число носков 2 цветов. Какое минимальное количество носков, взятых из комнаты, достаточно для составления пары 1 цвета?
3
Установив взаимно однозначное соответствие с сочетаниями 3 из 10 объектов, определить число треугольников, содержащихся в помеченном графе K10.
120
Всем помеченным деревьям на n вершинах могут быть поставлены в соответствие различные наборы из n-2 натуральных чисел. Наоборот, каждый из указанных наборов соответствует вполне определённому дереву. Каково количество помеченных деревьев на 5 вершинах?
125
Сколько помеченных 2,3-графов (двудольных графов с 2 и 3 вершинами в первой и второй долях)?
64
При каком значении X последовательность 4,X,2,1,1 является разбиением простого графа?
2
Определить X, если последовательность 7,X,5,3,2,2,2,2 является разбиением простого графа. Рекомендация: использовать критерий Гавела-Хакими более 1 раза, при необходимости упорядочивая образующиеся последовательности.
5
Укажите двудольные графы с паросочетанием из 2 рёбер:
(1) A
(2) B
(3) C
(4) D
Укажите матрицу, соответствующую двудольному графу:
(1) 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0
(2) 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0
(3) 1 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0
(4) 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0
Укажите матрицу, соответствующую двудольному графу:
(1) 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0
(2) 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0
(3) 1 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0
(4) 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0

Какой метод использован при доказательстве следующей теоремы?

Теорема. Двудольный граф не содержит циклов нечётной длины.

Доказательство. Любому циклу двудольного графа соответствует последовательность вида a(1)b(1)a(2)b(2)…a(1), где a(i) и b(i) - вершины первой и второй долей. Указанная последовательность содержит нечётное число элементов, что соответствует чётной длине цикла.

(1) Доказательство по индукции
(2) Конструктивное доказательство
(3) Метод резолюции
(4) Метод натурального исчисления
Доказательство истинности критерия Гавела-Хакими осуществляется методом:
(1) Графического разбиения
(2) Монте-Карло
(3) Бесконечного спуска
(4) Гаусса
В комнате, в которой нет света, разбросано бесконечное число носков 3 цветов. Какое минимальное количество носков, взятых из комнаты, достаточно для составления пары 1 цвета?
4
Установив взаимно однозначное соответствие с сочетаниями 4 из 11 объектов, определить число графов K4 , содержащихся в помеченном графе K11.
330
Всем помеченным деревьям на n вершинах могут быть поставлены в соответствие различные наборы из n-2 натуральных чисел. Наоборот, каждый из указанных наборов соответствует вполне определённому дереву. Каково количество помеченных деревьев на 6 вершинах?
1296
Сколько помеченных 3,3-графов (двудольных графов с 3 вершинами в каждой доле)?
512
При каком значении X последовательность 4,X,3,2,2 является разбиением простого графа?
3
Определить X, если последовательность 8,X,6,3,3,2,2,2,2 является разбиением простого графа. Рекомендация: использовать критерий Гавела-Хакими более 1 раза, при необходимости упорядочивая образующиеся последовательности.
6
Укажите двудольные графы с паросочетанием из 2 рёбер:
(1) A
(2) B
(3) C
(4) D
Укажите матрицу, соответствующую двудольному графу:
(1) 1 0 0 0 0 0 1 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0
(2) 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0
(3) 1 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0
(4) 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0

Какой метод использован при доказательстве следующей теоремы?

Теорема. Любое дерево на n >= 2 вершинах содержит 2 висячие вершины.

Доказательство. Рассмотрим цепь наибольшей длины, обратившись к любой из её концевых вершин (A). Если степень A отлична от 1, то существует вершина B, смежная с A и отличная от вершины, смежной с A в цепи. Если B не принадлежит цепи, то цепь не максимальна, что противоречит условию. С другой стороны, B не содержится в цепи, так как это ведёт к образованию цикла в дереве.

(1) Доказательство по индукции
(2) Доказательство от противного
(3) Метод Хао Вонга
(4) Метод натурального исчисления
Доказательство теоремы Дирака осуществляется методом:
(1) Гамильтоновых циклов
(2) От противного
(3) Возняка
(4) Крамера
В комнате, в которой нет света, разбросано бесконечное число носков 4 цветов. Какое минимальное количество носков, взятых из комнаты, достаточно для составления пары 1 цвета?
5
Установив взаимно однозначное соответствие с сочетаниями 2 из 15 объектов, определить число рёбер графа K15.
105
Всем помеченным деревьям на n вершинах могут быть поставлены в соответствие различные наборы из n-2 натуральных чисел. Наоборот, каждый из указанных наборов соответствует вполне определённому дереву. Каково количество помеченных деревьев на 4 вершинах?
105
Сколько помеченных 3,2-графов (двудольных графов с 3 и 2 вершинами в первой и второй долях)?
64
При каком значении X последовательность 4,3,3,3,X является разбиением простого графа?
3
Определить X, если последовательность 9,X,7,3,3,3,2,2,2,2 является разбиением простого графа. Рекомендация: использовать критерий Гавела-Хакими более 1 раза, при необходимости упорядочивая образующиеся последовательности.
7
Укажите двудольные графы с паросочетанием из 2 рёбер:
(1) A
(2) B
(3) C
(4) D