6) Известно, что каждая кошка прогнала четыре мышки, и что каждая мышка убежала от трех кошек. Кого больше, кошек или мышек? Постройте граф для решения этой задачи.

Разберём задачу по шагам и построим граф. 1) Обозначения - Пусть C — число кошек. - Пусть M — число мышек. 2) Формулировка условий как графовые величины - Каждая кошка прогнала 4 мышки. Это значит, что суммарно по сторонам кошек всего совершено 4C “взаимодействий” (ребер в связях между кошками и мышками). - Каждая мышка убежала от 3 кошек. Это значит, что суммарно по сторонам мышек всего 3M “взаимодействий”. 3) Равенство количества ребер - В такой задаче каждое взаимодействие — это связи между одной кошкой и одной мышкой. Поэтому общее число ребер E должно быть одинаковым, считая слева и справа: E = 4C = 3M. 4) Соотношение кошек и мышек - Из 4C = 3M следует M = (4/3)C. Значит M > C для любого положительного целого C. - Общий целочисленный набор решений: C = 3k, M = 4k, где k — положительное целое число. Наименьшее (когда задача решается наименьшими числами) — C = 3 кошки и M = 4 мыши. 5) Граф для иллюстрации - Граф будет бипартитным: левая часть — кошки, правая — мыши. В непосредственном примере к малым числам возьмём k = 1. - Узлы: - Кошки: C1, C2, C3 - Мыши: M1, M2, M3, M4 - Ребра (покажем все пары): каждая кошка связана со всеми четырьмя мышками. - C1 — M1, M2, M3, M4 - C2 — M1, M2, M3, M4 - C3 — M1, M2, M3, M4 6) Проверка графа - Степени кошек: deg(C1) = deg(C2) = deg(C3) = 4 — условие выполнено. - Степени мышек: deg(M1) = deg(M2) = deg(M3) = deg(M4) = 3 — условие выполнено. - Общее число ребер: 12 (3 кошки × 4 мыши), что равно 4C = 12 и равно 3M = 12. 7) Вывод - Мышек больше, чем кошек. Отношение M:C = 4:3 (в общем виде M = 4k, C = 3k). - В минимальном примере (3 кошки и 4 мыши) видно явное превосходство мышек. Если нужно, могу привести ещё один вариант графа для другого k (например, C = 6, M = 8) с аналогичным подходом, но с тем же соотношением степеней: каждая кошка имеет степень 4, каждая мышка — степень 3.