Новиков Ф.А. Дискретная математика для программистов (860615), страница 49
Текст из файла (страница 49)
Следовательно, она не былаотмечена. Отсюда следует, что все вершины, смежные с w, не были обойденыи отмечены. Аналогично, любые вершины, связанные с неотмеченными, сами неотмечены (после завершения алгоритма). Но G связен, значит, существует путь(v,w). Следовательно, вершина v пе отмечена.
Но она была отмечена на первомшаге!•260Глава8.СвязностьПусть..., щ,..., uj,...,ность вершин) при поиске в ширину. ТогдаСЛЕДСТВИЕ 1V г < j (d{ux,ui) <ир) — обход (то есть последовательd(uuuj)).Другими словами, расстояние текущей вершины от начальной является монотонно возрастающей функцией времени поиска в ширину, вершины обходятся впорядке возрастания расстояния от начальной вершины.СЛЕДСТВИЕ 2Пусть (ui,...,щ,...,ир) — обход при поиске в глубину. ТогдаVг ^ 1 (d(u\,щ)^ г ^ р).Другими словами, время поиска в глубину любой вершины не менее расстоянияот начальной вершины и не более общего числа вершин, причём в худшем случаевремя поиска в глубину может быть максимальным, независимо от расстояниядо начальной вершины.Пусть (щ,..., щ,..., ир) — обход при поиске в ширину, a D{u\, 1),D(ui, 2 ) , . . .
— ярусы графа относительно вершины щ. ТогдаСЛЕДСТВИЕ 3Другими словами, время поиска в ширину ограничено снизу количеством вершин во всех ярусах, находящихся на расстоянии меньшем, чем расстояние отначальной вершины до текущей, и ограничено сверху количеством вершин в ярусах, начиная с яруса текущей вершины и включая все меньшие ярусы.Пусть (щ,...... ,ир) — обход при поиске в ширину, aVj,..., vp) — обход при поиске в глубину, где щ — v3. Тогда в среднем г = 2j.СЛЕДСТВИЕ 4(vi,...,Другими словами, поиск в глубину в среднем вдвое быстрее, чем поиск в ширину.7.5.
Орграфы и бинарные отношенияЦелыо заключительного раздела дайной главы является установление связи теории графов с другими разделами дискретной математики.7.5.1. Графы и отношенияЛюбой орграф G(V, Е) с петлями, но без кратных дуг, задаёт бинарное отношение Е на множестве V, и обратно. А именно, пара элементов принадлежит отношению (a, b) е Е С V х V тогда и только тогда, когда в графе G есть дуга (а, Ь).Полный граф соответствует универсальному отношению. Граф (неориентированный) соответствует симметричному отношению. Дополнение графов есть дополнение отношений.
Изменение направления всех дуг соответствует обратномуотношению и т. д.7.5. Орграфы и бинарные отношения261ОТСТУПЛЕНИЕТаким образом, имеется полная аналогия между орграфами и бинарными отношениями —фактически, это один и тот же класс объектов, только описанный разными средствами. Отношения (в частности, функции) являются базовым средством для построенияподавляющего большинства математических моделей, используемых при решении практических задач. С другой стороны, графы допускают наглядное представление в виде диаграмм. Этим обстоятельством объясняется широкое использование диаграмм различноговида (которые суть представления графов или родственных объектов) при кодированиии особенно при проектировании в программировании.7.5.2. Достижимость и частичное упорядочениеВ качестве примера связи между орграфами и бинарными отношениями рассмотрим отношения частичного порядка с точки зрения теории графов.
Узел ив орграфе G(V,E) достижим из узла v, если существует путь из v в и. Путь изv в и обозначим (v,u). Отношение достижимости можно представить матрицейТ : array [l..p,l..p] of 0..1, где T[i,j] = 1, если узел Vj достижим из узла v^ иТ[г, j] = 0, если узел vj недостижим из узла к*. Рассмотрим отношение строгогочастичного порядка у, которое характеризуется следующими аксиомами:1. Антирефлексивность: Vv е V (~>(v у v)).2.
Транзитивность:Vu, v,w ((v у w к w У и ==> v У и)).3. Антисимметричность: \/u,v (->(и У v к, v У и)).Отношению строгого частичного порядка УС V х V можно сопоставить орграфG(V, Е), в котором а у b(a, b) 6 Е.Если отношение Е есть строгое частичное упорядочение, то орграфG(V,E) не имеет контуров.ТЕОРЕМА 1О Т противпого. Пусть в G есть контур. Рассмотрим любую дугу (а, Ь) в этом контуре. Тогда имеем а У Ь, по b у а по транзитивности, чтопротиворечит антисимметричности упорядочения.•ДОКАЗАТЕЛЬСТВОЕсли орграф G(V, Е) не имеет контуров, то отношение достижимости есть строгое частичное упорядочение.ТЕОРЕМА 2ДОКАЗАТЕЛЬСТВО[Антирефлексивность] Нет контуров, следовательно, нет петель.[Транзитивность] Если существуют пути из v в w и из w в и, то существует ипуть из v в и.[Антисимметричность]От противпого.
Пусть Зи, v (и У v & v У и), то есть су-ществует путь (v, и) из v в и и путь (и, f ) из и в v. Следовательно, существуетконтур вида (u,v) + (v,u),что противоречит условию.•262Глава8.Связность3Если орграф не имеет контуров, то в нем есть узел, полустепеньзахода которого равна 0.ТЕОРЕМАО Т противного. Пусть такого узла нет, тогда для любого узланайдётся узел, из которого есть дуга в данный узел. Следовательно, имеем контурпротив направления стрелок.•ДОКАЗАТЕЛЬСТВОЗАМЕЧАНИЕЭта теорема позволяет найти минимальный элемент в конечном частично упорядоченноммножестве, который требуется в алгоритме топологической сортировки (алгоритм 1.12).А именно, минимальный элемент — это источник, то есть узел, которому в матрицесмежности соответствует нулевой столбец.7.5.3.
Транзитивное замыканиеЕсли Е — бинарное отношение на V, то транзитивным замыканием (см.Е+ на V будет отношение достижимости на орграфе G(V,E).1.5.1)Пусть М — матрица смежности орграфа G(V, Е). Тогда Mk[i, j] = 1 втом и только в том случае, если существует путь длиной к из узла Vi в узел Vj.ТЕОРЕМАИндукция по к. База: к = 1, М 1 = М — пути длины 1. Пустьсодержит пути длины к — 1. ТогдаДОКАЗАТЕЛЬСТВОMfc_1м%з\(Mk-%i}kM[ij}),= у1=1то есть путь длины к из узла г в узел j существует тогда и только тогда, когданайдётся узел I, такой, что существует путь длины к — 1 из г в / и дуга (/, j),то есть3(Cj> (l(Ci)|) = k ^ 3 l((Э(С0 ( j ( 0 ) \ = k - l j b ( l J ) e E ) y•Если Т — матрица достижимости, то очевидно, чтоР-1Т=\J Мк.к= 1Трудоёмкость прямого вычисления по этой формуле составит 0(р 4 ).
Матрицадостижимости Т может быть вычислена по матрице смежности М алгоритмомУоршалла (алгоритм 1.11) за О(р3).Упражнения263КомментарииЭта глава является вводной главой той части книги, которая посвящена теории графов, поэтому здесь уместно привести краткий обзор учебной литературы по теории графов. Классическими учебниками по теории графов являютсякииги [18] и [28]. Первая является библиографической редкостью, а последняямонография переиздавалась в пашей стране и является образцовой по глубинеи широте охвата материала и одновременно по ясности и лаконичности изложения. Терминология и обозначения книги [28] взяты за основу в данном учебнике.Книга [28], хотя и имеет сравнительно небольшой объём, содержит большоечисло прекрасных упражнений и различные сведения справочного характера.В меньшей степени в пей представлены программистские аспекты теории графов.Существуют и другие доступные учебники по теории графов: [5] и [25].
Последняя книга доступна даже неподготовленному читателю, имеет небольшой объём,по в то же время вполне достаточна для первоначального знакомства. Разделы,посвящёпные теории графов, как правило, присутствуют во всех учебниках подискретной математике, хотя такие разделы, по естественным причинам, частоне отличаются полнотой охвата материала. Особого упоминания заслуживаюткниги [21], [4] и [20]. Содержание этих книг абсолютно точно соответствует ихназваниям и является необходимым для программиста дополнением к классическим монографиям типа [28]. Эти источники, особенно [21], в значительной мереповлияли па отбор материала для нашего учебника. Монография [20] отличается большим объёмом и энциклопедической полнотой изложения.
Единственныйв этой главе алгоритм 7.1 посит настолько общеизвестный характер, что трудноуказать его источник. Идея этого алгоритма лежит в основе огромного числа конкретных алгоритмов па графах. Как правило, она предполагается заранее известной читателю, и изложение сразу погружается в технические детали примененияобщей концепции поиска в ширину и в глубину для решения конкретной задачи.В то же время свойства алгоритма поиска, приведённые в виде следствий к теореме, обосновывающей алгоритм 7.1, хотя и являются вполне тривиальными, невсегда осознаются практическими программистами при решении задач. Именнопоэтому представляется важным предпослать обсуждению конкретных алгоритмов па графах изложение общей идеи в предельно простой и рафинированнойформе.Упражнения7.1.
Построить пример графов Gi и G2, для которых р\ = р2, qi = <72.= 62,Д1 = Д2, но G1 / G2 (кроме примера подраздела 7.1.6).7.2. Доказать, что в любом нетривиальном графе всегда существуют вершиныодинаковой степени.7.3. Задача Рамсея1.
Доказать, что среди любых 6 человек есть 3 попарно знакомых или 3 попарно незнакомых.1Франк Рамссй (1903-1930).264Глава8.Связность7.4. Рассмотрим матрицу смежности рёбер Q : array [1 ..q, 1 ..q] of 0..1, гдеr._ J 1,10,если ребро i смежно с ребром j,в противном случае.Является ли матрица смежности рёбер Q представлением в компьютере графа G(V,E)77.5. Описать в терминах теории графов отношение эквивалентности на конечноммножестве.Глава 8СвязностьВ этой главе обсуждается важное для приложений понятие связности, доказывается фундаментальная теорема — теорема Мепгера1 и рассматриваются наиболеепопулярные алгоритмы поиска кратчайших путей.8.1. Компоненты связностиВ русском языке есть как слово «компонент» мужского рода, так и слово «компонента» женского рода, оба варианта допустимы.
В современной языковой практике чаще используется слово мужского рода. Однако исторически сложилосьтак, что «компонента связности» имеет женский род, и в данном случае мыподчиняемся традиции.8.1.1. Объединение графов и компоненты связностиГраф связен тогда и только тогда, когда его нельзя представить в видеобъединения двух графов.ТЕОРЕМАДОКАЗАТЕЛЬСТВО[] От противного. Пусть k(G) = 1 и граф G состоит из двух компонент,то есть G = Gi(Vi,Ei)UG2(V2,E2),где Vi П V2 = 0 , Е\ ПЕ2 = 0, Vi ф 0 , V2 ф 0.Возьмём vi £ Vi, v2 £ V2. Тогда 3(v\,v2)(v\ e Vi h v2 £ V2). В этой цепи3 e = (a, b) (a £ Vi & b £ V2). Но тогда e 0 E\, e E2, следовательно, e 0 E.[ <*= ] От противного.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
