В.Н. Нефедов, В.А. Осипова - Курс дискретной математики (1127083), страница 42
Текст из файла (страница 42)
При любом йъ ! выполняется реееисгео Ь.'"' = 1 аЮЬ.еЮ ... О1..<'>, еде лри йм2 опрело берется композиция й матриц, а при й ! заражение справа вырождается е Ь,Ю. Доказательство будем проводить иидукцкей по й. При й ! гпрэвеллижють утверждения 4.28 очевидпа. Предположим, что данное утверждение выполняется при некотором йъ1. Поквжсм его справедливость при й+!.
Заметим, что согласно определеиию 1ь<ээв, („В>, !а<п О выполнЯетс» Равенство 1.< ь (1 <э>О(,,а>)0 ()(!. очО( Р>) э следовательно, Ь.<"эо = 1 <э>01.,<'>, откупа, используя индуктивное предположеиие, получаем справедливость доказываемого утверждеппя. Следствие. Для любых йм), шм ! выполняется равенство 1..<э>ОЬ,< > 1 <ээю. (4.23) Из утверждения 4.28 вытекает, что задачи перечисления путей в оргрэфе В ээдзииой едины йъ2, обладавших свойством а, сводится к выиолнеиию следующих простых действий.
Составляем ыатрииу 1.,<'> (по определению). Теперь для перечисления гутей длины 2, обладаюших свойством а, достаточно вайти 1 а> = Ь,<пО1„<ч для перечисления путей длины 3, обладаюп<чх свойством а, иэхояим Ь <'> = 1.,ОЮЬ,<'> и т, а Применяя формулу (4.25),можно при больших й ускорить решсиие задачи. Так, например, можно найти Ь,и> сразу посде определения Ь,<'> по формуле Ь.<'> Ь,<'>ОЬ.<'>. Пример 4.26. Найти все простые цепи длины 3 в орграфе (), кзобрвженном на рис. 4.!9.
Воспользуемся методом латинской композвции. Последозв. 'гсльиость результатов композиции Ь„о>, (.,и> 1 е>О о>, Ь,ш = 1 <чОЬ„и> предстэвлеиз соответственно в табл. 4.3а— 4.3е, где ц — свойство марюрутоа «быть простой цепью».
>ЕУ Залегание 4.29. Прп больших и, 74, где я — количество вер-- шин в орграфе В, й — число дуг в перечисляемых путях орграфа О, прзнтнческое применение метода латнисхоб композипии оказывается затруднительным (поскольку требуется большой объем вычислений и оператнвноб паыятн ЭВМ], ыг У что накладывает ограничения на область его использования. Замечание КЗО. Кан уже отмеча- 4 лось, метод латинской композиции (при соответствующем изменении в Рче. 439 терминологии) примениы и к неорн- ентпрованным графам и даже к пронзвольяым пссвдографам (ориснтировапцыи и иеориеитнровапным).
Та Еа я ее 4М г,е Таалве 4аа е егггт тгеч т зю е 4.2.7. Эйлеравы пепи и циклы Класси гесиай е теории графов является следующая эалача. В городе Кенигсберге имеется два острова, соединенных семью ностаии с берегвмн реки Преголь и друг с другом так, каи показано иа рвс. 4.20. Задача состоят в следующем: осугцествитьпро- гве тулку по городу такнм образом, чтобы, прсцдя по одному разу по казщому мосту, верпутьсн обратно. Решение этой задачи сводятся к нахождению некоторого специального маршрута в графе.
Пусть 6 — псевдограф. Бспь (цякл) в 6 называется эллероегй (эялероаил), если она (он) проходпт по оцному разу через каждое ребро псевлографа 6. Псставнм е соответствне схеме, прнведснной на рнс.'4.20, мультнграф 6, нзображенный на рнс. 4.21, в котором каждой частя суши соответствует вершнна, а каждому мосту — ребро, соединяющее сгютветствующяе вершины. На языке теория графов задача звучит сксдующнм образом: найти адлеров ннкл в мультнграфе 6 (решение эюд зада ~гг было дано Л. Эйлером н будет ярнведена в прпмере 4.26).
Очевидно, что свойство маршрутов а: чпроходпгь через каждое ребро не более одного раза» являатся латинским, а слеаовательно, все зблеровы цепи н циклы псевдографа 6 можно иолучнть, применяя к 0 метод латннсксй компознцнн. Онн будут ве. речнслсны в матраце 2 г г(0), где ш т(С) — «олячестао ре. бер з С. Прн этом все эйлероаы циклы псевдографа 6 полностью перечисляются в любом диагональном элементе этой матрицы.
Прежде чем решать задачу о выделеннн эйлеровой цепн нлн эйлсропа никла в псевдографе 6, надовыясншь, существуют лн оня. Простейшее необходимое условие як существования, очеандно, заключается в связности С. Исчерпывающий ответ на вопрос об пх существованнн дают прнаодямые ннжс теоремы 4д н 4.2.
Нам понадобятся слсауюоие вспомогательное угвержденве. Утверждсинс 4.29. Если е лсездозрофе 6 кмгегсл хил бы едко ребро н огсртстеуют эшхчке вершины, го С содсрпгиг «огя бы одпл простой цикл. Еслп в 6 имеется хотя бы одна петля х (о, с), то простым шкьчом является скг. Пусть теперь в 0 нет петель, т. е 0— мультнграф. Еслн а 6 кмшоюя кратные ребра х~ (с, ш), хг (ш ю), то простым цннлом является ох,шх,о. Пусть теперь в 0 нет кратных ребер, т. е. 6 — граф, я сь о» вЂ” прошвольные смежныс вершины в 6 (онн найлугся, так как по условиям до. казываемого утверждения в 6 имеется ребро).
Рассмотрнм по. гза сзедоваттльнссть оь оь оз, ... вершин графа С такую, что для любого 1мй вергпнны оь о, смежны н огчьо~ з (см. Рнс, 4.22) Поскольку в С ввсячвк вершин нет, то такую лослсловатваь ность можно продолжать неограниченна Испоаьзуя конечность мгюжествэ вершин в С, получаем, что обязательно произойдет совпадение ог = оь где 1ж1() — 2. ПУсть это бУдет псРвое сов. падение, т. е. совпадение с нанменьшнм номером 2 Тогда о,вшь. г,— простой цннл в С.
Замечание 4.3!. Доказательство щ цгг представляет собой алгоритм выделенна простого цпнла вв псевдо- графа С с непустмм множеством ребер н без висячих вершим. Введем следующие обозначения. Еплп Мь рэ — цнк.чы некоторого псевдографа С, нмеющне хотя бы одну общую вершину н не имеющие общих ребер, то, очевидно, существует цнкл, проходшцнй через ш:е ребра, входящие в р, н рь Обозначим черш р~ 4. Рт любой нз таких цнквов.
Кроме того, для любого цикла р обозначим через У(р), Х(р) множества вершин н Ребер. вколящнх ъ р. Утверждснне 4.30. Пуста р — цикл беэ петела. Тогда Уощ щу(р) количество ребер е Х(р), ппг(эденгкмх о, четко. Пусть ош У(р). Поскольку в цнкае р отсутствуют петли в все ребра попарно разлнчны (по определению), то с кажцым попым вхождением в р вершины и а этот пнкл войлут также дна новых пнцндснтных ей ребра, а следовательно, общее число ребер в Х(р) ннпндентных о, четно. Следствие. Если вершнна входнт в некоторый цнкз, то опа нс может быть висячей.
Теперь докажем, что справедлива Теорема 4.1. Для юео чтобы сеазкмд лсевдогроф С облодае эа.геровьглг цнкаом, иеабходило и достаточно, чг бы стгвенп езо вершок была чстнмлн. Леобхсдллосгм Пусть С облалает эйлеровым цнклом. Панажем, что степенв его вершин четвы. Удаляв нз С асс петли. В результате шжучнм мультнграф С', который, очевидно, также облаласг зйлеровым пнклом. Поскольку эйлеров цкнл мультнграфа С' содержит все ребра нз С; а следовательно, п все вер.
шины кз С', то в силу утверждения 4.30 степени всех вершка мультпграфа 6" четны, откуда, учитывая то, что вклад ветлы в степень вершнны, ннцндентвой втой петле, равен 2 (см. замечание 4.1), получаем четносгь степеней всех вершин нз С. Достаточность будем доназывать индукцнсй по ш — копнче ству ребер в С. Прк ш=1 связный псеадограф С с вершняамн четной степенн ьюжет аыглялеть только сшлуюпшм образоыГ С (У, Х), где )'= (о), Х (х (о, в)), а в таком псевдо.
графе существует эйлеров цикл. Предположим, по для некого. ЭЮ рого целого тж2 достаточкость доказана для всякага посада графа с жю — 1 ребрами. Докажем ее справедливость для поев. дографоп с ю ребраии. Пусть в связном псевдаграфе 6 си реб. рами степени вершин четиы. Покажем, что в нем существует эйлеров цикл.
В силу утверждения 4.29 в 0 имеется простой цикл иь Если иг содержит все ребре из 6, то искомый эйлеров. цинл найден. В противном случае удаляем из 0 все ребра, содержащиеся в из. В результате получаем псевдограф б', каждая компонента связности которого является либо взоляровапиой вер. шиной,либо псседографом, степень каждой вершины которого четка (см. утверждение 420). Пусть бь 1 1, ..., р, — компоненты связности асевдографа 6', отличные от изолированных вершин.
По индуктивному предположению иля каждого псевдаграфа 6! можно построить эйлеров цикл иь В силу связиооги б цикл рз имеет общие вершины с любым из циклов и!, ! 1, ..., р. Но тогда искомым эйлерааым циклом в 6, очевидно, является цикл и = (- ((ио+ р]+ из) +- +уо). Теорема 4.2. Для того чтобы сзюлыя пггедогрэф б обладал эйлгрооой цепью, необходима и достаточно, чтобы оя имел розно две оершияы чечеткой гтелечи. Необходимость. 1(усть 6 имеет эйлерову пепь, соединяющую о, щ Добавим к 6 дополнительное ребро (», ю), В результате получим асеадогрвф 6', обладающий эйлеровмм циклом, а следовательно (см. теорему 4.1), степени вершин вссвдографа.б' четки.
Но тогда четны и степени вершин псевдографа 6, за исключением вершин и, ю. Достаточность. Пусть б имеет ровно дие вершины от ю нечетной степени. Добавим и 6 ионов ребро (о, ю). В результате получим связный псевдограф 0' со всеми вершннамн четной степени. Но тогда в 6' существует эйлеров цикл (см. теорему 4.1). Исключив из этого цикла ребра (о, ю), получны эйлерову нпь в псевдогрзфе О, соелиняющую о, ю. Замечание 4.32. Из доказательства теоремы 4.2 слсмует, что если мы находимся в условиях этой теоремы, то юобаа эйлерова цепь псевдографа б соединяет вершины нечетной етеиснц Таким образом, мы имеем легко проверяемые необходимые и зостаточиые условие существования в произвольном псевдогра.
фе О эйлеровой деки илн эйлерова цикла, Рассмотрим теперь задачу построения реализуемых на ЭВМ алгоритмов выделения эйлероаой цепи «ли эйлерова никла в есевдографе б. для построения и обоснования таких алгаритиеа нам потребуется Утверждение 4.31.Пусть 0 (У, Х) — сояэямй псеодгмроф, П!. -., дг — циклы о 0 такие, что 1)) и Х(!и)Ц ЦХ(1и)=Х, Х(и!)ПХ(и!)=И при (чь() (420) ц-!вш за! т. е. Хйм), ..., Х(р6 — ризбиекяе множества Х.
Тогда для цик. ла р~ найдется цикл рь где гчи1, такой, что у(р~)ПУ(р,) чьИ. Рассмотрим произвольные вершины о, ш такие, что ишУ[р,). шщУ(р,). Если ющр(р,), то 1 2. Пусть теперь инййУ(рг), Тиг. да о чью, и е силу связности С найдется маршрут о~к~из ... ...кз-гие, где 2~2, и,=и, из=ш, соединяюпнп и, ю. пусть !— номер такой, что !к!мй — 1, игшУ(р,), ог ~ШУ(Ь) (номер 1 найдется, так как и~шУ(~ц), изщу(р~)). Тогда для ребра хт = (ит, отсД иысен «тШХ(р,), а следовательно, в силу (4.26) В!ш сп(2, ..., !):хтепХ(рд. Но тогда и,шу(Р~)ПУ(Р). т.е.УтвеРждеине полностью доказано.
Алгоритм 4.5 выделеняя зйлеровз никла а связном мульти. графе 6 = (У. Х), где ХчьИ, с четнымп степенями вершине Шаг 1. Выделим из 6 цикл р~ (в силу утаерждеиня 4.29 цика р, найдется, так кик ХтьИ и а 6 отсутствуют висячие вершины) Палагаеи 1=1, 6' 6. Шаг 2. Удаляем из 6' ребра, принадлежащие множеству Х(р~).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
