AOP_Tom1 (1021736), страница 106

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 106)

Ориентированный цикл (ог1еп1ед сдс(е) — это простой ориентированный путь от некоторой вершины до нее самой. (Ориентированный цикл может иметь длину 1 или 2, хотя такие короткие циклы были исключены из определения цикла в предыдущем разделе. Может ли читатель объяснить, зачем зто было нужно?) Для демонстрации данных определений рассмотрим рис. 31 из предыдущего раздела. Блок г ярлыком «дв является вершиной со степенью входа 2 (в нее входят две дуги егв, егг) и степенью выхода 1. Последовательность (егь егэ, енм егг) является ориентированным путем длины 4 от вершины д до вершины Р.

Однако этот путь не является простым, например, потому что ш11(глэ) = Т = 1п[1(егг). Такая схема не содержит ни одного ориентированною цикла длины 1, но (е)г, еш) является ориентированным циклом длины 2. Ориентированный граф называется строго связным (г1гопд(д соппесгед), если существует ориентированный путь от вершины Г до вершины Г' для любых двух а) каждая вершина 1' ф В является начальной вершиной в точности одной дуги, которая обозначается как е[1']; А е[р! (В) Ь) В не является начальной вершиной ни одной из дуг; с) В является корнем в указанном выше смысле (т. е. для С каждой вершины Г ф В существует ориентированный путь от Р к В).

С В Отсюда немедленно следует, что для каждой вершины 'г'р В существует единсгпвеннмй ориентированный путь Рис. 34. Ориентиот Г к В, а значит, ориентированных циклов не суще- рованное дерево. ствует. Легко видеть, что предыдущее определение ориентированного дерева (приведенное в начале раздела 2.3), не противоречит новому определению только в том случае, когда имеется конечное множество вершин.

При этом вершины отвечают узлам, а дуга е[К] — это связь между 1' и РАЯЕМТ(г') . Соответствующий ориентированному дереву (неориентировишый) граф является связным вследствие свойства (с). Более того, он не имеет циклов. Действительно, если (1а, Ры..., 'г'„) является неориептированным циклом с и > 3 и если е[\'1] — это ребро между 1'а и 1'ы то е[Гз] — это ребро между 111 и Ъг и аналогично е[Ъь] — это ребро между гь ~ и Ъь для 1 ( А ( и, что противоречит отсутствию ориентированных циклов. Если ребро между го и 1; не равно е[1'1], то оно должно быть равно е[га]. Тот же аргумент относится к циклу (1ы ~0~ 1а-ы" 111) вершин К р Г'. Он является корневым (гоо1ед), если существует хотя бы один корень (гоаб), т.

е. по крайней мере одна такая вершина В, прн наличии которой существует ориентированный путь от Г к.В для всех г' р' В. "Строго связный" граф всегда является "корневым", но обратное утверждение не верно. Блок-схема, показанная на рис. 31 в предыдущем разделе, является примером корневого диграфа (т. е. корневого ориентированною графа), корень В которого соответствует вершине-блоку "Начало". Причем, добавляя дугу от блока "Конец" до блока "Начало" (см. рис. 32), получим строго связный граф.

Каждый ориентированный граф С, очевидно, соответствует обыкновенному графу Са, если игнорировать ориентации и исключить двойные ребра или циклы. Формально выражаясь, граф Со содержит ребро от вершины 1' до вершины Г тогда и только тогда, когда г' ф Г' и граф С имеет дугу от вершины Г до вершины Г или от вершины Ъ ' до вершины г'. Рассматривая (неориентированные) пути и циклы в графе С, мы подразумеваем, что они являются путями и циклами графа Са. При этом граф С назовем связным, если соответствующий граф Са является связным (т. е.

рассматриваемое свойство не только "слабее" свойства "строго связный", но и еще слабее, чем свойство "корневой" ). Ориентированное дерево (ог1епсед ггее) (рис. 34), иногда называемое некоторыми авторами корневым деревом, представляет собой ориентированный граф с такой вер- я шиной В, что: так как Г„= 1о. Значит, ориентированное дерево является свободным деревом, если не учитывать направленая дуг. Следует отметить, что этот процесс можно обратить.

Если начать с такого непустого свободного дерева, как на рис. 30, то можно в качестве корня В выбрать любую вершину и задать направления для ребер. Если представить себе, что граф "подвесили" за вершину В и встряхнули, то стрелки ребер в нем будут направлены вверх. Более строгая формулировка выглядит так. Заменить ребро à — У" дугой от Г к 1х' тогда и только тогда, когда простой путь от Г к В проходит через Г', т. е, когда он имеет вид (1о, 1'~,..., 1'„), где и) О, 1ло— - Ъ; 1'1 =Ъ",Ъ'„=В, Для проверки справедливости этого построения нужно доказать, что для каждого ребра à — Рч указано направление И +- Уо (или à — ~ 1").

И это действительно легко сделать, если (г; К,,..., В) и (г', 1~',...,В) являются простыми путями, т. е. цикл существует всегда, за исключением случаев, когда 1' = г1' или 1; = 1ч. Такое построение демонстрирует, что направления дуг в ориентированном дереве полностью определяются расположением корня, а потому их можно не указывать на схемах, на которых корень обозначен явным образом. Таким образом, установлена связь между тремя типами деревьев: (упорядоченным) деревом, которое имеет принципиальное значение в компьютерных программах, как показано в начале раздела 2.3, ориентированным (или неупорядоченным) и свободным деревом.

Два последних типа деревьев также встречаются при изучении компьютерных алгоритмов, но не так часто, как первый. Основное различие между этими типолли древовидных структур заключаетпся только в обвелле струк пуриой инфорллаиии, которая считается существенной. Например, на рис. 35 показаны три дерева, которые различны, только если рассматривать их как упорядоченные деревья (с корнем вверху). А егли их рассматривать как ориентированные деревья, то идентичными являются первые два, поскольку порядок поддеревьев "слева направо" здесь не существен, Наконец, если считать деревья свободными, то все они на рис. 35 идентичны, так как корень не определен.

Рис. 35. Три древовидные структуры. Цепью Эйлера (Еи1ег1ап сггсиЫ) в ориентированном графе является такой ориентированный путь (ем ее,...,е ), что каждая дуга ориентированного графа встречается в этом пути только один раз и бп(е, ) = 1п11(е1). Она представляет собой "полный обход" дуг диграфа. (Цепь Эйлера названа в честь Леонарда Эйлера (Ьеопйагб Еп!ег), который в 1730 году рассмотрел знаменитую задачу о том, что невозможно обойти во время воскресной прогулки семь мостов Кенигсберга, посетив каждый из них в точности один раз.

Он также рассмотрел аналогичную задачу для неориентированных графов. Цепи Эйлера не следует путать с цепями Гамильтона (Наш111ошап с1гсшсв), т. е. ориентированными циклами, в которых каждая вершина встречается только один раз; см. гл. 7.) Ориентированный граф называется сбалансированнььи (ба1апсеа) (рнс. 36), если каждая вершина 1г имеет равные по величине степени входа и выхода, т. е, сколько существует ребер, для которых вершина 1' является начальной, столько же существует ребер, для которых вершина 1г является конечной. Это условие тесно связано с законом Кирхгофа (см. упр. 24).

Если ориентированный граф имеет цепь Эйлера, то очевидно, что он должен быть связным н сбалансированным, за исключением случаев, когда он имеет изолированные вершины (1за1асей иетЫссв), т. е. вершины с равными нулю степенями входа и выхода. Рнс. 36. Сбалансированный ориентированный граф.

Итак, в настоящем разделе дано довольно много определений (ориентированный граф, дуга, начальная вершина, конечная вершина, степень выхода, степень входа, ориентированный путь, простой ориентированный путь, ориентированный цикл, ориентированное дерево, цепь Эйлера, изолированная вершина, а также строгая связность, наличие корня и сбалансированность), но приведено лишь несколько связанных с ними результатов.

Теперь мы готовы приступить к изучению более сложного материала. Первым основным результатом является теорема И. Дж. Гуда 11. Л. Соос1, Х Е,опооп Магй. Яос. 21 (1947), 167 — 169), который показал, что цепи Эйлера существуют всегда, кроме случаев, когда они очевидно невозможны. Теорема С. Конечный ориентированный граф без изолированных вершил содержит цепь Эйлера тогда н только тогда, когда он связа ный и сбалансированный.

Доказательство. Предположим, что граф С сбалансирован и Р=(еы...,е ) представляет собой ориентированный путь максимально возможной длины, в котоРом ни одна дУга не пРоходитсЯ дважды. Тогда, если )г = бп(ев,) и если К— степень выхода вершины 1; то путь Р должен включать все 1с дуг е с начальной вершиной ш11(е) = И. В противном случае можно было бы добавить е и полу.чить более длинный путь.

Но если 1пй(е ) = 1г и 7' > 1, то бп(е ~) = 1'. Следовательно, твк как граф С сбалансирован, получим 1п!Ф(е~) = 1' = Йп(е ); в противном случае степень входа вершины 1г должна быть не меньше к + 1. Теперь, выполнив циклическую перестановку в Р, получим, что любая дуга е вне этого пути не имеет общих начальных и конечных вершин с любой дугой этого пути. Поэтому, если Р не является цепью Эйлера, граф С не является связным. Межлу цепями Эйлера и ориентированными деревьями существует следующая важная взаимосвязь. Лемма Е.

Характеристики

Список файлов книги