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

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

Упражнение 1:
Номер 1

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

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

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


Ответ:

 (1) Доказательство по индукции 

 (2) Доказательство от противного 

 (3) Метод резолюции 

 (4) Метод натурального исчисления 


Номер 2

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

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

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


Ответ:

 (1) Доказательство по индукции 

 (2) Конструктивное доказательство 

 (3) Метод резолюции 

 (4) Метод натурального исчисления 


Номер 3

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

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

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


Ответ:

 (1) Доказательство по индукции 

 (2) Доказательство от противного 

 (3) Метод Хао Вонга 

 (4) Метод натурального исчисления 


Упражнение 2:
Номер 1
Необходимое условие теоремы Холла есть непосредственное следствие принципа:

Ответ:

 (1) Ле Шателье 

 (2) Перечисления 

 (3) Дирихле 

 (4) Паули 


Номер 2
Доказательство истинности критерия Гавела-Хакими осуществляется методом:

Ответ:

 (1) Графического разбиения 

 (2) Монте-Карло 

 (3) Бесконечного спуска 

 (4) Гаусса 


Номер 3
Доказательство теоремы Дирака осуществляется методом:

Ответ:

 (1) Гамильтоновых циклов 

 (2) От противного 

 (3) Возняка 

 (4) Крамера 


Упражнение 3:
Номер 1
В комнате, в которой нет света, разбросано бесконечное число носков 2 цветов. Какое минимальное количество носков, взятых из комнаты, достаточно для составления пары 1 цвета?

Ответ:

 3 


Номер 2
В комнате, в которой нет света, разбросано бесконечное число носков 3 цветов. Какое минимальное количество носков, взятых из комнаты, достаточно для составления пары 1 цвета?

Ответ:

 4 


Номер 3
В комнате, в которой нет света, разбросано бесконечное число носков 4 цветов. Какое минимальное количество носков, взятых из комнаты, достаточно для составления пары 1 цвета?

Ответ:

 5 


Упражнение 4:
Номер 1
Установив взаимно однозначное соответствие с сочетаниями 3 из 10 объектов, определить число треугольников, содержащихся в помеченном графе K10.

Ответ:

 120 


Номер 2
Установив взаимно однозначное соответствие с сочетаниями 4 из 11 объектов, определить число графов K4 , содержащихся в помеченном графе K11.

Ответ:

 330 


Номер 3
Установив взаимно однозначное соответствие с сочетаниями 2 из 15 объектов, определить число рёбер графа K15.

Ответ:

 105 


Упражнение 5:
Номер 1
Всем помеченным деревьям на n вершинах могут быть поставлены в соответствие различные наборы из n-2 натуральных чисел. Наоборот, каждый из указанных наборов соответствует вполне определённому дереву. Каково количество помеченных деревьев на 5 вершинах?

Ответ:

 125 


Номер 2
Всем помеченным деревьям на n вершинах могут быть поставлены в соответствие различные наборы из n-2 натуральных чисел. Наоборот, каждый из указанных наборов соответствует вполне определённому дереву. Каково количество помеченных деревьев на 6 вершинах?

Ответ:

 1296 


Номер 3
Всем помеченным деревьям на n вершинах могут быть поставлены в соответствие различные наборы из n-2 натуральных чисел. Наоборот, каждый из указанных наборов соответствует вполне определённому дереву. Каково количество помеченных деревьев на 4 вершинах?

Ответ:

 105 


Упражнение 6:
Номер 1
Сколько помеченных 2,3-графов (двудольных графов с 2 и 3 вершинами в первой и второй долях)?

Ответ:

 64 


Номер 2
Сколько помеченных 3,3-графов (двудольных графов с 3 вершинами в каждой доле)?

Ответ:

 512 


Номер 3
Сколько помеченных 3,2-графов (двудольных графов с 3 и 2 вершинами в первой и второй долях)?

Ответ:

 64 


Упражнение 7:
Номер 1
При каком значении X последовательность 4,X,2,1,1 является разбиением простого графа?

Ответ:

 2 


Номер 2
При каком значении X последовательность 4,X,3,2,2 является разбиением простого графа?

Ответ:

 3 


Номер 3
При каком значении X последовательность 4,3,3,3,X является разбиением простого графа?

Ответ:

 3 


Упражнение 8:
Номер 1
Определить X, если последовательность 7,X,5,3,2,2,2,2 является разбиением простого графа. Рекомендация: использовать критерий Гавела-Хакими более 1 раза, при необходимости упорядочивая образующиеся последовательности.

Ответ:

 5 


Номер 2
Определить X, если последовательность 8,X,6,3,3,2,2,2,2 является разбиением простого графа. Рекомендация: использовать критерий Гавела-Хакими более 1 раза, при необходимости упорядочивая образующиеся последовательности.

Ответ:

 6 


Номер 3
Определить X, если последовательность 9,X,7,3,3,3,2,2,2,2 является разбиением простого графа. Рекомендация: использовать критерий Гавела-Хакими более 1 раза, при необходимости упорядочивая образующиеся последовательности.

Ответ:

 7 


Упражнение 9:
Номер 1
Укажите двудольные графы с паросочетанием из 2 рёбер:
	

Ответ:

 (1)

 (2)

 (3)

 (4)


Номер 2
Укажите двудольные графы с паросочетанием из 2 рёбер:
	

Ответ:

 (1)

 (2)

 (3)

 (4)


Номер 3
Укажите двудольные графы с паросочетанием из 2 рёбер:
	

Ответ:

 (1)

 (2)

 (3)

 (4)


Упражнение 10:
Номер 1
Укажите матрицу, соответствующую двудольному графу:
	

Ответ:

 (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  


Номер 2
Укажите матрицу, соответствующую двудольному графу:
	

Ответ:

 (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  


Номер 1
Укажите матрицу, соответствующую двудольному графу:
	

Ответ:

 (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  




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