Веселые картинки

дефолтная задача теории графов о кенингсбергских мостах

объяснение весьма просто

мост = дверь = ребро графа

остров = комната = вершина графа

буду как тут в картинках юзать двери и комнаты

дверь всегда соединяет 2 комнаты, тут объяснять нечего

из-за этого общее количество дверей обязано быть четным, ведь иначе одна из дверей ведет вникуда.

так как общее количество дверей должно быть четным, у тебя есть два варианта

либо четное количество дверей во всех комнатах, либо количество комнат с нечетным количеством дверей будет четным. Только в этом случае общая сумма может остаться четной

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

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

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

но наш граф позволяет случаи с четным количеством комнат с нечетным количеством дверей.

единственный возможный вариант нормально обработать комнату с нечетным количеством дверей, это либо не входить в нее откуда-то, либо не выходить из нее

а такой вариант возможен лишь тогда, когда ты стартуешь в комнате с нечетным количеством дверей и когда заканчиваешь в такой же комнате

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

в одной из комнат ты просто застрянешь, войдя в нее, но потеряв возможность выхода.

в задаче

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

4 таких комнаты очевидно больше допустимых 2 комнат, итого пройти нельзя, в одной из комнат с нечетным количеством дверей ты застрянешь

а в задаче, что скинул умник

у тебя лишь две комнаты с нечетным количеством дверей.

внешняя комната имеет 4 двери.

итого начиная в одной из этих двух комнат, и заканчивая в другой, ты нарисуешь себе путь.

например

бля, чет стена