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

крещенной 1$01»10й эациой маршрута, указывая только верпинн или только ребра. Сокра!дан1ще формы привеленного маршрута имэют вид : ! (tr, , iTt, irj ЕЛЙ (зс,, ХД, . I 'LH будем в основном ПОЛЬ-, аоватьоя перзкм из этих опособов сокращенной зашей маршрутов. ' Боли концы маршрута совпадают, то маршрут называется замк­ нутым, в противном случав маршрут наь^ладгся разомкщ'тым. В дальнейкам, говоря "шрирут", будем иметь в виду разомкнутый шряЕут. Длиной маршрута называатся чнило ребер в нам. Если н„.<оторый маршрут, то его дагана обозначается через 1Х(у<)1 - Заметим, что мартрут это не подграф графа, т . к . в нем о у - 1;,^та0нную роль играет порядок прохождения вершин и реоср; од­ на и та же вортина или ребро ыожот встречаться (входить) в мар­ шруте несколько p a j . При вычислании длины маршрута каадое ребро учитывается отолько pa s , сколько раз оно вотрэте «'"!Я в маршруте,' Цепью называется мар-'-^т, в которо:! эао peo j » разные. Map-' шрут, в котором вое вершаны 1яанне (а следовательно, и р е бр а ) называется простой цепью. Замкнутая цепь называется диклом, замкнутая прсотая ц е п ь - i П|юстнм циклом. В простом цикле вое Е1.ршиш разные, кроме кон­ цевых. &ту oroBopty в дальнейшем будем опуоаать. Очевидно, чтс воли граф G не пуотой, то в нем имеется бесконечное число маршрутов. Длнна любой цепи не превосходит ^ихлв ребер графа Поэтому число цепей в графа - конечно. Ллика любой проотсй цепи кв превосходит чиола />-( ( f - i V i f f ) ! ) , а длина любого простого цикла не превосходит числа f> . Следо­ вательно , числа простых це? Й и простых циклов в г р ^ е К' "е-чты. В графа <? на рио.3.1 маршрутами или замкнутыми маршдута- т являются ЕооледоБатвльисоти; = JS.Щ ) ; одадоввтвльно, и цепью),- т . к . в нем повторязотоя, в частности, вершвдв и ребро ,f ;f X ( / O l ' в ; tTso.s.i S^eobyf/ — ) - ^iapшpyт , не явлчгощийоя простой цепью ( а 18