По вопросам приобретения обращаться
 Скачать 5.46 Mb.
|
|
4. Алгоритмы на графах 209 кратчайших расстояниях это поиск мини- мального значения по массиву. Количество ходов для короля из клетки (i, j) в z) рав- но Abs(j-z)). Рассмотрим случай, когда конь может «подвозить» короля. Пусть клетка (i,j) — место встречи фигур и sc — оценка количе- ства ходов коней до этой клетки. Необходи- мо найти коня и клетку доски, в которой он подхватит короля, причем вклад в общую оценку ходов при этом должен быть мини- мальным. 15. Задан ориентированный граф с N вер- шинами, пронумерованными целыми числа- ми от 1 до N. Написать программу, которая подсчитывает количество различных путей между всеми парами вершин графа. Входные данные. Входной файл содержит количе- ство вершин графа N и список дуг графа, заданных номерами начальной и конечной вершин. Выходные данные. Вывести в выходной файл матрицу N*N, элемент (i,j) которой равен числу различных пу- тей, ведущих из вершины i в вершину j или -1, если существует бесконечно много таких путей. Пример Указание. В алгоритмах на гра- фах есть очень изящный метод опре- деления кратчайших путей между всеми парами вершин — алгоритм Флойда. Используем его идею для решения нашей задачи. Пусть в мат- рице F[1..N,1..N] в текущий момент времени хранится количество путей длины г между всеми парами вер- шин, и нам необходимо найти количество путей длины r+1. Что делать? При между вершинами i и k есть какое-то ко- личество путей длины r и если при этом то между вершинами i и j есть пути длины r+1. Просчитывая для всех значений k, мы получаем количество путей между всеми парами вершин длины Второе соображение касается циклов в гра- фе, ибо они определяют значение бесконечности (число путей) задачи. Очевидно, что если выявлен цикл, то до всех вершин этого цикла существует бесконечно много путей. Выявленный 210 4. Алгоритмы на графах цикл — это ненулевой элемент на главной диагонали матрицы F при какой-либо из N итераций. Почему N? Да очень просто, N — это длина максимального цикла в графе. 16. Дано прямоугольное клетчатое поле M*N клеток. Каж- дая клетка поля покрашена в один из шести цветов, причем верхняя левая и нижняя правая имеют различный цвет. В ре- зультате поле разбивается на некоторое количество одноцвет- ных областей: две клетки одного цвета, имеющие общую сторо- ну, принадлежат одной области. Правила игры. За первым игроком закреплена область, включающая левую верхнюю клетку, за вторым — правую нижнюю. Игроки ходят по очереди. Делая ход, игрок перекра- шивает свою область по своему выбору: • в любой из шести цветов; • в любой из шести цветов, за исключением цвета своей об- ласти и цвета области противника. В результате хода к области игрока присоединяются все прилегающие к ней области выбранного цвета, если такие име- ются. Если после очередного хода окажется, что области игро- ков соприкасаются, то игра заканчивается. Написать программу, которая определяет минимально воз- можное число ходов, по прошествии которых игра может за- вершиться. Входные данные. Цвета пронумерованы цифра- ми от 1 до 6. Первая строка входного файла (in- put.txt) содержит М и N — размеры поля N=<50). Далее следует описание раскраски поля — М строк N цифр (от 1 до 6) в каждой без пробе- лов. Первая цифра файла соответствует цвету ле- вой верхней клетки игрового поля. Количество од- ноцветных областей не превосходит 50. Выходные данные. В выходной файл put.txt) необходимо вывести искомое количество ходов для каждого из пунктов. Указание. Сведем задачу к некоторой графовой модели. Рассмотрим идею решения на примере, при- веденном в формулировке задачи. Преобразуем ис- ходную матрицу (Г) в матрицу областей (Ob), опреде- лим цвет каждой области (массив С) и подсчитаем их количество Для примера будет выглядеть следующим образом. Массив С — (1, 2, 1, 1, 4, 3, 3, 2), k равно 8. А затем по этой матрице построим матрицу смежности графа (G), опре- деляющего связи между областями. 4. Алгоритмы на графах 211 После этих замечаний решение первого пункта задачи сводится к поиску кратчай- шего пути, точнее количества ребер в пути, между вершинами 1 и 8. Для этого можно использовать алгоритм Дейкстры или об- ход графа в ширину. Ответ задачи — значе- ние уровня вершины 8 (при обходе в шири- ну) минус единица. Чем отличается решение по второму пункту задачи? Нельзя окрашивать область в цвета своей области и области противни- ка. Это приводит к тому, что мы можем остаться в той же вер- шине графа областей. Опишем состояние игры корте- жем где х — номер области первого игрока, у — номер области второго игрока, play — номер игрока и color — номер цвета, в который игрок окрашивает область. Как выполнить такой просмотр состояний игры? Да опять же традиционным обходом в ширину в пространстве со- стояний. Завершением обхо- да будет или просмотр всей очереди, или достижение од- ного из конечных состоя- ний. Принцип обхода в ши- рину дает минимальное возможное ходов, по прошествии которых игра заверша- ется. 17. Корпоративная сеть состоит из N компьютеров, некото- рые из них соединены прямыми двусторонними каналами свя- зи. В целях повышения секретности при проектировании сети количество каналов связи было сокращено до минимума с тем условием, чтобы любые два компьютера имели возможность об- мена информацией либо непосредственно, либо через другие компьютеры сети. Хакер хочет прослушивать все передаваемые в сети сообще- ния. Для этого он разработал вирус, который, будучи установ- ленным на какой-либо из компьютеров, передает ему всю ин- формацию, проходящую через этот компьютер. Оказалось, что материальные затраты, необходимые для установки вируса на конкретный компьютер, различны. Требуется определить на- бор компьютеров, которые хакер должен заразить вирусом, чтобы минимизировать общие материальные затраты. 212 4. Алгоритмы на графах Входные данные. Первая строка входного фай- ла содержит N — количество компьюте- ров в сети (l= строк содержатся номера компьютеров, с которы- ми непосредственно связан компьютер с номером i. Далее следует N целых чисел из диапазона [1,1000] — материальные затраты, связанные с установкой вируса на каждый из компьютеров. Выходные данные. В выходной файл put.txt) требуется вывести минимально возмож- ные суммарные затраты и список номеров компь- ютеров, которые необходимо инфицировать, упорядоченный по возрастанию. Указание. В условии задачи в «сверхзавуалированной» фор- ме сказано о том, что связи компьютеров описываются некото- рой древовидной структурой, ибо в противном случае «сокра- щение до минимума» каналов связи невозможно. Итак, мы имеем какое-то дерево (связное), описывающее связи между компьютерами. Это ограничение дает возможность решать за- дачу и для 500 компьютеров. При связях компьютеров, описы- ваемых произвольным связным графом, вероятно, ничего дру- гого, кроме перебора с некоторыми эвристиками, не остается делать. А это уже достаточно безнадежно. Идея решения. Рас- сматриваем вершины дерева по принципу обхода в ширину. Мы находимся в вершине с номером и нам требуется оценить (с учетом требования задачи — все связи между компьютерами должны быть под контролем): • — стоимость заражения компьютеров из поддерева, при условии, что и компьютер с номером k заражается; • — то же самое, только компьютер с номером k не за- ражается. Так как используется обход в ширину, то оценки В W для всех компьютеров с номерами k 1 ..., уже получены. В первом слу- чае — при оценке B[k] — компью- теры мы можем как заражать, так и не заражать, т. е. необходимо найти Во втором случае — не заражаем компьютер k — компьютеры ..., необходимо заражать, в противном будет нарушено 4. Алгоритмы на графах 213 условие задачи, т. е. Ответом на первый задачи будет значение min(B[j],W[j]), где j — номер вершины, с которой начинается обход в ширину. 18. Дан ориентированный граф. Вершинам приписаны веса. Требуется найти путь между начальной и конечной вершинами (они заданы) с максимально возможным суммарным весом. Путь должен удовлетворять следующим условиям: • по каждой дуге разрешается пройти один раз; • если в вершину попадаем по входящей дуге, то к суммар- ному весу вес этой вершины прибавляется; • если в вершину попадаем по выходящей дуге, то из суммарного веса вес этой вер- шины вычитается. Входные данные. Входной файл (input.txt) содержит данные в следующей последователь- ности: • N — количество вершин графа и их веса (1=<N=<30, • b, е — номера начальной и конечной вер- шин; • М — количество дуг; • — номера вершин, соединяемых пер- вой дугой; • i 2 j 2 номера вершин, соединяемых вто- рой дугой; • ... • — номера вершин, соеди- няемых дугой с номером Выходные данные. В выходной файл (output.txt) требуется вывести максимальный вес пути и путь, на котором он достигается. В случае, если решение не существует, выход- ной файл должен содержать единст- венную строку solution». Указание. Задача на поиск эйле- рова пути в графе между заданными вершинами. Так как требуется най- ти не просто путь, а путь с наилуч- шей оценкой, то перебор вариан- тов, — это, наверное, единственный способ решения задачи. Эйлеров путь между вершинами b и е существует (теорема Эйлера) в связном графе в том и только 2 5 2 2 3 0 3 5 0 2 0 1 0 0 0 0 4 0 0 о 0 0 0 0 о 214 4. Алгоритмы на графах том случае, если вершины Ъ и е имеют нечетные степени, а все остальные — четные степени. Следовательно, на стадии предва- рительной обработки требуется выяснить существует ли в принципе путь между заданными вершинами. Для сокращения перебора разумно ввести дополнительную структуру данных, в которой для каждой вершины определена последовательность просмотра остальных вершин графа. Для нашего примера она может иметь следующий вид. Так, из вершины 2 очередность просмотра вершин — 5, 1, 4. Вероятность того, что при этом на первых шагах перебора получается оценка, близкая к опти- мальной, возрастает, если не рассматривать специально подо- бранные тесты. Кроме того, следует ввести оперативную про- верку связности непросмотренной части графа. Пусть мы идем по ветке перебора 1-4-6, как показано на рисунке. В процессе поиска решения — эйлерова пути — пройденные ребра «выбра- сываются». Перечеркнутые ребра удалены, они пройдены, и мы находимся в 6-й вершине. Может оказаться, во-первых, что появятся изолированные вершины и, во-вторых, что на- рушится связность оставшейся части графа. Например, так, как это показано на рисунке. Необходимо попасть из 1-й вер- шины в 7-ю. Очевидно, что вер- шины 2, 3, 4 уже никак не попадут в путь, поэтому дальней- ший поиск пути в этом варианте решения не имеет смысла. Поиск эвристик, сокращающих перебор, можно продолжить. 19. «Стены»* . В некоторой стране стены построены таким образом, что каждая стена со- единяет ровно два города, и стены не пересекают друг дру- га. Таким образом, страна раз- делена на отдельные области. Чтобы добраться из одной об- ласти в другую, необходимо либо пройти через город, либо пересечь стену. Два любых го- рода А и могут соединяться не более чем одной стеной Задача с Международной олимпиады школьников по информатике 2000 года. 4. Алгоритмы на графах 215 (один конец стены в городе А, а другой — в городе В). Более того, всегда существует путь из города А в город В, проходящий каких-либо стен и через города. Существует клуб, члены кото- рого живут в городах. В каждом городе может жить либо один член клуба, либо вообще ни одно- го. Иногда у членов клуба возникает желание встретиться внутри одной из областей, но не в городе. Чтобы попасть в нуж- ную область, каждый член клуба должен пересечь какое-то ко- личество стен, возможно равное нулю. Члены клуба путешест- вуют на велосипедах. Они не хотят въезжать ни в один город из-за интенсивного движения на городских улицах. Они также хотят пересечь минимально возможное количество стен, так как пересекать стену с велосипедом довольно трудно. Исходя из этого, нужно найти такую оптимальную область, чтобы сум- марное количество стен, которые требуется пересечь членам клуба, называемое суммой пересечений, было минимальным из всех возможных. Города пронумерованы целыми числами от 1 до N , где N — количество городов. На первом рисунке (с. 214) пронумерован- ные вершины обозначают города, а линии, соединяющие вер- шины, обозначают стены. Предположим, что членами клуба являются три человека, которые живут в городах с номерами 3, 6 и 9. Тогда оптимальная область и соответствующие марш- руты движения членов клуба показаны на втором рисунке выше. Сумма пересечений равняется 2, так как членам клуба следует пересечь две стены: человеку из города 9 требуется пе- ресечь стену между городами 2 и 4, человеку из города 6 требу- ется пересечь стену между городами 4 и 7, а человек из города 3 не пересекает стен вообще. Требуется написать программу, которая по заданной информа- ции о городах, областях и местах проживания членов клуба нахо- дит оптимальную область и минимальную сумму пересечений. Входные данные. Файл имеет имя walls.in. Первая строка содержит одно целое число: количество областей М, Вторая строка содержит одно целое число: количество городов N, 3 L L различных целых чисел в возрастающем порядке: номера го- родов, где живут члены клуба. 216 4. Алгоритмы на графах Оставшаяся часть файла содержит 2М строк, по паре строк для каждой из М областей. Пер- вые две строки из них описывают первую об- ласть, вторые две строки — вторую область, и т. д. В каждой паре первая строка содержит ко- личество городов на границе области; вторая строка содержит номера этих I городов в поряд- ке обхода границы области по часовой стрелке. Единственным исключением является послед- няя область — это находящаяся снаружи (внеш- няя) область, окружающая все города и другие области, и для нее порядок следования городов на границе задается против часовой стрелки. По- рядок описания областей во входном файле зада- ет целые номера этим областям. Область, опи- санная первой во входном файле, имеет номер 1, описанная второй — номер 2, и т. д. Обратите внимание, что входной файл содержит описание всех областей, образованных городами и стена- ми, включая находящуюся снаружи (внешнюю) область. Выходные данные. Файл имеет имя Первая строка этого файла содержит одно целое число: минимальную сумму пересечений. Вторая строка содержит одно целое число: номер оптима- льной области. Если существует несколько раз- личных решений, вам необходимо выдать лишь Указание. В формулиров- ке задачи содержится под- сказка решения. Описание исходного графа, а это явная задача на графовые алгорит- мы, дано (например) не в виде матрицы смежности, а заданием областей. Требует- ся построить граф, вершина- ми которого являются облас- ти, а ребрами — стены между областями. Естественно, что должна быть вершина и для внешней области. Выше изображен граф областей для дан- ных, представленных на рисунках в условии задачи. После формирования графа областей находим кратчайшие расстоя- 4. Алгоритмы на графах 217 ния между всеми парами вершин (алгоритм Флойда). Для каж- дого члена клуба и каждой области определяем минимальное расстояние, за которое он добирается до этой области. Осталось просуммировать эти расстояния по всем членам клуба и вы- брать минимум. 20. Два графа и называются изоморф- ными, если существует взаимно однозначное соответствие такое, что сохраняется отношение смежности между вершинами графа, т. е. тогда и только тогда, когда Даны два графа. Определить, изоморфны ли они. На рисунке приведены примеры изоморфных графов. Рекомендации. Прямой метод решения, заключающийся в генерации всех возможных перестановок N!, где N — мощ- ность множеств и и проверке сохранения отношения смежности для каждого случая работоспособен для небольших значений N Несколько сократить перебор позволяет введение массивов для хранения степеней вершин (число ребер, инцидентных вершине) и установка соответствия только между вершинами, имеющими одну степень. Для графов, приведен- ных на рисунке и имеющих одно значение степени, это сокра- щение не работает. 21. Максимально полный подграф графа G называется кли- кой. В клике между каждой парой вершин существует ребро. Число клик в графе может рас- ти экспоненциально относите- льно числа вершин. Так, в гра- фах с 3*N вершинами вершины разбиты на триады (1, 2, 3), (4, 5, 6), ... (3*N-2, 3*N-1, 3*N). Ребер между вершинами любой триа- ды нет. Однако вершины триа- ды связаны ребрами со всеми вершинами, не принадлежащи- ми данной триаде. На предыду- 218 4. Алгоритмы на графах щем рисунке приведен граф Муна-Мозера при N=2, на этом рисунке при iV=3. Графы Муна — Мозера имеют клик, каждая из которых содержит N вершин. Перечислить для небольших значений N клики в графах Муна-Мозера. Примечание В общем случае задача о поиске клик в графе G решается достаточ- но сложно. Однако понятие клики противоположно понятию мак- симально независимого множества. Строим дополнение графа G'. Находим в G' максимально независимые множества (это мы умеем делать) — они соответствуют кликам исходного графа. 22. Рассмотрим четыре множества 3], 2, 4], 4], 3, 4]. Требуется выбрать такие различные че- тыре числа что i = l , 2, 3, 4. Этими числами могут быть они представляют данную систему множеств. Несложно привести пример множеств, для которых данное представление невозможно. Ф. Холлом дока- зана теорема о существовании системы различных представи- телей. Система ..., имеет систему различных представителей тогда и только тогда, когда для любой подсис- темы выполняется неравенство т.е. количество элементов в объединении любых к подмножеств должно быть не менее к. Пусть [1, 2, ..., N]. Определить, имеет ли систему различных представителей. Указание. По M(S) требуется построить двудольный граф. Система различных представителей существует тогда и только тогда, когда в двудольном графе есть максимальное паросочета- ние из iV ребер. 23. Дан массив N*M, в клетках которого произвольным об- разом поставлены числа от 1 до N*M. Горизонтальным ходом называется такая перестановка любого числа элементов масси- ва, при которой каждый элемент остается в той строке, в кото- рой он был. Вертикальным ходом называется такая перестанов- ка любого числа элементов массива, при которой каждый элемент остается в том столбце, в котором он был. Разрешают- ся только горизонтальные и вертикальные ходы*. По мнению автора, это — одна из лучших олимпиадных задач Сергея Генна- дьевича Волченкова. |