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

ШВА 12. raCOTOHJE ЗАДАЧИ И AHTOBfl'iMU В данной главе приводятоя форлудировки некоторых iiaudoju/i? чаото вотрочающихоя в прилокениях задач таории грнфов и даютя алгоритмы их ред; iiuH, За обоонованидали алгортмов отоилааг чи­ тателя к литературе, omiooK которой приведен в конце пособия, §12.1. Задача о ггутях с наименьшим чнолом ДУГ Пуоть G- = СЦ Г ) - щйизвольный орграфи^1(^6 V" - вершинн. Требуетоя найти (^^-ч'')-путь , имащий наименьшее чиоло .пуг. Алгоритм решения: ^ , I . Присвоить вершине метку О . 2. Пуоть AOn),<n=0ji,, „ - . ножеотво яершин, имеющих меткут , Варшшам шюжеотва , _ ^ п , / л , i присвоить метку Wf-I . Еоли на наком-то шаге мпожаотно Д См+О пусто и вершина 'Ш' не получила метки, то в (г не сущеотвует (IR-K^J-NYTH. 3. Процеоо приовоения меток продолжать до тех пор, когда рергана получит пакоторую матку И t . e . 1*^& АС^} • 4 . Определишь пооледовательнооть вершин'VI,,4^2^ таких, ITI, Е Д ( П Н ) 8: И ; - Е , Г № ^ ) ; Е Д ( И - ; 1 ) ^ Г > - ^ , , Е Г С 1 Г Д ; 5. nyTbyWs:ftrsir £^,'^L,j.,,Mij4i?') является иокошм. Легко аамб" гать, что :летка каждой вершинн 0 " jaBHa наименьшему .чиолу м , •здя KODopol'Q сущеотвует (V~'U^)- путь, оодержащий т дуг. За­ метим чйкже, что пооле раоотаяовкя воех возможных меток вершин можмо определить( i O ~ }~пути о наименьшим числом дуг для зшвой аерши. дa t , вола они оущеотвуют. JIG »:?.», & ш т . M W M 9 H I ' M G L A S A M Пуоть •<? дрГ1)аф4 каждой дуге •= (Vj,, ) , ooe- дйшшцай вершину F,; о вершиной , ирипиоано число Д ' ; > 0 , называемое длиной пути, Еоли/ i - дуть s графе & , то даганой вутиуУ вайы1аавтоя ч-аоло ~ данов сумме длин дуг, входящих в 69