4.3Заданиеграфов

МатрицейсмежностиграфаG=(V,E)называетсяматрицаA=||a_ij||n×nсэлементамиa_ij=1,если{i,j}∈E,иa_ij=0,если{i,j}/∈E.Длямультиграфовa_ijравнократностиребра{i,j}.

Аналогичновводитсяматрицасмежностидляорграфов.Длянеориентированныхграфовматрицасмежностиполностьюопределяетсясвоейправойверхнейлиболевойнижнейтреугольнойподматрицей,посколькуa_ij=a_jiдлявсехiиj.

Орграфымогутбытьтакжепредставленыоднимилинесколькимиспискаминепосред-

ственныхпоследователейA⁰(i)инепосредственныхпредшественниковB⁰(i)каждойвер-шиныi.

4.4Топологическаясортировка

Предположим,чтофирменеобходимовыполнитьnпроектов,намножествеV={1,...,n}

^{которыхзаданоотношениепредшествования→такое,чтоизi→jследует,чтопроектj}

неможетначатьсяраньше,чемзакончитсяпроектi(проектjиспользуетинформациюили

продукцию,получаемуюврезультатевыполненияпроектаi).Нужнонайтидопустимыйпорядоквыполненияпроектоввовремени.

^{РассмотриморграфG=(V,A)отношенияпредшествования.Дуга(i,j)∈Aтогдаи}

^{толькотогда,когдаi→j.}

Решениезадачисуществует,еслиорграфотношенияпорядканесодержитциклов.Если

естьцикл,тониодинизпроектов,принадлежащихциклу,нельзяначинать.

Пустьперестановка(i₁,...,i_n)определяетпорядоквыполненияпроектов.Этотпорядокявляетсядопустимым,еслиизi_j→i_kследует,чтоi_{jпредшеств}уетi_kвуказаннойпере-

становке.

Введемпонятиеномеравершины–label(i)∈{1,...,n}.ЗадачасводитсякотысканиюнумерациивершинграфаGтакой,чтоиз(i,j)∈Aследуетlabel(i)<label(j).Тогда

последовательностьпроектоввпорядкевозрастанияихномеровlabel(i)будетявлятьсярешениемзадачи.Указаннаянумерацияназываетсятопологическойсортировкойвершинграфа.

Алгоритмтопологическойсортировки.

Предположим,чтографзаданспискаминепосредственныхпоследователейA⁰(i),i=

1,...,n,и,крометого,заданоколичествонепосредственныхпредшественниковb_iкаж-дойвершиныi:b_i=|B⁰(i)|.

^{Шаг1.Просматриваемсписок(b}1^,...,bn^{)исоздаемсписокJ={j|b}j^{=0}вершин,у}

которыхнетпредшественников.ЕслиJ=φ,товграфеестьцикл.

Шаг2.Присваиваемтекущийномерj(вначалеj=1)любойвершинеизJ.Далеерас-сматриваемвсехеенепосредственныхпоследователейi∈A⁰(j)ипреобразуемb_i=b_i−1.

Еслиb_i=0,товершинуiвключаемвJ.Послетого,каквсемножествоA⁰(j)просмотрено,удаляемjизJ.Еслитекущийномернеравенn,увеличиваемегонаединицу.ПовторяемШаг2.

4.5Остовноедерево(остов)минимальноговеса

Граф,неимеющийциклов,называетсялесом.Связныйграф,неимеющийциклов,назы-ваетсядеревом.

Пустьnиm–количествавершиниреберграфасоответственно.

Теорема4(Свойствадеревьев)ПустьG–неориентированныйграф.Тогдаследую-щиеусловияэквивалентны:

1)G–дерево,

^{2)G–связныйграфиm=n−1,}

^{3)G–графбезцикловиm=n−1,}

4)междулюбойпаройвершинсуществуетединственнаяцепь,

5)Gнеимеетциклов,нопридобавлениипроизвольногоребравGвнемвозникаетедин-ственныйцикл.

Вориентированномграфевводятсяпонятиявходящегоивыходящегодерева.Этоорграф,неориентированныйаналогкоторогоявляетсядеревом,и,

вслучаевыходящегодерева,вкаждуювершинувходитнеболееоднойдуги,а

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

ПодграфнеориентированногографаG=(V,E)называетсяостовнымдеревом(остовом)

иобозначаетсяT,еслиT–деревоимножествоеговершинсовпадаетсV.

^{Графназывается(реберно)взвешенным,есликаждомуегоребру{i,j}приписаннекото-}

^{рыйвесw}_ij^.

Весомостовногодереваназываетсясуммавесоввсехегоребер.

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

Нижеприводятсядваалгоритма,которыестроятостовноедеревоминимальноговесаT_n−1.

^{Напомним,чтоTn−1несодержитцикловиимеетn−1ребер.}

АлгоритмКраскала

^{Шаг1.ПолагаемT}₀^{=(V,φ),|V|=n.}

^{Шаг2.Дляi=0,...,n−1полагаемTi+1=Ti∪e,гдеe–реброGсминимальнымвесом}

^{такое,чтоононеявляетсяребромT}_i^{инеобразуетцикласребрамиT}_i^.

АлгоритмПрима

^{Шаг1.ПолагаемT}₁^=(V₁^,E₁^),гдеV₁^={a,b},E₁^={a,b},иw_ab^=min{w_e^|e∈E}.

^{Шаг2.Дляi=1,...,n−1полагаемTi+1=Ti∪e,гдеe–реброGсминимальнымвесом}

^{такое,чтоононеявляетсяребромT}_i^{исвязываетT}_i^{свершинойG,непринадлежащейT}_i^.

Пример.Любойнеориентированныйреберновзвешенныйграф.