ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Фильтр
Сложность с по   Класс с по  
Выбрана 1 задача
Версия для печати
Убрать все задачи

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

   Решение

Задачи

Страница: << 17 18 19 20 21 22 23 >> [Всего задач: 383]      



Задача 111780

Темы:   [ Теория графов (прочее) ]
[ Разбиения на пары и группы; биекции ]
[ Принцип Дирихле (прочее) ]
[ Доказательство от противного ]
Сложность: 3+
Классы: 8,9,10

25 мальчиков и несколько девочек собрались на вечеринке и обнаружили забавную закономерность. Если выбрать любую группу не меньше чем из 10 мальчиков, а потом добавить к ним всех девочек, знакомых хотя бы с одним из этих мальчиков, то в получившейся группе число мальчиков окажется на 1 меньше, чем число девочек. Докажите, что некоторая девочка знакома не менее чем с 16 мальчиками.

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

Задача 116441

Темы:   [ Теория графов (прочее) ]
[ Классическая комбинаторика (прочее) ]
[ Примеры и контрпримеры. Конструкции ]
Сложность: 3+
Классы: 9,10,11

Автор: Фольклор

В некотором государстве система авиалиний устроена таким образом, что каждый город соединен авиалиниями не более чем с тремя другими, и из каждого города можно попасть в любой другой, сделав не более одной пересадки. Какое наибольшее количество городов может быть в этом государстве?

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

Задача 67312

Темы:   [ Теория графов (прочее) ]
[ Оценка + пример ]
Сложность: 3+
Классы: 8,9,10,11

Автор: Метелев Д.

В клуб любителей гиперграфов в начале года записались $n$ попарно незнакомых школьников. За год клуб провёл $100$ заседаний, причём каждое заседание посетил хотя бы один школьник. Два школьника знакомились, если было хотя бы одно заседание, которое они оба посетили. В конце года оказалось, что количество знакомых у каждого школьника не меньше, чем количество заседаний, которые он посетил. Найдите минимальное значение $n$, при котором такое могло случиться.
Прислать комментарий     Решение


Задача 30783

Темы:   [ Связность и разложение на связные компоненты ]
[ Четность и нечетность ]
[ Доказательство от противного ]
Сложность: 4-
Классы: 7,8,9

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

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

Задача 30790

Тема:   [ Деревья ]
Сложность: 4-
Классы: 8

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

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

Страница: << 17 18 19 20 21 22 23 >> [Всего задач: 383]      



© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .