Главная » Java, Структуры данных и алгоритмы » Абстрактный тип данных «граф»

0

С точки зрения абстрактного представления граф G — это просто набор Vузлов (vertex) и коллекция (набор) пар узлов Е из К, называемых путями (edge). Таким образом, граф — это способ представления связей и отношений между парами объектов из некоторого множества V. К сожалению, в разных книгах для описания графов используется разная терминология. Так, например, на узлы (или вершины)-vertices ссылаются как на узлы-nodes, а на пути (или ребра)-edges — как на дуги-ягсу.

Пути в графах могут быть направленными или ненаправленными. Путь (u,v) будет направленным от и к v, если пара (u,v) упорядочена так, что и предшествует v. Путь (u,v) будет ненаправленным от и к v, если пара (u,v) не упорядочена. Ненаправленный путь иногда может обозначаться с помощью {u,v}, но для простоты используем простое написание (u,v) с тем условием, что (w;v) будет означать то же, что и (v,u). Визуально графы обычно представлены узлами в виде овалов или прямоугольников и путями в виде изогнутых линий, связывающих овалы или прямоугольники.

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

Рис. 12.1. Граф взаимодействия соавторов

Пример 12.2. Граф можно сопоставить с объектно-ориентированной программой, где узлы представляют классы, а пути между узлами означают наследование классов. Если класс, ассоциируемый с v, расширяет класс, ассоциируемый с и, то от узла v будет проведен путь в узел и. Этот путь будет уже направленным, поскольку наследование может осуществляться только в одну сторону (то есть является асимметричным).

Если все пути графа ненаправленные, говорят о ненаправленном графе. И наоборот, если все пути являются направленными, граф считается направленным, или диграфом (digraph). Заметим, что любой ненаправленный граф или граф смешанного типа можно конвертировать в направленный граф, заменив каждый ненаправленный путь (u,v) парой направленных путей (u,v) и (v,u).

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

Пример 12.4. Физическими примерами графов могут быть системы электропроводки или водоснабжения в здании. Такие коммуникации могут моделироваться в виде графов, в которых каждое соединение, выключатель или розетка рассматриваются как узел, а каждый провод или труба — как путь. Эти графы в свою очередь являются компонентами других, более сложных графов, а именно местных систем электро- и водоснабжения. В зависимости от специфических аспектов данных графов можно рассматривать их пути как направленные или ненаправленные, так как вода в принципе, как и электрический поток, может двигаться как в том, так и в другом направлении.

Два узла, соединяемые одним путем, называются конечными узлами, или конечными точками пути. Если путь является направленным, то его первая точка будет местом происхождения (источником), а другая — местом назначения (целью) пути. Два узла называются смежными (объединенными), если они являются конечными точками некоторого пути. Путь называется инцидентным (попутным) путем узла, если этот узел является одним из конечных этого пути. Исходящими путями узла называются направленные пути, местом происхождения которых является данный узел. Соответственно входящими путями узла будут называться пути, пунктом назначения которых он является. Степенью узла v, обозначаемой с помощью deg(v), является количество инцидентных путей данного узла. Полустепенью захода и полустепенью исхода узла v является количество входящих и исходящих путей данного узла, обозначаемые как indeg(v) и outdeg(v) соответственно.

Пример 12.5. С помощью графа G под названием схема полетов можно изучить сеть авиамаршрутов. Узлы будут ассоциироваться с аэропортами, а пути — с рейсами (см. рис. 12.2). В графе G пути являются направленными, поскольку каждый рейс имеет четко определенное направление (из аэропорта отправления в аэропорт назначения). Конечные точки пути е в графе соответствуют месту вылета и месту прибытия рейса, ассоциируемого с этим путем. Два аэропорта являются смежными, если их соединяет маршрут, по которому осуществляются перелеты. Путь е будет инцидентным для узла v графа С, если рейс, соответствующий е, прилетает или вылетает из аэропорта, ассоциируемого с v. Исходящие пути узла v соответствуют рейсам, вылетающим из аэропорта v, а входящие пути — рейсам, прилетающим в него. И наконец, полустепень захода узла v графа G будет соответствовать количеству прибывающих, а полустепень исхода — количеству убывающих из аэропорта v рейсов.

Рис. 12.2. Пример направленного графа, представляющего сеть авиамаршрутов.

Конечными точками пути UA 120 являются LAX и ORD; следовательно, LAX и ORD являются смежными. Полустепенью захода DFW является 3, а исхода — 2

Эти определения графа предназначаются для путей, организованных в виде коллекции, но не множества, предоставляя таким образом возможность двум ненаправленным путям иметь одинаковые конечные точки, а двум направленным путям — одинаковое место происхождения и место назначения. Такие пути называются параллельными, или множественными путями. Параллельными путями могут быть маршруты полетов (как в примере 12.5), когда между двумя пунктами по одному и тому же мар-

19 Зак. 2456

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

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

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

Утверждение 12.1. Если G является графом, имеющим т путей, то

Доказательство. В этом уравнении путь (u,v) учитывается дважды: один рзз до конечной точки и, второй раз — до конечной точки v. Таким образом, общее количество путей, определяющих степени узлов, равно

их удвоенному количеству.

1

Утверждение 12.2. Если Gявляется направленным фафом с т путями, то

Доказательство. В направленном графе путь (u,v) передает один объект в исходящую степень своего места происхождения и и один объект — во входящую степень места назначения v. Таким образом, общее количество путей, учтенных в исходящих степенях узлов,,будет равно количеству путей во входящих степенях, тр есть имеющемуся количеству путей.

Утверждение 12.3. Пусть G — простой граф с п узлами и т путями. Если G является ненаправленным, то т< п(п – 1) /2, если же С — направ- «ленный, то щй п(п- 1). . ,                                           ,

Доказательство. Пусть G является ненаправленным храфом. Так как два пути могут иметь один и тот же конечный пункт и петли отсутствуют, максимальная степень узла в G составляет п – 1. Таким образом, согласно утверждению 12.1, выполняется условие 2т < п(п – 1). Теперь предположим, утр ,(? являемся направденнгым. Поскольку ни один узел не может

быть местом происхождения или назначения для двух разных путей, а петли также отсутствуют, максимальная полустепень захода узла в G составляет п – 1. Тогда, согласно утверждению 12.2, выполняется условие т < п(п – 1).

Проще говоря, последнее утверждение означает, что простой граф из п узлов имеет 0(п2) путей.

Маршрутом (path) графа называется последовательность сменяющихся узлов и путей, начинающаяся в одном и заканчивающаяся в другом узле, причем каждый путь является инцидентным относительно своего предшественника и последователя. Циклом (cycle) называется маршрут, пункт отправления и пункт назначения которого являются одним и тем же узлом. Маршрут является простым, если каждый,узел на его пути уникален. Цикл также будет простым, когда каждый узел на его пути уникален, за исключением первого и последнего. Направленным маршрутом считается маршрут, все пути которого являются направленными и проходят вдоль своих направлений. Направленный цикл определяется точно так же. Например, в схеме полетов на рис. 12.2 маршруты BOS, NW 35, JFK, АА 1387, DFW будут простыми направленными, a LAX, UA 120, ORD, UA877, DFW, АА49, LAX — это простой направленный цикл.

\

Пример 12.6. Промоделируем маршрут движения супружеской пары в ресторан на графе G, представляющем карту города (см. пример 12.3). При условии отсутствия проезда через один и тот же перекресток дважды их маршрут будет простым маршрутом в G. Таким же образом моделируется дорога этой пары от дома до ресторана и обратно в виде кольца. Если они едут домой из ресторана не по той дороге, по которой приехали, в том числе не пересекая ни одного из прежних перекрестков, то их поездка будет представлять собой простой цикл. И наконец, если они ехали туда и обратно только по улицам с односторонним движением, то их путь можно назвать направленным циклом.         !

Подграфом графа G будет граф //, узлы и пути которого являются подмножеством узлов и путей G. Например, в схеме полетов рис. 12.2 узлы BOS, JFK и MIA и пути АА903 и DL 247 формируют подграф. ОсШовным подграфом (spanning subgraph) графа G будет подграф, содержащий все узлы графа G. Граф является связным, если для любых двух узлов существует соединяющий их путь. Если граф не является связным, его максимальные связные подграфы называются связными компонентами. Лесом (forest) называется граф, не имеющий циклов. Дерево представляет собой связный лес, то есть связный граф без циклов. Заметьте, что здесь определение дерева отличается от приведенного в главе 6. А именно, применительно к графам, у дерева нет корня. Чтобы не было никакой двусмысленности, дерево из главы 6 будем считать деревом с корнем, а деревья из

этой главы — свободными деревьями. Связные компоненты леса являются (свободными) деревьями. Ocmoenbte деревья графа являются остовными подграфами, то есть (свободными) деревьямй.

Пример 12.7. Возможно, наиболее известным примером является Интернет, который можно рассматривать как граф, узлами которого являются компьютеры, а (ненаправленными) путями — связи между парами компьютеров в Сети. Компьютеры и связи между ними в одном домене, например, wiley.com, формируют подграф Интернета. Если этот подграф является связным, то два пользователя на компьютерах данного домена могут посылать друг другу письма без выхода за пределы домена. Положим, что пути этого подграфа формируют остовное дерево. Это предполагает, что при обрыве даже Ъдной связи (например, кто-то выдернул сетевой шнур из компьютера) этот подграф уже не может быть связным.

Деревья, леса и связные графы обладают несколькими простыми свойствами.

Утверждение 12.4. Пусть G будет направленным графом из п узлов и т путей. Тогда имеет место следующее:

•                      если G является связным, то т > п — 1;

•                      если G является деревом, то т = п — 1;

•                      если G является лесом, то т < п — 1.

Обоснование данного утверждения оставляем для упражнения 3-12.1.

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии