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

Равакство (3.1) позволяет построить алгоритм отыокашгя об­ ластей доотижимооти вершин графа о помощью выполнения операций объединения МНОУ^ОТВ ДО тех пор, когда "текущее" множаотво пе­ рестанет меняться при очередной операции объединения. Информацию о доотишшоотя вершин удобно представлять в ви­ де матрицы доот , .гамостей R , элементы которой определяюгоя так: _ 1 I , если I О, воли Uj ^ HCtTe). Множеством контрдоотигишооти (обратной ^^остяжимооти) вер- шини iT орграфа называется множество воршин Q.CV) т акое,что V € , I . e . I t доотикима из й)" . Раосматриваетоя также матрица контрцоотижимоотей Q. ~( ^ . п ) : „ _ f I , если r c i T/ j (или ) y i t - i • <• (3.3) 0 0 , в противном случае. По аналогии о равенством (3,1) можно заттиоать равенство Q,cv)'^itr}(jr (ir)uf\ir)U.,.UГ ^(1г), (3.4) где Г '(1г) - множество прообразов верпганы г Г ; Г ' ( , г ) = Г и т . д . ; |> - некоторое конечное целое чиоло. Из определений (3,2) и (3.3) видно, что Vi ^-В. столбец матрицы О, совпадает о ^^-й'строкой матрицы ft. , t.9,(5=R''' . Здесь индекс Т обозначает операцию транспонирования матриц. Из определений R((r) я Q.(v) следует, что множество fttir)!! f ) A i b r ) оодержит т е и только те вершны Г1Мфа, каждая из которыг, принадлежит хотя бы одному ( )-пути. • Удаление вершин U' ФdCv) не влияет на пути от ж ИУ . Иногда раооматривают мне эотва и матрицы ограниченных до- отияимоотей и контрдостижимоотей, когда требуется, чтобы длины рпооматривав?лых путей не цревшпали заданного числа, Дта нахож­ дения множеств и матриц ограниченной доотикимооти или контрдооти- лшмооти можно польэож;:'ься .соотношениями ( 3 , 1 ) , (3 . 4 ) , положив р равным верхней границе дайн допустимых путай. Данные опреде­ ления Достижимости к контрдоотижимости можно перенести на неори­ ентированные графа, учитывая возможность их прадртавления в вида симметричных орграфов, • Прямо из определений следует утверждение: Дамма 3 . I I . Орграф^=(V,PJ оильно овязный тогда и только тогда, когда M v e V 27