Дискретная математика (998286), страница 36
Текст из файла (страница 36)
Если в орграфе полустепень захода некоторой вершины равна нулю (то есть д+(о) = О), то такая вершина называется источником, если же нулю равна полу- степень исхода (то есть д (о) = О), то вершина называется стоком. Направленный орграф с одним источником и одним стоком называется сетью. 7.3.4.
Операции над графами Введем следующие операции над графами: 1. Дополнением графа С(УмЕг) (обозначение — Сг(УыЕг)) называется граф С(Уг, Ег), где Уг.=УгЙЕг.— — Уг.=(е Е Уг х Уг ~ е фЕг). 2. Обьединением графов Сг(Уы Ег) и Сг(Уг, Ег) (обозначение — С,(Ую Ег) 0Сг(Уг, Ег), при условии У и Уг = О, Е, йЕг —— ю) называется граф С(У, Е), где У,=Уг 0 Уг(кЕ:=Ег 0Ег. Пример Ез,з =Сз0Сз 3. Соединением графов Сг(Уы Ег) и Сг(Уг, Ег) (обозначение — Сг(Ую Ег) + Сг(Уг, Ег), при условии Уг й Уг = Е, Ег й Ег = е) называется граф С(У, Е), где У:=Уг 0Уг8гЕ:=Ег 0Ег0(е =(оыег) ! ог Е Угкгог е Уг).
Пример К,„=К +К„. 2ОО Глава 7. Графы й уоалеиие вершины е из графа Сг(ЪыЕг) (обозначение- . СгЯ,Я) — ю, при условии е е Ъ;) дает граф Сг(Ъг, Ег), где Ъг.=Ъг ~ [о)йЕг.— — Ег ~(е = (вьюг) ~ ег =еаза = е). Пример Сз — е = Кг. 5. Иалеиив Ребра е из графа Сг(Ъы Ег) (обозначение — С,(Ъы Е,) — е, при условии е б Е,) дает граФ Сг(Ъг Ег), где Ъг. =Ъ",йЕг . .=Ег 'г (е). Пример Кг — е = Кг. 6. Добавление вершины е в граф С,(ЪшЕг) (обозначение — Сг(ЪыЕг) + о, при условии о ф Ъг) дает граф Сг(Ъг, Ег), где Ъг.=Ъз 0(е) йЕг.=Ег.
Пример С+о = СОКг 7. Добавление РебРа е в гРаф Сг(Ъ;, Е) (обозначение — Сг(Ъш Ег) + е, пРи Условии е й Ег) дает граф Сг(Ъш Ег), где Ъ г .' = Ъг й Ег .' = Ег 0 (е). 8. Стягивание подграфа А графа Сг(ЪшЕг) (обозначение — Сг(ЪгыЕг)7А, при условии А с Ъ'г) дает граф Сг(Ъг, Ег), где Ъг.=(Ъг ~А) 0(и)й Ег . = Ег ~.(е = (и, ю) ~ и б А Ч ш е А) 0 (е = (и, о) ~ и е Г(А) ~ А) . Пример К4/Сз = Кг. 9. Размножение вершины е графа Сг(Ъы Ег) (обозначение — Сг(Ъы Ег) 7' е, при условии А с Ъы е е Ъы ю' ф Ъг) дает граф Сг(Ъг, Ег), где Ъ г ° — Ъг 0 (е') й Ег .
= Ег 0 ((е, е')) О (е = (и, е') ~ и е Г+(ю) ) . Пример Кг Т е = Сз. 201 74. Представление графов в ЭВМ 7.4. Представление графов в ЭВМ Следует еще раэ подчеркнуть, что конструирование структур данных для представления в программе объектов математической модели — это основа искусства практического программирования. Мы приводим четыре различных базовых представления графов. Выбор наилучшего представления определяется требованиями конкретной задачи. Более того, при решении конкретных задач используются, как правило, некоторые комбинации или молификации указанных представлений, общее число которых необозримо. Но все они так или иначе основаны на тех базовых идеях, которые описаны в этом разделе.
7.4.1. Требования к представлению графов Известны различные способы представления графов в памяти компьютера, которые различаются объемом занимаемой памяти и скоростью выполнения операций нац графами. Прелставление выбирается, исходя из потребностей конкретной задачи. Далее приведены четыре наиболее часто используемых представления с указанием характеристики и(р, д) — объема памяти для каждого представления. Здесь р — число вершин, а (( — число ребер. ЗАМЕЧАНИЕ Указанные представления пригодны Лля графов н орграфов, а после некоторой модификации также н Лля псевдографов, мультнграфов и гиперграфов. Прелставления иллюстрируются на конкретных примерах графа С и орграфа О, диаграммы которых представлены на рис. 7.10. Юз ст ез Рис. 7.10. Диаграммы графа (спевв) и оргрвфв (справа), используемых в качестве примеров 7.4.2.
Матрица смежности Представление графа с помощью квадратной булевской матрицы М: аггау [1..р, 1..р~ оГ 0..1, отражающей смежность вершин, называется мат)ищей смежноспги, где 11, если вершина тч смежна с вершиной с, т7 г ~0, если вершины щ и су не смежны. го2 Глава 7.
Графы Яля матрицы смежности и(р, о) = О(ра). Пример 1 0 1 0 1 1 1 0 1 1 1 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 1 0 7.4.3. Матрица инциденций Представление графа с помощью матрицы Н: аггау [1..р, 1..е] о(' 0..1 (для оргра- фов Н: аггау [1..р,1,.е] оГ -1..1), отражающей инцидентность вершин и ребер, называется матрицей иициденций, где для неориентированного графа ] 1, если вершина сч инцндентна ребру е, Н[',Я= ' ~[[0, в противном случае, а для ориентированного графа т 1, если вершина еа инцидентна ребру е и является его концом, н[1, г] = о, если вершина са и ребро ет не пнцидентны, -1, если вершина гц ннцидентна ребру е и является его началом.
Для матрицы инциденций и(р, д) = О(рц). Пример — 0 0 1 0 1 — 1 0 0 — 1 0 1 1 0 0 0 0 -1 — 1 1 0 0 1 1 0 0 1 1 0 0 1 1 7.4.4. Списки смежности Пример Списки смежности для графа О и орграфа Р представлены на рис. 7. Представление графа с помощью списочной структуры, отражающей смежность вершин н состоящей из массива указателей Г: мтау [1..р] о('7 Ф на списки смежных вершин (элемент списка представлен структурой Ф: гесогг( е: 1..р; и:7 Н епогесого), называется списком смежносиш.
В случае представления неориентированных графов списками смежности о(р, е) = О(р+ 2д), а в случае ориентированных графов п(р,д) = О(р+ а). 203 7.4. Представление графов е ЭВМ Рнс. т. 11. Списки смежности длн графа В (слеаа) н орграфа 0 (справа) 7.4.5. Массив дуг Представление графа с помощью массива структур Е: аггау (1..р[ ог гесотч( Ь, е: 1..р епт(гесогт(, отражающего список пар смежных вершин, называется массивом ребер (или, для орграфов, массивом дуг). Для массива ребер (или дуг) п(р,о) = О(2()). Пример Представление с помощью массива ребер (дуг) показано в следующей таблице (для графа О слева, а для орграфа 1) справа).
7.4.6. Обходы графов Обход графа — это некоторое систематическое перечисление его вершин (иггили ребер). Наибольший интерес представляют обходы, использующие локальную информацию (списки смежности). Среди всех обходов наиболее известны поиск в ширину и в глубину. Алгоритмы поиска в ширину и в глубину лежат в основе многих конкретных алгоритмов на графах.
Алгоритм г.1. Поиск в ширину н в глубину Вход: граф О(тг, Е), представленный списками смежности Г. Выход: последовательность вершин обхода. 1ог о б 1' т(о х[о]: =0( вначале все вершины не отмечены ) епт) Еог ве)ес( о е И( начало обхода — произвольная вершина ) о -+ Т( помещаем о а структуру данных Т... ) 204 Глава 7.
Графы в[в]: = 1( ... н отмечаем вершину в ) терев 1 и г — Т( извлекаем вершину нз структуры данных Т... ) у!е!и и( ... и возвращаем ее в качестве очередной пройденной вершины ) гог ю Н Г(и) г!о !Г х[ю] = о г!геп ю -+ Т( помещаем ю в структуру данных Т ... ) х(ю] г = 1( ... и отмечаем вершину ю ) епй !1 епй Гог пп61 Т = а Если Т вЂ” зто стек (1.1ЕΠ— ?лзг 1п Е!гзг Опт), то обход называется поиском в глубину. Если Т вЂ” зто очередь (Е1ЕΠ— Е!гзг 1п Е!гзг Опт), то обход называется поиском в ширину. Пример В следующей таблице показаны протоколы поиска в глубину и в ширину для графа, диаграмма которого приведена на рис. 7.12. Слева в таблице протокол поиска в глубину, а справа — в ширину.
Предполагается, что начальной является вершина 1. Рнс. 7.12. Диаграмма графа к примеру обхода а ширину н а глубину ТЕОРЕМА Если граф С свезен (и конечен), то поиск в ширину и поиск в гзубину обойдут все вершины по одному разу. Доклзлтальство 1. Единственность обхода вершины. Обходятся только вершины, попавшие в Т.
В Т попалают только неотмеченные вершины. При попадании в Т вершина отмечается. Следовательно, любая вергпина будет обойдена не более одного раза. 205 7.4. Представление графов а ЗВМ 2. Завершаемость алгоритма. Всего в Т может попасть не более р вершин На каждом шаге одна вершина удаляется из Т. Следовательно, алгоритм завершит работу не более чем через р шагов. 3. Обход всех вершин. От противного. Пусть алгоритм закончил работу, и вершина ш не обойдена.
Значит, ш не попала в Т. Следовательно, она не была отмечена. Отсюда следует, что все вершины, смежные с и, не были обойдены и отмечены. Аналогично, любые вершины, смежные с неотмеченными, сами не отмечены (после завершения алгоритма). Но С связен, значит, существует путь (о, ш). Следовательно, вершина и не отмечена. Но она была отмечена на первом шаге! С! СЛЕДСТВИЕ ПУсть (иы..., ип, .., и,, ир) — обход (то есть последовательность вершин) при поиске в ширину. Тогда 'т'г > 7' 4(имиг) < д(ит,и ). Другими словами, расстояние текущей вершины от начальной является монотонной функцией времени поиска в ширину, вершины обходятся в порядке возрастания расстояния от начальной вершины.
СЛЕДСТВИЕ Пусгпь (ит,..., и„..., ир) — обход при поиске в глубину. ~Ьгда Чг' > 1 д(им и,) < ! < р. Другими словами, время поиска в глубину любой вершины не менее расстояния от начальной вершины и ие более общего числа вершин, причем в худшем случае время поиска в глубину может быть максимальным, независимо от расстояния до начальной вершины. СЛЕДСТВИЕ Пуопь (ит,...,иг,...,и„) — обход при поиске в ширину, а Р(им 1), Р(ит, 2),...
— ярусы графа относительно вершины ит. Тогда В(нннд В!ьььд-1 Чт' > 1 ~ /Р(ит,т)! < 1 < ~~ !Р(иы7)!. Другими словами, время поиска в ширину ограничено снизу количеством вершин во всех ярусах, находящихся на расстоянии меньшем, чем расстояние от начальной вершины до текущей, и ограничено сверху количеством вершин в ярусах, начиная с яруса текущей вершины и включая все меньшие ярусы. СЛЕДСТВИЕ Пусть (им..., иг,..., ир) — обход при поиске в ширину, а (от,... ог,..., ср) — обход при поиске в глубину, где иг = ого Тогда в среднем г = 2у.
Другими словами, поиск в глубину в среднем вдвое быстрее, чем поиск в ширину. 2ОВ Глава 7. ГраФы 7.5. Орграфы и бинарные отношения Целью зтого, заключительного раздела данной главы является устаиовлеиие свя- зи теории графов с другими разделами дискретной математики. 7.5.1. Графы и отношения Любой орграф С(У, Е) с петлями, ио без кратных дуг задает бинарное отношение Е иа множестве У, и обратно.
А именно, пара элементов принадлежит отношению (а, Ь) е Е с и х У тогда и только тогда, когда в графе С есть дуга (а, Ь). Полный граф соответствует универсальному отношению. Граф (иеориеитироваииый) соответствует симметричному отношению. Дополнение графов есть дополиеиие отношений. Изменение направления всех дуг соответствует обратному отношению. Гиперграф соответствует многоместному отношению и т. д. ОТСТУПЛЕНИЕ Таким образом, имеется полная аналогия между оргафами и бинарными отцошеинями— фактически, это один и тот же класс объектов, только описанный разными средствами. Отношения (а частности, функции), являются базовыми средствами дхя построения подавляющего большинства математических моделей, используемых при решении практических задач.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
