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.