Каталог по темам

Задачи

Страница: << 125 126 127 128 129 130 131 >> [Всего задач: 1006]

Задача 30806

Темы:	[	Обход графов	]
	[	Деревья	]
	[	Четность и нечетность	]
	[	Индукция (прочее)	]

Сложность: 4
Классы: 8,9

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

Прислать комментарий

Решение

Задача 30824

Темы:	[	Ориентированные графы	]
	[	Обход графов	]
	[	Индукция (прочее)	]

Сложность: 4
Классы: 8,9

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

Прислать комментарий

Решение

Задача 31091

Темы:	[	Степень вершины	]
	[	Обход графов	]
	[	Принцип крайнего (прочее)	]
	[	Доказательство от противного	]

Сложность: 4
Классы: 6,7,8

В графе 20 вершин, степень каждой не меньше 10. Доказать, что в нём есть гамильтонов путь.

Прислать комментарий

Решение

Задача 31104

Темы:	[	Теория графов (прочее)	]
	[	Степень вершины	]
	[	Принцип крайнего (прочее)	]
	[	Неравенство Коши	]
	[	Разбиения на пары и группы; биекции	]

Сложность: 4
Классы: 6,7,8

а) Какое наибольшее число рёбер может быть в 30-вершинном графе, в котором нет треугольников?
б) Какое наибольшее число рёбер может быть в 30-вершинном графе, в котором нет полного подграфа из четырёх вершин?

Прислать комментарий

Решение

Задача 35166

Темы:	[	Разбиения на пары и группы; биекции	]
Темы:	[	Сочетания и размещения	]

Сложность: 4
Классы: 10,11

На собеседовании десяти человекам был предложен тест, состоящий из нескольких вопросов. Известно, что любые пять человек ответили вместе на все вопросы (то есть на каждый вопрос хоть один из пяти дал правильный ответ), а любые четыре – нет. При каком минимальном количестве вопросов это могло быть?

Прислать комментарий

Решение

Страница: << 125 126 127 128 129 130 131 >> [Всего задач: 1006]