Теория графов и комбинаторика

длины без повторяищихоя вершин (кроме крайних), т . е . npoovofi цшш нечач'яйй дошпы. Умерадение юмглы 3 . 5 не справедливо дня зажнутых маршру­ тов четной длины. Читателю предлагается в качества уцражнешзя выяснить, какие из л еш 3 . 1 . ; . 3 . 5 оотаютоя справедливыми для мультиграфов и ьоевдографов. Если = ~ два маршрута, то сцепкой этих маршрутов называется маршрут Сцеяку (Зудам обозначать/*-- 'или §3.й. Машотты в OOTPafey *4 Путем в орграфе назнвается такая чере,пующаяся последовательность вершин и дуг, начинающаяся и оканчивающаяся вершинами, что любая дуга а ней исходит из дредшаотвующвй ей вершины и заходит в последующую вершину. Таким образом, если 7 f > - Щ 'Ь,то HP i T c ' V l h - Этот п у т ь ^ / называют - путем. Он соединяет вершину iTf о вершиной ™ ° *. Вершина называется началом пути, а iTv^ - кошом пути. За­ метим, что в графах (неориентиройанных) концы маршрута были равног_авны, любой иэ них можно было считать началом маршрута. Длина пути - число луг в нем, обознЕ ;а8тся 1Г(/^)1. Путь называется простым, воли все дуги в нем разине, и йлемеятарныгу!, если вое верияны рзные, Замкнутый путь ( 1 /1 = I' M ) называется кмтуром. Контур, в KOTopoi:? все дуги разные, называется простым контуром. Ксн'гур, , в ксторсм все вершны, кроме крайних, разные, называется эле­ ментарным контуром. Введенные понятия маршрутов в орграфах являются ботеотван- HL.J обобщением ооответствущих понятий для графов с учатсм ори- внтирсванности дуг. Справедливы леммы, аналогичные леммам 3 . 1 . . . 3 . 5 . ДемМа 3 . 6 . Из любого ( ^ )-11ути орграфа (. VФ VX' ) можно выделить элементарный ( V~ ii>' )-путь. Л е т а 3 . ? . Кратчайший ( l/'-'U)' )-путь (V=hit^ ) является элементарным путем. Лемма 3 . 8 . Из любого простого контура орграфа 1? можно яндалить еламёнтарный контур. Лемма 3 . 9 . Любой простой контур орграфа можно представить как объединение влементарГ'чх контуров, не имеющих общих дуг.