Этюды для программистов

6. (Продвинуться или вернуться?) Если текущаявершина получила допустимый цвет, мы хотим перейти к следующей вершине; в противном случае необходимо отступить. Поэтому, если цвет [текущаявершина] > старшийцвет, установить цвет [текущаявершина] равным нулю и уменьшить значение текущаявершина на единицу; в противном случае увеличить значение текущаявершина на единицу. Заметьте, что цвета вершин с номерами большими, чем текущаявершина, по-прежнему нулевые и что, когда мы возвращаемся к уже раскрашивавшейся вершине, мы продолжаем продвигать ее цвет со значения, оставшегося от предыдущей обработки.

7. (Добавление цвета, если это необходимо.) Если вершина нулевая, увеличить старшийцвет на единицу и установить значение текущаявершина равным единице. Если мы вернулись к самому началу, число цветов необходимо увеличить.

Легко видеть, что данный алгоритм должен завершиться. В крайнем случае, он остановится, когда все вершины получат разные цвета. Также достаточно ясно, что перед началом каждого прохождения основного цикла все вершины от первой до (текущаявершина — 1) имеют допустимую раскраску. Чуть менее очевидно, что старшийцвет увеличивается только тогда, когда невозможно раскрасить некий начальный подграф выделенным числом цветов. Удостовериться в этом вам помогут эксперименты на небольших графах. Заметьте, что алгоритм правильно работает для пустого графа, для графов, все вершины которых изолированы, и для графов, все вершины которых связаны.

Реализация

В нашей реализации мы используем Фортран. Ясно, что Фортран — очень бедный язык, с недостаточными возможностями определения данных и управления последовательностью действий. Однако мы выбрали его как раз для того, чтобы показать, что даже на неудобном языке можно написать хорошо структурированную, ясную программу. Теоретически каждую программу можно было бы написать на более новом, более выразительном языке; на практике большинству программистов время от времени приходится работать на архаичном языке, но плохие инструменты не могут служить оправданием для плохого программирования.

Логическую функцию связь на Фортране можно представить двумерным логическим массивом, в котором (i,j)-й элемент имеет значение истина тогда и только тогда, когда вершина i связана с вершиной j. Первый элемент ввода — это запись с количеством вершин раскрашиваемого графа. Затем читаются наборы записей, где каждый набор описывает связи одной вершины. Первая запись набора содержит номер вершины и количество ее соседей; в оставшихся записях в произвольном порядке перечисляются соседи. Признаком конца исходных данных служит нулевой номер вершины. Вершины можно описывать в произвольном порядке, а описание одной вершины можно разбивать на несколько частей. Когда вершина i связывается с вершиной j, вершина j автоматически связывается с вершиной i. Единственными возможными ошибками являются выход номера вершины за допустимые границы и попытка связать вершину с ней самой. Ниже воспроизводится реальная программа. 

Исходные данные взяты с рис. 1 из гл. 3. Штаты перенумерованы сверху вниз; столбцы упорядочены слева направо. В каждой головной перфокарте справа присутствует название штата; вследствие заданного формата существенны только первые восемь литер карты. Для экономии места в книге данные разбиты на две колонки, но в остальном они точно соответствуют требованиям программы.

Выдача выглядит наилучшим образом, если ее напечатать АЦПУ и повесить на стену. Пропорции приведенной в книге выдачи несколько нарушают симметрию. Заметьте, что горизонтальная печать решения экономит много бумаги, без всякой потери информации. Первоначально мы хотели напечатать номера и цвета вершин вертикально, что делается несколько проще, но выдача при этом получается весьма неряшливой. Реальная выдача приведена на предыдущей странице.

Замечания по программе

Строки 1—19. Заголовок программы служит тем же целям, что и аннотация в научной статье. Вне зависимости от того, велика или мала программа, в ее начале должна присутствовать такого рода информация. В частности, в программе обязательна ссылка на соответствующую внешнюю документацию.

Строки 22—26. Если бы программа была побольше, перед определением данных следовало бы поместить больше материала по алгоритмическим вопросам. В нашем же случае тексту программы предшествует полный словарь. Поскольку размеры модулей не должны превышать нескольких страниц, мы предпочли толковый словарь, в котором переменные упоминаются группами в соответствии со своей ролью, важностью и местом употребления. Очевидно, количество пояснений в словаре зависит от других комментариев, но ни одна переменная не должна быть выпущена. Мы пытались сделать шестилитерные имена мнемоничными, однако нелегко бороться против одного из глупейших фортрановских правил.