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

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

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

   Решение

Задачи

Страница: << 2 3 4 5 6 7 8 >> [Всего задач: 36]      



Задача 116875

Темы:   [ Текстовые задачи (прочее) ]
[ Подсчет двумя способами ]
[ Деревья ]
Сложность: 3
Классы: 10,11

Туристическая фирма провела акцию: "Купи путевку в Египет, приведи четырёх друзей, которые также купят путевку, и получи стоимость путевки обратно". За время действия акции 13 покупателей пришли сами, остальных привели друзья. Некоторые из них привели ровно по четыре новых клиента, а остальные 100 не привели никого. Сколько туристов отправились в Страну Пирамид бесплатно?

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

Задача 79244

Темы:   [ Принцип крайнего (прочее) ]
[ Связность и разложение на связные компоненты ]
[ Деревья ]
Сложность: 3+
Классы: 10

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

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

Задача 98443

Темы:   [ Шахматные доски и шахматные фигуры ]
[ Четность и нечетность ]
[ Деревья ]
[ Доказательство от противного ]
[ Многоугольники и многогранники с вершинами в узлах решетки ]
[ Замощения костями домино и плитками ]
[ Раскраски ]
[ Теорема Пика ]
Сложность: 5+
Классы: 9,10,11

Ладья, делая ходы по вертикали и горизонтали на соседнее поле, за 64 хода обошла все поля шахматной доски 8×8 и вернулась на исходное поле. Докажите, что число ходов по вертикали не равно числу ходов по горизонтали.

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

Задача 31095

Темы:   [ Степень вершины ]
[ Обход графов ]
[ Четность и нечетность ]
[ Деревья ]
[ Индукция (прочее) ]
Сложность: 4
Классы: 6,7,8

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

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

Задача 65677

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

В однокруговом хоккейном турнире принимало участие 2016 команд. По регламенту турнира за победу даётся 3 очка, за поражение 0 очков, а в случае ничьей назначается дополнительное время, победитель которого получает 2 очка, а проигравший – 1 очко. По окончании турнира Остапу Бендеру сообщили количество очков, набранных каждой командой, на основании чего он сделал вывод, что не менее N матчей закончились дополнительным временем. Найдите наибольшее возможное значение N.

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

Страница: << 2 3 4 5 6 7 8 >> [Всего задач: 36]      



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

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