Паросочетания и супергерои

[comichelle]

В прошлом году обсуждали с Лёшей, что в качестве "жизненного примера" для поиска максимального паросочетания приводят "задачу о свадьбах". А где же однополые браки? А где браки не двух людей, а больше? Скучно!

Мы тогда придумали кучу других интерпретаций, я уже почти все забыла, но что-то всплывает в памяти.

Comments

просто

[a_shen]

искать максимальное паросочетание в двудольном графе проще, поэтому часто этим и ограничиваются...

Re: просто

[comichelle]

Да не, это понятно. Просто скучная интерпретация получается, усложнять задачу я не предлагаю:)

и да,

[a_shen]

стандартная олимпиадная интерпретация теоремы Холла говорит. что если в школе есть несколько кружков, и начальство хочет назначить в каждом старосту, чтобы никто не был старостой сразу двух, то препятствие состоит в $k$ кружках, в которых всего меньше $k$ участников...

Re: и да,

[comichelle]

Этого я не знала, спасибо!

[anonymous]

Читай экономику, все случаи разобраны.

Забавные матчмэйкинги троек есть - хорошо приложимые к проблеме расселения студентов)

[comichelle]

"все случаи разобраны."
Все случаи прикольных интерпретаций?:)