Файл: Серия Паросочетания .pdf

Серия 3. Паросочетания +
1. В графе есть вершина a степени 1 и вершина b степени 101, а степени всех остальных вершин равны
10. Докажите, что в этом графе есть ab-путь.
2. В графе G есть гамильтонов цикл. Докажите, что для любого множества S ⊂ V (G) в графе G − S
не более чем |S| компонент связности.
3. На курсе Архитектура Компьютера в Университете ИТМО студенты проверяют эссе друг друга. Так получилось, что каждая из 100 девочек послала одному или нескольким из 100 мальчиков свое эссе. Всего было послано больше 100 эссе. Докажите, что какой-то ленивый мальчик может выкинуть все полученные им эссе и ничего не проверять так, что при этом эссе каждой девочки останется у кого-либо из остальных мальчиков.
4. Из бумаги вырезан квадрат. Сверху на нем красным цветов нарисовано разбиение на 2021 равнове- ликих треугольников, а снизу зеленым цветом нарисовано разбиение на 2021 равновеликих треугольников.
Докажите, что можно проткнуть квадрат 2021 булавками так, чтобы каждый заленый и каждый красный треугольник был проткнут во внутренней точке ровно одной булавкой.
5. а) Для курса продвинутой математики на ВТ пригласили 101 преподавателя. Оказалось, что многие раньше работали вместе и любых 100 из них можно разбить на 50 пар знакомых. Какое наименьшее число пар знакомых может быть в среди преподавателей продвинутой математики?
б) После проведения контрольных многих студентов отчислили и больше на курсе не нужно так много преподавателй, поэтому их всех уволили и заново набрали 100 человек. Оказалось, что любых 98 из них можно разбить на 49 пар знакомых. Какое наименьшее число пар знакомых может быть среди препода- вателей теперь?
6. Докажите, что из любого связного графа с четным числом вершин можно удалить несколько ребер
(возможно, 0) таким образом, чтобы в полученном графе степени всех вершин оказались нечетны.
7. Докажите теорему Холла, увеличивая максимальное паросочетание с помощью метода дополняю- щих путей.
Серия 3. Паросочетания +
1. В графе есть вершина a степени 1 и вершина b степени 101, а степени всех остальных вершин равны
10. Докажите, что в этом графе есть ab-путь.
2. В графе G есть гамильтонов цикл. Докажите, что для любого множества S ⊂ V (G) в графе G − S
не более чем |S| компонент связности.
3. На курсе Архитектура Компьютера в Университете ИТМО студенты проверяют эссе друг друга. Так получилось, что каждая из 100 девочек послала одному или нескольким из 100 мальчиков свое эссе. Всего было послано больше 100 эссе. Докажите, что какой-то ленивый мальчик может выкинуть все полученные им эссе и ничего не проверять так, что при этом эссе каждой девочки останется у кого-либо из остальных мальчиков.
4. Из бумаги вырезан квадрат. Сверху на нем красным цветов нарисовано разбиение на 2021 равнове- ликих треугольников, а снизу зеленым цветом нарисовано разбиение на 2021 равновеликих треугольников.
Докажите, что можно проткнуть квадрат 2021 булавками так, чтобы каждый заленый и каждый красный треугольник был проткнут во внутренней точке ровно одной булавкой.
5. а) Для курса продвинутой математики на ВТ пригласили 101 преподавателя. Оказалось, что многие раньше работали вместе и любых 100 из них можно разбить на 50 пар знакомых. Какое наименьшее число пар знакомых может быть в среди преподавателей продвинутой математики?
б) После проведения контрольных многих студентов отчислили и больше на курсе не нужно так много преподавателй, поэтому их всех уволили и заново набрали 100 человек. Оказалось, что любых 98 из них можно разбить на 49 пар знакомых. Какое наименьшее число пар знакомых может быть среди препода- вателей теперь?
6. Докажите, что из любого связного графа с четным числом вершин можно удалить несколько ребер
(возможно, 0) таким образом, чтобы в полученном графе степени всех вершин оказались нечетны.
7. Докажите теорему Холла, увеличивая максимальное паросочетание с помощью метода дополняю- щих путей.