Читать книгу Русская Идея - Александр Исаакович Зеличенко - Страница 16

Пусть из четырех девушек, которых зовут Вера, Надя, Люба и Соня, нужно выбрать самую добрую.

Каждую спрашивают: «Какие девушки добрее тебя?».

Предположим, они отвечают так:

Вера – «Добрее меня Надя, Люба и Соня. Я самая злая.»

Надя – «Добрее меня Люба.»

Люба – «Добрее меня нет.»

Соня – «Добрее меня Вера и Люба»

В виде таблицы (матрицы) их ответы можно представить так:

Если одна девушка считает, что другая ее добрее, то ставим 1 на пересечении ряда первой девушки (ставящей оценку) с колонкой второй (получающей оценку).

В виде ориентированного графа эти ответы можно представить так.

Выделяем в этом графе циклы «кукушка-петух». Такой цикл в нашем случае один (он выделен жирным).

Теперь все голоса (ребра графа), входящие в циклы, из графа удаляем. Получаем очищенный граф голосования:

Вера и Соня, у которых нет ни одного «очищенного голоса», присваиваем ранг доброты 0 (ноль). Наде, у которой есть очищенный голос Веры, присваиваем ранг доброты на единицу больше ранга доброты Веры, то есть 1. А Любе, у которой есть 3 очищенных голоса (Веры, ранг доброты 0; Сони, ранг доброты 0, и Нади, ранг доброты 1), присваиваем ранг доброты на 1 больше максимального ранга доброты голосовавших за нее, то есть на 1 больше ранга доброты Нади. Таким образом, ранг доброты Любы – 1+1=2.