Новиков Ф.А. Дискретная математика для программистов (860615), страница 48
Текст из файла (страница 48)
В частности:GIUG2G1 = G2=G2UGI,G1 - G2,G1 + G2 = G2 +GIUG2=GI,GI+G2.254Глава8.СвязностьЗАМЕЧАНИЕОперации добавления и удаления ребра взаимно обратны:Ve<E Е,е$Е((G - е) + е = (G + е) - е = G) .В то же время Уг/ ^ V ((G + v') — v' = G), но если вершина v графа G не изолированная,то (G — v) + v ф G, потому что в этом случае q((G — v) + v) < q(G).Результат выполнения нескольких последовательных операций удаления илидобавления вершин или рёбер пе зависит от порядка выполнения операций:(G+Vl) +v2 = {G + v2)+ Vl,(G + ei) + e2 = (G + e2) + eb(G-Vl)-v2= (G- v2) - Vl,(G - ei) - e2 = (G - e2) - ег.Поэтому операции удаления и добавления вершин и рёбер можно обобщить, идопускать в качестве второго аргумента множества вершин и рёбер.ОТСТУПЛЕНИЕПриведённые определения операций над графами и примеры к ним дают повод затронутьодин тонкий вопрос, связанный с различиями в традициях математических и программных обозначений.
Рассмотрим пример к операции дизъюнктного объединения графов(Кз,з = C3UC3). Если введённые обозначения понимать буквально, то этот пример кажется противоречащим определению. Действительно, определение требует, чтобы множествавершин объединяемых графов не пересекались. Если считать, что Сз обозначает конкретный треугольник, то придётся признать, что в выражении Сз U Сз множества вершин петолько пересекаются, но и совпадают, а значит, операция объединения неприменима. Насамом деле Сз обозначает как класс треугольников (все треугольники изоморфны какграфы), так и отдельный объект — экземпляр этого класса.
Как именно следует пониматьобозначение, считается ясным из контекста. Если стремиться к (излишней в данном случае) строгости и однозначности обозначений, то приведённый пример можно было бызаписать, например, так:VGi(Vi,£i) G C3,G2(V2,£;2) € Сз (Vi П V2 ф 0 = • 3G 3 (V3,£ 3 ) е #з,з (Gi U G2 ~ Щ ) .Подобная неоднозначность обозначений присуща и программированию, хотя и в меньшейстепени.
Например, ключевое слово int в различных контекстах может обозначать встроенный тип данных (класс объектов), операцию порождения нового объекта этого типа(экземпляра класса), операцию преобразования другого объекта в объект типа int (явное приведение). Следуя стилю объектно-ориентированных языков программирования,приведённый пример можно было бы записать так:пехуДТз.з = newC3 U newC3.Ради краткости и простоты изложения в этой книге принят значительно менее строгийстиль обозначений в надежде на то, что программистская интуиция и здравый смыслпозволят читателю избежать заблуждений, несмотря на вольности в обозначениях.7.4.
Представление графов в программах2557.4. Представление графов в программахСледует еще раз подчеркнуть, что конструирование структур данных для представления в программе объектов математической модели — это основа искусства практического программирования. Мы приводим четыре различных базовыхпредставления графов. Выбор наилучшего представления определяется требова*ниями конкретной задачи. Более того, на практике используются, как правило,некоторые комбинации или модификации указанных представлений, общее число которых необозримо. Но все они так или иначе основаны на тех базовыхидеях, которые описаны в этом разделе.7.4.1.
Требования к представлению графовИзвестны различные способы представления графов в памяти компьютера, которые различаются объёмом занимаемой памяти и скоростью выполнения операций над графами. Представление выбирается, исходя из потребностей конкретной задачи. Далее приведены четыре наиболее часто используемых представления с указанием характеристики n(p,q) — объёма памяти для каждогопредставления.
Здесь р — число вершин, a q — число рёбер.ЗАМЕЧАНИЕЗначение характеристики n(p,q) указывается с помощью символа О, который означает совпадение по порядку величины (или равенство с точностью до мультипликативнойконстанты с, см. замечание в подразделе 1.3.4). Применительно к измерению занимаемойпамяти использование символа О связано с тем, что память может быть измерена в битах, байтах, машинных словах или иных единицах. Коэффициент с при этом меняется,а порядок величины остаётся.Представления иллюстрируются на конкретных, примерах графа G и орграфа D,диаграммы которых представлены на рис.
7.10.Рис. 7.10. Диаграммы графа (слева) и орграфа (справа), используемыхв качестве примеров7.4.2. Матрица смежностиПредставление графа с помощью квадратной булевой матрицыМ : a r r a y [ l . . p , 1 ..р\ o f 0..1,256Глава8.Связностьотражающей смежность вершин, называется матрицей смежности, где1, если вершина vi смежна с вершиной Vj,О, если вершины Vi и Vj пе смежны.M[i,j]Для матрицы смежности n(p,q) = 0(р2).ПримерG:0101101101011110D:0001100001010100ЗАМЕЧАНИЕМатрица смежности графа симметрична относительно главной диагонали, поэтому достаточно хранить только верхнюю (или нижнюю) треугольную матрицу.7.4.3.
Матрица инциденцийПредставление графа с помощью матрицыЯ : array [1 ..р, l..q] of 0..1,для орграфов Я : array [1 ..р, 1 ..q] of -1..1,отражающей инцидентность вершин и рёбер, называется матрицей инциденций,где для неориентированного графа1, если вершина Vi инцидентна ребру ej,О, в противном случае,H[iJ] =а для ориентированного графа1,H[hj] = \ 0,если узел Vi инцидентен дуге ej и является её концом,если узел v.L и ребро ej не инцидентны,-1,если узелинцидентен дуге е3 и является её началом.Для матрицы инциденций п(р, q) — Q(pq).Пример11000110001110010101D:-11000-110001-1100-10-101ЗАМЕЧАНИЕДля связных графов q > р, поэтому матрица смежности несколько компактнее матрицыинциденций.7.4. Представление графов в программах2577.4.4.
Списки смежностиПредставление графа с помощью списочной структуры, отражающей смежностьвершин и состоящей из массива указателейГ : array [l..p] of 1 Nна списки смежных вершин, где элемент списка представлен структуройN = record v : l..p; п : | N end record,называется списком смежности. В случае представления неориентированных графов списками смежности n(p, q) = 0(p + 2q), а в случае ориентированных графовn{jp,q) = 0{p + q).ЗАМЕЧАНИЕМассив Г также можно представить списком.ПримерСписки смежности для графа G и орграфа D представлены па рис.
7.11.Рис. 7.11. Списки смежности для графа G (слева) и орграфа D (справа)7.4.5. Массив дугПредставление графа с помощью массива структурЕ : array [L.g] of record b,e : l..p end record,отражающего список пар смежных вершин (или, для орграфов, узлов), называется массивом рёбер (массивом дуг).
Для массива рёбер (или дуг) n(p,q) = 0(2q).ЗАМЕЧАНИЕДля представления графов с изолированными вершинами может понадобиться хранитьещё и число р, если только система программирования не позволяет извлечь это число измассива структур Е.258Глава8.СвязностьПример Представление с помощью массива рёбер (дуг) показано в следующейтаблице (для графа G слева, а для орграфа D справа).ЗАМЕЧАНИЕУказанные представления пригодны для графов и орграфов, а после некоторой модификации — также и для псевдографов, мультиграфов и гиперграфов.7.4.6. Обходы графовОбход графа — это некоторое систематическое перечисление его вершин (и/илирёбер). Наибольший интерес представляют обходы, использующие локальнуюинформацию (списки смежности).
Среди всех обходов наиболее известны поискв ширину и в глубину. Алгоритмы поиска в ширину и в глубину лежат в основемногих конкретных алгоритмов на графах.Алгоритм 7.1 Поиск в ширину и в глубинуВход: граф G(V,E), представленный списками смежности Г.Выход: последовательность вершин обхода,for v € V dox[v]: = 0 { вначале все вершины не отмечены }end forselect v е V { начало обхода — произвольная вершина }v —• Т { помещаем v в структуру данных Т...}x[v]: = 1 { ... и отмечаем вершину v }repeatи <— Т { извлекаем вершину из структуры данных Т...}yield и { ... и возвращаем её в качестве очередной пройденной вершины }for w еТ(и) doif x[w) = 0 thenwT { помещаем w в структуру данных Т...}x[w]: = 1 { ...
и отмечаем вершину w }end ifend foruntil T = 0Если в алгоритме 7.1 структуры данных Т — это стек (LIFO — Last In First Out),то обход называется поиском в глубину. Если Т — это очередь (FIFO — First InFirst Out), то обход называется поиском в ширину.7.4. Представление графов в программах259Пример В следующей таблице показаны протоколы поиска в глубину и в ширину для графа, диаграмма которого приведена на рис.
7.12. Предполагается, чтоначальной является вершина 1. Слева в таблице протокол поиска в глубину, асправа — в ширину. На рис. 7.12 сплошные стрелки с номерами рядом с рёбрамипоказывают движение по графу при поиске в глубину, а пунктирные — в ширину.иТиТ14322,42,32012432,44,33032Рис. 7.12. Диаграмма графа к примеру обхода в ширину и в глубинуЕсли граф G связен (и конечен), то поиск в ширину и поиск в глубинуобходят все вершины по одному разу.ТЕОРЕМАДОКАЗАТЕЛЬСТВО[Единственность обхода вершины] Обходятся только вершины, попавшие в Т.В Т попадают только неотмеченные вершины.
При попадании в Т вершинаотмечается. Следовательно, любая вершина будет обойдена пе более одного раза.[Завершаемость алгоритма] Всего в Т может попасть пе более р вершин. Накаждом шаге одна вершина удаляется из Т. Следовательно, алгоритм завершитработу пе более чем через р шагов.[Обход всех вершин] От противного. Пусть алгоритм закончил работу и вершина w не обойдена. Значит, w не попала в Т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
