1626435694-d107b4090667f8488e7fa1ea1b3d0faa (844295), страница 35
Текст из файла (страница 35)
Итак 9 «.«. РАСКРАСКА ВЕРШИН ГРАФА (75) РАСКРАСКА: (лог проц ГРАФ НЕПОЛНЫЙ (и); апач и; цел и; ТЕЛО ГРАФ НЕПОЛНЫЙ /83/; цел 1, 1; НАЧАЛЬ НАЯ РАСКРАСКА; ЦИКЛ РЕДУКЦИИ /77/) (76) НАЧАЛБНАЯ РАСКРАСКА /1, О/: 1цел»; для «: = 1 шаг е(.): =.) (77) ЦИКЛ РЕДУКЦИИ /(75) 1, П, О, 1, 1/: (цел 1; г: = О; для 1: .= 1 + 1 пока ГРАФ НЕПОЛНЫЙ (1 — » + 1) цика РЕДУКЦИЯ) дрим РЕДУКЦИЯ /1, О, О, 1, Х, г/ ааключается в склеивании 1-й и Х-й вершин графа, перенумерации вершин графа, начиная с (1+ 1)-й, и в соответствующей коррекции раскраски О. Заметим, что перед г-й редукцией граф имеет 1 — г + 1 вершин. Итак (78) РЕДУКЦИЯ: (СКЛЕИВАНИЕ; КОРРЕКЦИЯ /8о/) дрим СКЛЕИВАНИЕ В, П, 1, 1, г/ состоит в прибавлении 1-й строки к 1-й строке (с симметричным преобразованием 1-го столбца).
После этого происходит фактическая редукция графа, состоящая в переносе «периферийной» части матрицы смежности так, как это порезано на рис. 4.4. Итак — 1 р-й сна«йи с /-Р гааюш Рнс. 4.4. Редукция матрицы смежности графа. (79) СКЛЕИВАНИЕ: (СЛОЖЕНИЕ; ПЕРЕНОС /81/) прим СЛОЖЕНИЕ /г, П, 1, Х, г/. Складывая 1-й столбец с 1-м, мы будем, учитывая симметричность матрицы, направлять одновременно результат и в 1-ю строку. Вспомним, что матрица смежности неориентированного графа имеет на диагонали нули (граф без петель). Так как мы складываем столбцы несмежных вершин, после сложения на диагонали останутся нули. Итак Гл. а РеАлизАция (80) СЛОЖЕНИЕ: (цел й; для й: = 1 шаг 1 до / — 1 + 1 цикл П[й, 1[: = 0[1, Й): = П[й, П + (/[Й, Х[) прим ПЕРЕНОС //, 1/, 1, Х, 1/ будет состоять в цикле переноса всех столбцов матрицы, начиная с (Х + 1)-го.
Правила алгола позволят нам не выделять отдельно случай, когда Х ) / — 1, так как в этом случае цикл не выполнится ни разу. Те компоненты столбцов, которые находятся над Х-й строкой, переносятся на одну позицию влево и одновременно заносятся в симметричную позицию матрицы. Компоненты , столбцов, находящиеся под Х-й строкой, переносятся на одну позицию влево и одну позицию вверх. Итак (81) ПЕРЕНОС: (цел /; для /: = 1 + 1 глаг 1 до 1 — / -[- 1 цикл (цел Й; для Й: = 1 шаг 1 до 1 — / + 1 цикл если Й( Х то П[й, /' — 1[: = У[/ — 1, й): = (/[Й, /) иначе если й ) Х то П[й — 1, / — 1]: = П[й,'/))) прим КОРРЕКЦИЯ /(78) /, О, 1, Х/ напоминает слияние текущих компонент связности в (42 — 45).
Так как по условию 1 ( Х, то все компоненты вектора О, равные Х, должны быть ааменены на 1. Кроме атого все компоненты, большие Х, должны быть уменьшены на единицу в связи с перенумерацией части вершин редуцируемого графа. Итак (82) КОРРЕКЦИЯ: (цел И для й = 1 шаг 1 до / цикл если О[/[ = Х то О[/[: = 1 иначе если О[/[) Х то (/[1[: Е[ [-1) прим ТЕЛО ГРАФ НЕПОЛНЫЙ /(75) П, 1, Х, и/. В качестве эвристики для поиска кандидатов на соцветность (т 3.4) мы выберем более трудоемкую, но и самую эффективную процедуру нахождения пары вершин 1 и Х (1( Х), находящихся на расстоянии 2 и имеющих наибольшее количество разделяющих вершин. Организация алгоритма прямолинейна. Мы заведем величину д с начальным отрицательным значением, где будем поддерживать максимальное из найденного числа разделяющих вершин.
Затем переберем все вершины графа, проверяя, не является ли она звездой. Если она такой не является, начинаем выбирать нз не смежных с ней вершин, имеющих больший номер,. вершины, находящиеся на расстоянии 2. Если текущее число разделяющих вершин окажется больше д, оно вытесняет предыдущее, а номера вершин запоминаются в 1 и Х. Если после просмотра всех вершин д окажется отрицательным, то это означает полноту графа. Описанное правило рассчитано на связный граф, когда неполнота автоматически обеспечивает существование пары вершин на расстоянии 2 друг от друга. Описанный алгоритм обязательно выдаст требуемую пару вершин, если только она З С«. РАСКРАСКА ВЕРШИН ГРАФА «67 есть, безотносительно к тому, связен или не связен граф.
Однако если граф представляет собой собрание изолированных полных нодграфов, то тогда может не произойти никакого разумного присваивания значений величинам 1 и 1. Для этого частного случая нам надо ввести некоторое дополнительное правило склеивания какой-нибудь вершины 1 одного подграфа с какой-нибудь вершиной 1 другого нодграфа. Автор предлагает читателю в качестве упражнения установить, что, как бы ни происходило начальное сцепление двух поляых подграфов, описанный выше алгоритм склеивания будет давать всегда минимальную раскраску: подграф меньшего порядка, однажды зацепившись за подграф большего порядка, будет «вклеиваться» в последний до тех пор, пока болыпий подграф не поглотит меньший, ие увеличившись при этом в размерах.
В нашем случае мы поступим следующим образом: как только очередная вершина найдет себе несмежную, она подсчитает число рааделяющих вершин по некоторому общему правилу, дающему нуль, если вершины не на расстоянии 2. Если д все еще отрицательное, ее значение будет заменено на нуль, а 1 и 1 будут загружены номерами этих несмежных вершин. Любая «полноценная» пара вершин с ненулевым числом разделяющих вытеснит эту пару, если же этого не произойдет, то мы получим сцепку двух полных подграфов. Итак (83) ТЕЛО ГРАФ НЕПОЛНЬ1Й: ((цел З, »; «У: = — 1; для $: = 1 шаг 1 до и цикл ПЕРЕБОР ВЕРШИН); РЕЗУЛЬТАТ /87/) (84) ПЕРЕБОР ВЕРШИН/У, 1, 1, и, «У, [/: (целу; для у: = » + 1 глаг 1 до и цикл если У [Д у [ = О то ОБРАБОТКА НЕСМ ЕЖНОЙ) прим ОБРАБОТКА НЕСМЕЖНОЙ /У, 1, Х, и, с[, У, у/. Представление графа матрицей смежности в данном случае оказывается для нас очень удобным: число вершин, разделяющих Г-ю и у-ю, равно просто скалярному произведению 1-й и у-й строк матрицы У.
Если вершины находятся друг от друга дальше, чем на расстоянии 2, произведение будет равно нулю. Итак (85) ОБРАБОТКА НЕСМЕЖНОЙ: ((цел г; г: = О; (цел й; для У«: = 1 шаг 1 до и цикл»с = г + У[У, У«) х У[/, У«[)); ОТБОР МАКСИМУМА) (86) ОТБОР МАКСИМУМА /1, Х, З, У, у, г/: если г ) Ы то (ай = 3; (1:=у; 1:=у) (87) РЕЗУЛЬТАТ /(83) З/: ГРАФ НЕПОЛНЬТЙ: = «У «О Этот 87-й шаг завершает программирование задачи экономии памяти в операторной схеме.
ГЛАВА 5 ЗАКЛЮЧИТЕЛЬНЫЙ АНАЛИЗ в 5.1. Связь с теорией и практикой О прикладном исследовании. Еще Сократ заметил, что истинным свидетельством глубины знания является поннманиеегопределов. Вот и сейчас, завершив программирование поставленной аадачи, мы вернемся к ее общему анализу с позиций накопленного знания.
Автор наэвал эту книгу «Введение в теоретическоепрограммирование». В то же времявпредисловии им было сказано, чтоэадача экономии памяти будет рассматриваться как пример прикладного исследования. Давайте же попробуем разобраться,чтовпроведенном исследовании теоретического и что — прикладного. Конечно, в такой буквальной постановке вопрос эвучит несколько наивно.
Иэучение связи и рааличия между теоретическим и прикладным исследованием является одной нз наиболее глубоких методологических проблем современной науки вообще, а не только математики. Мало того, один и тот же компонент исследования в эависимости от рассматриваемого контекста будет, с одной стороны, казаться созданным по ходу дела как подспорье для достижения конкретной цели, а с другой, — может получить «постоянную прописку» в теоретическом фундаменте целого раздела науки. Например, информационный граф ($2.3) оказался для нас хотя и полеэным в нужный момент, но вспомогательным, проходным построением, которому не досталось место в результирующей ,программе. В то же время в теоретическом программировании— это одно из основных понятий, являющееся инварнантоммногих полезных манипуляций с программами, а также самостоятельной, явной конструкцией, используемой в важном классе схем программ.
Подчеркивая неправильность «абсолютного» противопоставления теоретических и прикладных аспектов, академик С. Л. Соболев неоднократно говорил, что «Нет чистой математики и прикладной математики, а есть математика и ее приложения». Мы, однако, сейчас не будем сильно вдаваться в диалектику единства противоположностей и выжимать из нашего исследования случайные наблюдения, не сравнимые по своей эначнмости с серьезными работами по методологии и истории математики.
В то же время, учитывая вводный характер книги в целом, мыне $5л. связь с ткогиея и ПРАктинон будем бояться наивных выражений и придадим некоторую определенность нашей трактовке теоретического и прикладного аспектов задачи зкономии памяти. Прикладное исследование характерно прежде всего своей целеустремленностью, направленностью на получение заранее заданного результата. Истоки задачи обычно носят внематематический характер или, более точно, внешний по отношению к применяемому методу решения. Процесс решения конкретной задачи протекает обычно в некоторой реальной обстановке, характеризующей возможности и ограничения в способах решения, которые такхзе приходится рассматривать как заданные.
Говоря о различии между теоретическим и прикладным исследованием, не следует также забывать, что последнее оказывается, как правило; более универсальным по своей природе. Связи прикладного исследования с «виешник мирома более богаты и многофакторны по сравнению с четко вьщеленными и, по возможности минимальными предпосылками теоретической работы. Теория, несмотря на исчерпывающую полноту своего логического анализа, как ни парадоксально это звучит, всегда в чем-то специализирована, а стало быть, ограничена. Она подчеркнуто отмежевывается от любого утверждения или условия, не включенного в систему исходных определений или посылок.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
