Устойчивая проблема соответствия

Question

Я сейчас читаю книгу Алгоритма и столкнулся с проблемой Устойчивого Сопоставления.И мне пришло в голову вопрос, который мне интересен, но книга не отвечает.В каждом SMP можно ли всегда иметь одну пару, где каждая предпочитает другую больше всего?Как в примере с классическим браком.Всегда ли есть пара, в которой есть одна женщина и один мужчина, где оба ставят друг друга на первое место?

Answer 1

Пример счетчика:

M1 prefers W1.
M2 prefers W2.
W1 prefers M2.
W2 prefers M1.

Невозможно спариться, когда оба члена пары получают наибольшее предпочтение.