Упражнения с решениями - Урок 3 - Графы

Упражнение с решением 1

Возьмем направленный ациклический граф G на рис. 3.9. Сколько топологических упорядочений он имеет?

Рис. 3.9. Сколько топологических упорядочений существует у этого графа?

Решение

Вспомните, что топологическим упорядочением G называется такое упорядочение узлов v₁, v₂, ..., v_n, при котором все ребра указывают “вперед”: для каждого ребра (v_i, v_j) выполняется условие i < j.

Конечно, чтобы ответить на вопрос, можно перебрать все 5 ∙ 4 ∙ 3 ∙ 2 ∙ 1 = 120 возможных упорядочений и проверить, является ли каждое из них топологическим упорядочением. Впрочем, такой перебор займет много времени.

Лучше действовать иначе. Как было показано в тексте (и как следует непосредственно из определения), первым узлом топологического упорядочения должен быть узел, не имеющих входящих ребер. Аналогичным образом последним узлом должен быть узел, не имеющий выходящих ребер. Следовательно, в каждом топологическом упорядочении G узел а должен стоять на первом месте, а узел e — на последнем.

Теперь нужно понять, как должны располагаться узлы b, c и d в середине упорядочения. Ребро (c, d) требует, чтобы узел c предшествовал d, однако b может находиться в любой позиции относительно этих двух узлов: до обоих, между с и d, или после обоих. Других вариантов нет, и мы можем заключить, что существуют три возможных топологических упорядочения:

a, b, c, d, e

a, c, b, d, e

a, c, d, b, e

Упражнение с решением 2

Ваши друзья работают над методами координации групп мобильных роботов. Каждый робот оснащен радиопередатчиком, который используется для связи с базовой станцией. Выяснилось, что если роботы оказываются слишком близко друг к другу, между передатчиками возникают помехи. Встает естественная задача: как спланировать такое перемещение роботов, чтобы каждый робот оказался у предполагаемой цели, но роботы не сближались на опасное расстояние?

Задачу можно абстрактно смоделировать следующим образом. Допустим, имеется ненаправленный граф G = (V, E), предоставляющий план здания; два робота изначально расположены в узлах а и b графа. Робот в узле а должен переместиться к узлу c по пути в графе G, а робот в узле b должен переместиться к узлу d. Для этого используется механизм планирования: на каждом временном отрезке один из роботов перемещается по одному ребру, от ребра к соседнему узлу; в конце периода планирования робот из узла а должен находиться в узле c, а робот из узла b — в узле d.

Планирование свободно от помех, если не существует точки, в которой два робота занимают узлы на расстоянии ≤ r друг от друга в графе (для заданного параметра r). Предполагается, что два начальных узла а и b находятся на расстоянии, большем r (как и два конечных узла c и d).

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

Решение

Рассматриваемая задача относится к более общей категории: имеется набор возможных конфигураций для роботов (под конфигурацией понимается выбор местонахождения каждого робота). Мы пытаемся перейти из заданной начальной конфигурации (a, b) в конечную конфигурацию (c, d), принимая во внимание ограничения на возможность перемещения между конфигурациями (робот может перейти только в соседний узел) и на то, какие конфигурации считаются “допустимыми”.

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

Определим следующий граф H (большего размера). Множество узлов H соответствует множеству всех возможных конфигураций роботов; иначе говоря, H состоит из всех возможных пар узлов в G. Два узла H соединяются ребром, если они представляют конфигурации, которые могут занимать последовательные позиции в процессе планирования; иначе говоря, (u, v) и (u', v') соединяются ребром в H, если одна из пар u, u' или v, v' состоит из одинаковых значений, а другая пара соответствует ребру в G.

Мы уже видим, что пути из (a, b) в (c, d) в H соответствуют правилам планирования для роботов: такой путь состоит из последовательности конфигурации, в которой на каждом шаге один робот пересекает ровно одно ребро в G. Тем не менее в расширенной формулировке еще не отражено правило, согласно которому планирование должно быть свободно от помех.

Для этого из H просто удаляются все узлы, соответствующие конфигурациям с помехами. Таким образом определяется H' — граф, полученный удалением всех узлов (u, v), для которых расстояние между u и v в G не превышает r.

В этом случае полный алгоритм выглядит так. Мы строим граф H', а затем выполняем алгоритм из текста для проверки существования пути из (a, b) в (c, d). Правильность работы алгоритма следует из того факта, что пути в H' соответствуют процессам планирования, а узлы H' точно соответствуют конфигурациям без помех.

Остается оценить время выполнения. Пусть n — количество узлов в G, а m — количество ребер в G. Чтобы проанализировать время выполнения, мы сформулируем оценки для: (1) размера графа H' (который в общем случае больше G), (2) времени построения H' и (3) времени поиска пути от (a, b) к (c, d) в H.

1. Начнем с размера H'. Граф H' содержит не более n² узлов, так как его узлы соответствуют парам узлов в G. Сколько же ребер содержит H'? С узлом (u, v) связаны ребра (u', v) для каждого соседа u' узла и в G и ребра (u, v') для каждого соседа v' узла v в G. Чтобы сформулировать простую верхнюю границу, заметим, что имеется не более n вариантов для (u', v) и не более nвариантов для (u, v'), поэтому каждый узел H' имеет максимум 2n инцидентных ребер. Суммируя по (максимум) n² узлам H', получаем O(n³) ребер. (Вообще говоря, для количества ребер H' можно дать улучшенную границу O(mn) на основании границы (3.9), доказанной в разделе 3.3, для суммы степеней графа. Мы вернемся к этой теме позднее.)

2. Перейдем ко времени, необходимому для построения H'. Чтобы построить H, мы переберем все пары узлов в G за время O(n²) и построим ребра по приведенному выше определению за время O(n) на каждый узел, за общее время O(n³). Теперь нужно определить, какие узлы следует удалить из H для получения H'. Это можно сделать так: для каждого узла u в G запускается поиск в ширину от u, который находит все узлы v, находящиеся на расстоянии не более г от u. Все такие пары (u, v) удаляются из H. Каждый поиск в ширину в G выполняется за время O(m + n), и мы проводим по одному такому поиску от каждого узла, поэтому общее время для этой части составит O(mn + n²).

3. Итак, граф H' построен, и теперь достаточно определить, существует ли путь из (a, b) в (с, d). Для этого можно воспользоваться алгоритмом связности (см. выше) за время, линейное по отношению к количеству ребер и узлов H'. Так как H' состоит из O(n²) узлов и O(n³) ребер, последний шаг также выполняется за полиномиальное время.

Упражнения

1. Рассмотрим направленный ациклический граф G на рис. 3.10. Сколько топологических упорядочений он имеет?

Рис. 3.10. Сколько топологических упорядочений существует у этого графа?

2. Предложите алгоритм для проверки наличия циклов в заданном ненаправленном графе. Если граф содержит цикл, то ваш алгоритм должен вывести его. (Выводить все циклы в графе не нужно, достаточно одного.) Алгоритм должен выполняться за время O(m + n) для графа с n узлами и m ребрами.

3. Алгоритм, описанный в разделе 3.6 для вычисления топологического упорядочения DAG, многократно находит узел, не имеющий входящих ребер, и удаляет его. В конечном итоге это приводит к получению топологического упорядочения (при условии, что входной граф действительно является DAG).

Но допустим, что вы получили произвольный граф, который может быть или не быть DAG. Расширьте алгоритм топологического упорядочения так, чтобы для входного направленного графа Gон выводил одно из двух: (a) топологическое упорядочение, доказывающее, что входной граф является DAG; или (b) цикл в G, доказывающий, что входной граф не является DAG. Алгоритм должен выполняться за время O(m + n) для направленного графа с n узлами и m ребрами.

4. Вдохновившись примером великого Владимира Набокова, ваши друзья занялись лепидоптерологией (проще говоря, изучением бабочек). Часто при возвращении из поездки с новыми образцами им бывает очень трудно определить, сколько же разных видов было поймано, ведь многие виды очень похожи друг на друга.

Однажды они возвращаются с n бабочками, каждая из которых принадлежит одному из двух видов, — назовем их A и B. Вашим друзьям хотелось бы разделить n образцов на две группы (относящиеся к видам A и B), но напрямую классифицировать каждый отдельно взятый образец очень трудно. Вместо этого они решают действовать немного иначе.

Каждая пара образцов i и j располагается рядом и тщательно изучается. Если исследователи достаточно уверены в своей оценке, они помечают образцы из пары (i, j) либо как “одинаковые” (то есть как относящиеся к одному виду), либо как “разные” (то есть как относящиеся к разным видам). Также они могут отказаться от назначения оценки конкретной паре; в таком случае пара называется неопределенной.

Итак, имеется набор из n образцов, а также набор из m оценок (“одинаковые” или “разные”) для пар, которые не были отнесены к неопределенным. Вашим друзьям хотелось бы знать, соответствуют ли эти данные представлению о том, что каждая бабочка относится к одному из видов A или B. Говоря конкретнее, набор из m оценок объявляется непротиворечивым, если возможно пометить каждый образец A или B так, чтобы для каждой пары (i, j) с пометкой “одинаковые” i и j относились к одному виду, а для каждой пары (i, j) с пометкой “разные” i и jотносились к разным видам. Ваши друзья возятся с проверкой непротиворечивости оценок, как вдруг один из них осознает: ведь вы сможете придумать алгоритм, который позволит с ходу получить ответ на этот вопрос. Предложите алгоритм для проверки непротиворечивости оценок с временем выполнения O(m + n).

5. Бинарным деревом называется корневое дерево, в котором каждый узел имеет не более двух дочерних узлов. Покажите посредством индукции, что в любом бинарном дереве количество узлов с двумя дочерними узлами ровно на 1 меньше количества листьев.

6. Имеется связный граф G = (V, E) и конкретная вершина u ∈ V. Предположим, при вычислении дерева поиска в глубину с корнем u было получено дерево T, включающее все узлы G. После этого при вычислении дерева поиска в ширину с корнем u было получено то же дерево T. Докажите, что G = T. (Иначе говоря, если T одновременно является деревом поиска в глубину и в ширину с корнем в u, то G не может содержать ребер, не принадлежащих T.)

7. Ваши друзья, занимающиеся технологиями беспроводных сетей, в настоящее время изучают свойства сети из n мобильных устройств. Перемещаемые устройства (или вернее, их хозяева) в любой момент времени определяют граф по следующим правилам: существует узел, представляющий каждое из n устройств, и между i и j существует ребро, если физические позиции i и jнаходятся на расстоянии не более 500 метров. (В таком случае устройства находятся “в пределах дальности” друг друга.)

Чтобы сеть устройств по возможности оставалась связной, перемещение устройств ограничивается по следующему правилу: в любое время каждое устройство i должно находиться на расстоянии не более 500 метров от по крайней мере n/2 других устройств (где n — четное число). Требуется узнать: гарантирует ли это свойство само по себе, что сеть будет оставаться связной? Ниже приведена конкретная формулировка этого вопроса как утверждения применительно к графам.

Утверждение: пусть G — граф из n узлов, где n — четное число. Если каждый узел G имеет степень не менее n/2, то граф G является связным.

Считаете вы это утверждение истинным или ложным? Приведите доказательство истинности или ложности.

8. Во многих публикациях, посвященных структуре Интернета и Всемирной паутины, в том или ином виде обсуждался следующий вопрос: на каком расстоянии находятся типичные узлы этих сетей? Если внимательно читать такие статьи, выясняется, что многие из них путают понятия диаметра сети и среднего расстояния в сети; авторы используют эти понятия так, словно они являются взаимозаменяемыми.

В соответствии с нашей терминологией расстоянием между двумя узлами u и v в графе G = (V, E) называется минимальное количество ребер в пути, связывающем эти узлы; расстояние будет обозначаться dist(u, v). Диаметром G называется максимальное расстояние между любой парой узлов G; эта характеристика будет обозначаться diam(G).

Определим сопутствующую характеристику, которая будет называться средним попарным расстоянием в G, обозначим ее apd(G). Величина apd(G) вычисляется как среднее арифметическое по всем множествам из двух разных узлов u и v для расстояния между u и v.

Другими словами,

Простой пример наглядно показывает, что существуют графы G, для которых diam(G) ≠ apd(G). Пусть G — граф с тремя узлами u, v, w и двумя ребрами {u, v} и {v, w}. Тогда

при том, что

Конечно, эти два числа не так уж сильно отличаются в случае графа из трех узлов; будет естественно задаться вопросом, всегда ли между ними существуют тесные отношения. Следующее утверждение пытается формализовать этот вопрос.

Утверждение: существует положительное натуральное число с, при котором для любого связного графа G выполняется условие

Считаете вы это утверждение истинным или ложным? Приведите доказательство истинности или ложности.

9. Интуитивно понятно, что качество связи между двумя узлами коммуникационной сети, находящимися на большом расстоянии (с множеством переходов), хуже, чем у двух узлов, расположенных вблизи друг от друга. Существует ряд алгоритмических результатов, в определенной степени зависящих от разных способов формального отражения этих представлений. В следующем варианте учитывается устойчивость путей к удалению узлов.

Допустим, ненаправленный граф G = (V, E) из n узлов содержат два узла s и t, расстояние между которыми строго больше n/2. Покажите, что должен существовать некоторый узел v, отличный от 5 и t, такой, что удаление v из G приведет к уничтожению всех путей s-t. (Другими словами, граф, полученный из G посредством удаления v, не содержит путей от s к t.) Предложите алгоритм поиска такого узла v с временем выполнения O(m + n).

10. Во многих музеях можно увидеть работы художника Марка Ломбарди (19512000), которые представляют собой художественно воспроизведенные графы. На этих графах изображены полученные в результате серьезных исследований отношения между людьми, замешанными в крупных политических скандалах за последние десятилетия: узлы представляют участников, а ребра — некие отношения в парах. Если внимательно присмотреться к этим рисункам, можно проследить довольно зловещие пути от высокопоставленных государственных служащих США через бывших деловых партнеров и швейцарские банки к подпольным торговцам оружием.

Такие изображения служат ярким примером социальных сетей, в которых, как упоминалось в разделе 3.1, узлы представляют людей и организации, а ребра — различного рода отношения. Короткие пути, в изобилии встречающиеся в таких сетях, в последнее время привлекают общественное внимание: люди размышляют над их смыслом. В случае с графами Марка Ломбарди такие пути наводят на мысли о короткой последовательности шагов, приводящих от хорошей репутации к позору.

Конечно, один короткий путь между узлами v и w в такой сети может объясняться простой случайностью; большое количество коротких путей между v и w выглядит куда убедительнее. По этой причине наряду с задачей вычисления одного кратчайшего пути v-w в графе G исследователи социальных сетей занимались рассмотрением задачи определения количества кратчайших путей v-w. Как выяснилось, у этой задачи есть эффективное решение. Допустим, имеется ненаправленный граф G = (V, E), в котором выделены два узла v и w. Приведите алгоритм, который вычисляет количество кратчайших путей v-w. (Алгоритм не должен выводить все пути; достаточно указать их количества.) Алгоритм должен выполняться за время O(m + n) для графа с nузлами и m ребрами.

11. Вы помогаете специалистам по безопасности отслеживать распространение компьютерного вируса. Система состоит из n компьютеров С₁, C₂, ..., C_n; на входе вы получаете набор данных трассировки с указанием времени взаимодействий между парами компьютеров. Таким образом, данные представляют собой последовательность упорядоченных триплетов вида (C_i, C_j, t_k), сообщающих, что между компьютерами C_i и C_j передавались данные во время t_k. Общее количество триплетов равно m.

Предполагается, что триплеты передаются отсортированными по времени. Для простоты будем считать, что каждая пара компьютеров обменивается данными не более одного раза за интервал наблюдения. Специалисты по безопасности хотели бы иметь возможность получать ответы на вопросы следующего типа: если вирус был внедрен на компьютер C_a во время х, мог ли он достичь компьютера C_b ко времени у? Механика распространения вируса проста: если зараженный компьютер C_i взаимодействует с незараженным компьютером C_j во время t_k (другими словами, если в данных трассировки присутствует один из триплетов (C_i, C_j, t_k) или (C_j, C_i, t_k)), то компьютер C_j тоже становится зараженным начиная с времени t_k.

Таким образом, вирус передается с машины на машину через серию взаимодействий; предполагается, что ни один шаг в этой последовательности не подразумевает перемещения назад во времени. Например, если компьютер C_i заражен к моменту t_k, и данные трассировки содержат триплеты (C_i, C_j, t_k) и (C_j, C_q, t_r), где t_k ≤ t_r, то компьютер C_q будет заражен через C_j. (Обратите внимание: время t_k может быть равно t_r; это означало бы, что у C_j были одновременно открыты подключения к C_i и C_q, так что вирус мог переместиться с C_i на C_q.)

Допустим, для n = 4 данные трассировки состоят из триплетов

и вирус был внедрен на компьютер C₁ во время 2. В этом случае компьютер C₃ будет заражен ко времени 8 серией из трех шагов: сначала C₂ заражается во время 4, затем C₄ получает вирус от C₂ ко времени 8 и, наконец, C₃ получает вирус от C₄ ко времени 8. С другой стороны, если бы данные трассировки имели вид

и вирус снова был бы внедрен на компьютер C₁ во время 2, то компьютер C₃ не был бы заражен за наблюдаемый период: хотя C₂ заражается к времени 14, мы видим, что C₃ взаимодействует с C₂ до заражения C₂. Никакая последовательность взаимодействий с прямым перемещением во времени не приведет к распространению вируса с C₁ на C₃ во втором примере.

Разработайте алгоритм, который позволит получить ответы на вопрос типа: для заданного набора данных трассировки необходимо определить, сможет ли вирус, внедренный на компьютере C_aво время х, заразить компьютер C_b ко времени у. Алгоритм должен выполняться за время O(m + n).

12. Вы помогаете группе ученых-этнографов в анализе устных исторических данных о людях, живших в некоторой деревне за последние двести лет. В этих материалах ученые узнали о множестве из n людей (все эти люди уже умерли), которых мы будем обозначать P₁, P₂, ..., P_n. Также были собраны сведения о времени жизни этих людей друг относительно друга. Каждый факт представлен в одной из двух форм:

• для некоторых i и j человек P_i умер до рождения человека P_j; или

• для некоторых i и j сроки жизни P_i и P_j перекрывались по крайней мере частично.

Естественно, ученые не уверены в правильности всех этих фактов; память порой подводит, а многие сведения передавались из уст в уста. Они хотят, чтобы вы проверили хотя бы внутреннюю непротиворечивость собранных данных, то есть может ли существовать множество людей, для которых одновременно истинны все собранные факты.

Предложите эффективный алгоритм для решения этой задачи: алгоритм должен либо выдавать предполагаемые даты рождения и смерти каждого из n людей, чтобы все факты были истинны, либо сообщать (правильно), что такие даты существовать не могут, то есть что набор фактов, собранных этнографами, внутренне противоречив.

Примечания и дополнительная литература

Теория графов — большая тема, включающая как алгоритмические, так и неалгоритмические темы. Обычно считается, что теория графов началась с работы Эйлера (Euler, 1736), развивалась на основе интереса к представлению карт и химических компонентов в виде графов в XIX веке и стала областью систематических научных исследований в XX веке — сначала как ветвь математики, а позднее на основе практического применения в информатике. В книгах Берга (Berge, 1976), Боллобаса (Bollobas, 1998) и Дистела (Diestel, 2000) основательно рассматриваются многие вопросы теории графов. В последнее время появились обширные данные для изучения больших сетей, встречающихся в физике, биологии и социологии, а также возрос интерес к свойствам сетей, задействованных во всех этих областях. В книгах Барабаси (Barabasi, 2002) и Уоттса (Watts, 2002) эта перспективная область исследований обсуждается с примерами, ориентированным на общую аудиторию.

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

Примечания к упражнениям

Упражнение 12 основано на результатах Мартина Голумбика и Рона Шамира.