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

?I2.3. Задача о ПУТЯХ натЗольшей .танш В условиях предадущвЯ задачи трабуетоя найти (if- , наибольшей .тушнн. Решить эту задачу можно, иопол^ауя алгор'.г?и §12.2. Двд этого тужпо дашны дат очитагь отрнца '1 'вльнш .гл (."-'но- }!шть на - I ) , в получанном таким образом графа найти путь наи- М9НЬГ!9Й ДЛШЩ у*» I! П0М8НЯТЬ ЭНЭК ДД1ПШ ПуТИ Ь( / О . Другой способ отыокаяия длиннейшаго пути заключаотоя D том, чтобы минимум Е равенстве ( I 2 . I ) замеюггь на MaKonf^yM, т 9. определять меа^и вершил и з уолор::я А,' = w H X I. Л; } • (12.й) Й R-'FTFJ-) Для этого алгоритм §12. i; необходиг модифицировать олод, > щим образом. Началыше значения меток варшин задать равными Ло - 0 , A t - -о о , 1 > 0 . Отыскивать дуги V i j = ( / , для которых , и заменять метки конца на норыо: A j = Яi,+'^cj , П^оцеоо изменения меток прекратить при выпол­ нении условия: Vtcj<s. Г ^ . Алгоритм отыскания путей наибольшей длиш будет коррекг- - : ним, если граф (? не содержит контуров ^ ложительной длины. §12.4. 01говдедоний паоотояний между вег,:.;.1наМ1'1 • Пусть G= ( y , X ) - г р а ф и ' i r , i l € V - проиевольные в в р - шини. Трабуетоя ч'.'-'тч расотояние между вершинами JT H U .. Понимая rpt'^ ff как симметричный орграф, можно для определения раоотояний -ti.) использовать алг01)итм §12.1, Друго!4 ал­ горитм определения ра^зотояяий можно построить на основании тоо- р е ш 5 . 2 и 60 олодотвий. Пуо'ль = X j - С р, )'--х'раф. Алгоритм решрния: 1 . Перенумеровать ае, ины г р ф а проивволькнм образом. При 0ТС;.! верпшш-' гГ и й получат накоторие Нь.шра К и ^ ( Построить матрицу омежнооти графа Д , ооотпатотпув- щую '• «бранной пуме. ации вершин. 2. Пусть <4 и-/4'', - и -я степень матрицы А . 3 . Если ( К , £ )-й элемент матрицы Av\ отличен от н у - л я , то f я. И , и процеоо закончен, В противном случае аычиожть 4 ц Д , положить М = Hf-I и перейти к п.?.. 4 . )1рй,г->лкать процеоо до тех пор, кох-да Y) > ^ , Ч1.'0 означает отоутотвие ( i T - H ) -марвфутов в rpaipe & . 7 1