Дискретная математика (998286), страница 37
Текст из файла (страница 37)
С другой стороны, графы допускают наглядное представление в виде диаграмм. Это обстоятельство объясняет широкое использование диаграмм различного вида (которые суть представления графов или родственных объектов) при кодировании н особенно при проектировании з программировании.
7.5.2. Достижимость и частичное упорядочение В качестве примера связи между орграфами и бинарными отношениями рассмотрим отношения частичного порядка с точки зрения теории графов. Вершина и в орграфе С(У, Е) достижима из вершины о, если существует путь из э в и. Путь из о в и обозначим (йо). Отношение достижимости можно представить матрицей Т: аггау [1..р,1..р) оГ 0..1, где Т(л', ~] = 1, если вершина ог достижима из вершины оо и Т(л, Я = О, если вершина еу недостижима из вершины иь Рассмотрим отиошеиие строгого частичного порядка л-, которое характеризуется следующими аксиомами: ь аитирефлексивиостгс Уо Е У (о л- о); ь траизитивиостгс Уи, о, ш (о л.
ш бгш ь- и =л о л- и); а аитисмметричиостгс Чи,о (и ь- ойо л- и). Отношению строгого частичного порядка РС У х У можно сопоставить граф С(У, Е), в котором а ~ Ь ч=л (а,6) е Е. ТЕОРЕМА Если отношение Е есть строгое частичное утюрядочение„то орграф С(У, Е) не имеет контуров. 207 7.5. Орграфы и бинарные отношения ДОКАЗАТЕЛЬСТВО От противного. Пусть в С есть контур. Рассмотрим любую дугу (а, Ь) в этом контуре. Тогда имеем а >- Ь, но Ь ~ а по транзнтивности, что противоречит строгости упорядочения. П ТЕОРЕМА Если орграф С(У,Е) не имеет контуров, то достижимость есть строгое частичное упорядочение.
ДОКАЗАтЕЛЬСтво 1. Нет циклов, следовательно, нет петель, следовательно, достнжимость антирефлекснвна. 2. Если существуют пути из о я и и из и " и, то существует и путь из'о в и. Следовательно, достижимость транзитивна. 3. Пусть достижнмость — зто не строгое упорядочение. Тогда Э и, о и ь- о ьс о >. и, то есть существует путь из о в и и из и в ш Следовательно, существует контур (йо) + (о, и), что противоречит условию. П ТЕОРЕМА Если орграф не имеет контуров, то в нем есть вершина, полустенень захода которой равна О. ДОКАЗАТЕЛЬСТВО От противного.
Пусть такой вершины нет, тогда для любой. вершины найдется вершина, из которой есть дуга в данную вершину. Следовательно, имеем контур против направления стрелок. П ЗАМЕЧАНИЕ Эта теорема позволяет найти минимальный элемент в конечном частично упорядоченном множестве, который требуется в алгоритме топологической сортировки (алгоритм 1.7).
А именно, минимальный элемент — это источник, то есть вершина, которой в матрице смежности соответствует нулевой столбец. 7.5.3. Транзитивное замыкание Если Š— бинарное отношение иа У, то транзитивным замыканием Е+ на У будет отношение достижимости на орграфе С(У, Е). ТЕОРЕМА Пусть М вЂ” матрица смежности орграфа С(У, Е). Тогда Мь(г', г] = 1 в том и только в том случае, если сушествует путь длиной Ь из вершины ог в вершину ог. Глава т. Графы 208 ДОКАЭАтвльотво Индукция по й.
База: й = 1, М1 = М вЂ” пути длины пути длины й — 1. Тогда Пусть МА ' содержит м" [1,1] = ~ м"-'[', ]1 м[1, ], 1=1 то есть путь длины й нз вершины 1 в вершину 1 существует тогда и только тогда, когда существуют вершина 1, такая что существует путь длины й — 1 из 1 в 1 и дуга (1,1), то есть 3 (1, 1) ](1, 1)] = й е=ь 31 (3 (1, 1) ](1, 1)] = й — 1й((,,у) 6 Е). П Если Т вЂ” матрица достижимости, то очевидно, что р т= ~/м". А=1 Трудоемкость прямого вычисления по этой формуле составит О(р~). Матрица достижимости Т может быть вычислена по матрице смежности М алгоритмом Уоршалла (алгоритм 1.8) за 0(рз). Комментарии Эта глава является вводной главой второй части, поэтому здесь уместно привести беглый обзор учебной литературы по теории графов.
Классическими учебниками по теории графов являются книги [2] и [23]. Первая является библографической редкостью, а последняя монография переиздавалась в нашей стране и является образцовой по глубине и широте охвата материала и одновременно по ясности и лаконичности изложения. Терминология и обозначения книги [23] взяты за основу в данном учебнике.
Книга [23], хотя и имеет сравнительно небольшой объем, содержит большое число прекрасных упражнений и различные сведения справочного характера. В меньшей степени в ней представлены программистские аспекты теории графов. Существуют и другие доступные учебники по теории графов: [6, 21]. Последняя книга вполне доступна даже неподготовленному читателю, имеет небольшой объем, но в то же время вполне достаточна для первоначального знакомства. Разделы, посвященные теории графов, как правило, присутствуют во всех учебниках по дискретной математике, хотя такие разделы, по естественным причинам, не отличаются полнотой охвата материала.
Особого упоминания заслуживают книги [11] и [5]. Содержание этих книг абсолютно точно соответствует их названиям и является необходимым для программиста дополнением к классическим монографиям типа [23]. Эти источники, особенно [11], в значительной мере повлияли на отбор материала для данного учебника.
209 Гпражнееиэ Единственный в этой главе алгоритм 7,1 носит настолько общеизвестный ха рактер, что трудно указать его источник. Идея этого алгоритма лежит в основе огромноГо числа конкретных алгоритмов на графах. Как правило, эта идея предполагаатся заранее известной читателю, и изложение сразу погружается в технические детали применения обшей концепции поиска в ширину и в глубину для решения конкретной задачи. В то же время свойства алгоритма поиска, приведенные в виде следствий к теореме, обосновывающей алгоритм 7.1, хотя и являются вполне тривиальными, не всегда осознаются практическими программистами прн решении задач. Именно поэтому представляется важным предпослать обсуждению конкретных алгоритмов на графах изложение общей идеи в предельно простой и рафинированной форме.
Упражнения 7.1. Построить пример графов Сг и Сю для которых рг = рз, д1 = дю 61 = бю Ь, = Ью но С, ~С Сэ (кроме примера подраздела 7.1.6). 7.2. Доказать, что в нетривиальном графе существуют вершины одинаковой степени. 7.3. Задача Рамсея. Доказать, что среди любых 6 человек есть либо 3 попарно знакомых, либо 3 попарно незнакомых.
7А. Рассмотрим матрицу смежности ребер С): аггау [1..ц, 1..д1 оГ 0..1, где 11, если ребро г смежно с ребром У, ~р,,г 10, в противном случае. Является ли матрица смежности ребер б) представлением в ЭВМ графа С(К Е)7 7.5. Описать в терминах теории графов отношение эквивалентности на конечном множестве.
ГЛАВА 8 Связность Данная глава является центральной во второй части. Здесь обсуждается важное для приложений понятие связности, доказывается наиболее глубокая теорема— теорема Менгера и рассматриваются самые распространенные алгоритмы поиска кратчайших путей. 8.1. Компоненты связности В русском языке есть как слово «компонент» мужского рода, так и слово «компонента» женского рода, оба варианта допустимы. Современная языковая практика склоняется к использованию мужского рода, и мы ей следуем в остальной части книги.
Однако исторически сложилось так, что «компонента связности» имеет женский род, и в этом случае мы подчиняемся традиции. 8.1.1. Объединение графов и компоненты связности Напомним, что если граф С состоит из одной компоненты связности (то есть Ь(С) = 1), то он называется связным. В связном графе любые две вершины соединены (простой) цепью.
ТЕОРЕМА Граф связен тогда и только пюгда, когда его нельзя представить в виде обьединения двуз: графов. Доказатальство Необходимость. От противного. Пусть й(С) = 1 и граф С состоит из двух компонент, то есть С = С, Я, Ег) О Сг(Ъа, Ез) где )г и Тгг = е, Ег и Еа = а, ~'г Ф в, Ъг ф в. Возьмем ог н Ъм ог б»г. Тогда З(омоа) ьг ц Уг ьгог и Ъ~.
В этой цепи Зе = (а,Ь) а ц Ъ", егЬ и Ъ~. Но тогда е Ф Еь е Ф Ет следовательно, е ф Е, 211 ВЛ. Компоненты связности Достаточность. От противного. Пусть й(С) > 1. Тогда 3 и, о Б (и, п). Следовательно, вершины и,о принадлежат разным компонентам связности. Положим Сг— компонента свизности длЯ и, а Сз — все остальное. Имеем С = Сг Г1 Сз. ЗАМЕЧАНИЕ Таким образом, несвязный граф можно всегда представить как объединение связных компонент.
Эти компоненты можно рассматривать независимо. Поэтому во многих случаях можно без ограничения общности предполагать, что рассматриваемый граф связен. 8.1.2. Точки сочленения Вершина графа называется точкой сочленения, если ее удаление увеличивает чи- сло компонент связности. ЛЕММА В любам нетривиальном графе есть (по крайней мере) две вершины, которые не являются точками сочленения.
Доказаткльство Например, это концы диаметра. 8.1.3. Оценка числа ребер через число вершин и число компонент связности Инварианты р(С), у(С) и й(С) не являются независимыми. ТЕОРЕМА Пусть р — число веришн, о — число ребер, й — число компонент связности графа. Тогда р-й<й< (р — йНр — й+ 1) 2 Доказательство 1. р — й < а. Индукция по р, База: р = 1, о = О, й = 1. Пусть оценка верна для всех графов с числом вершин меньше р. Рассмотрим граф С, р(С) = р.
Удалим в С вершину о, которая не является точкой сочленения: С': = С вЂ” и. Тогда если и — изолированная вершина, то р' = р — 1, й' = й — 1, о' = о. Имеем р — й = р' — й' < о' = д. Если о — не изолированная вершина, то р' = р — 1, й' = й, о' < о. Имеем: р — й = 1+ р' — й' < 1+ о' < о. 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
