Теорема о связности графа
Пусть дан связный граф с n вершинами. Тогда в нем не менее n–1 ребер. Пусть граф с n вершинами распадается на с компонент связности. Тогда в нем не менее n–c ребер. Дан связный графе с n вершинами.В графе нет циклов (= он – дерево) ⬄ в графе n–1 ребро.
1. а) Можно ли рёбра куба раскрасить в два цвета так, чтобы между любыми двумя вершинами был путь как по рёбрам одного цвета, так и по ребрам другого цвета?
б) Можно ли рёбра графа на рисунке раскрасить в два цвета так, чтобы между любыми двумя вершинами был путь как по рёбрам одного цвета, так и по ребрам другого цвета?
2. Тетрадный лист раскрасили в 23 цвета по клеткам (при этом все цвета присутствуют). Пара цветов называется хорошей, если найдутся две соседние клетки, закрашенные этими цветами. Каково минимальное число хороших пар?
3. Есть n камней разного веса. За одно взвешивание на чашечных весах без гирь можно сравнить два камня. За какое наименьшее число взвешиваний можно наверняка найти самый лёгкий камень?
Сумма степеней вершин
Теорема. а) Сумма степеней вершин графа вдвое больше числа его ребер.
б) В конечном графе число вершин нечетной степени четно.
4. Легко разбить треугольник на 3 меньших треугольника так, чтобы треугольники граничили друг с другом или с исходлным только по целой стороне. А можно ли так разбить его на 4 треугольника?
5. В пустые клетки доски 5×5 Петя по одному вписывал числа. Вписанное число равнялось количеству соседних по стороне клеток, в которые уже был вписаны числа. Петя заполнил всю доску. Найдите сумму все чисел и докажите, что она не зависит от порядка заполнения.
6. В однокруговом турнире участвовали 15 команд. Докажите, что хотя бы в одной игре встретились команды, которые перед этой игрой участвовали в сумме в нечетном числе игр этого турнира.
Двудольные графы
Определение. Граф – двудольный, если его вершины можно раскрасить в два цвета так, что не будет ребер с концами одинакового цвета. Пример: любое дерево.
7. Какое наибольшее число рёбер может быть в двудольном графе а) с 2n вершинами; б) с 2n+1 вершиной?
8. В классе 30 человек. За месяц было 29 дежурств, в каждом дежурила пара учеников. Докажите, что можно так выставить всем ученикам класса по одной оценке по 5-балльной шкале, что будет выставлена хотя бы одна пятерка, и в каждой паре дежуривших сумма оценок будет равна 8.
Зачетные задачи
УГ1. Промежуток из одного или несколько подряд идущих дней назовем нечетным, если нечетное число из этих дней были дождливыми. Каково наибольшее возможное число нечетных промежутков в июле?
УГ2. Для игры в классики на земле нарисован ряд клеток, в которые вписаны по порядку числа от 1 до 10 (см. рис). Маша прыгнула снаружи в клетку 1, затем попрыгала по остальным клеткам (каждый прыжок – на соседнюю по стороне клетку) и выпрыгнула наружу из клетки 10. Известно, что на клетке 1 Маша была 1 раз, на клетке 2 – 2 раза, ..., на клетке 9 – 9 раз. Сколько раз побывала Маша на клетке 10?
УГ3. Какое наибольшее число клеток доски 9×9 можно разрезать по обеим диагоналям, чтобы при этом доска не распалась на несколько частей?
Малый мехмат, 8 класс, июль 2017 г, http://www. ashap. info/Uroki/Bolgar2/2017/8-1/index. html
