Методы работы с разреженными матрицами произвольного вида. Глушакова Т.Н - 25 стр.

                                     25
   Граф G = (V, E) состоит из множества V вершин u, v, ω, …и
множества E ребер, где ребром называется пара (u, v) вершин из V.
   Граф G = (V, E) называется ориентированным графом или орграфом,
когда пары его вершин, представляющие ребра, упорядочены.
   Полустепенью захода вершины v называется число ребер, заходящих в v.
   Полустепень исхода – это число ребер, исходящих из v.
   Матрица достижимостей R орграфа – это булева матрица, определяемая
следующим образом: rij = 1, если vj достижима из vi в орграфе, и rij = 0 в
противном случае.
   Орграф называют слабо связным, если связен соответствующий
неориентированный граф, получаемый удалением ориентации ребер.
   Если имеется ориентированное ребро (u → v), то говорят, что вершина v
смежна с u. Если W – подмножество вершин G, то смежное множество для
W, обозначаемое через Adj(W), – это множество вершин, не принадлежащих
W, но смежных с вершинами из W. Пусть даны G = (V, E) и WδV, тогда
                  Adj(W) = {v ∈V −W ∃u ∈W : ∃(u → v) ∈E}.

      3.1 Сильные компоненты орграфа
      Рассмотрим слабо связный орграф G = (V, E). Орграф G называют
сильно связным, если для любой пары вершин v,ω0V существует путь из v в ω
и путь из ω в v, т.е. v и ω взаимно достижимы. Поскольку путь из v в ω
вместе с путем из ω в v составляют цикл, то сильный связный орграф можно
определить и как орграф, в котором для всякой пары вершин существует
цикл, содержащий обе вершины. Матрица достижимостей сильно связного
орграфа состоит из одних единиц. В общем случае орграф G может не быть
сильно связным. Сильно связной компонентой или сильной компонентой
называется G частичный граф в G, являющийся сильно связным и не
допускающий расширения без потери этого свойства. Частичный граф
содержит все ребра G вида (v, ω), такие что обе вершины v, ω принадлежат
ему. Из определения сильной компоненты вытекает существование цикла,
которому принадлежат любые две заданные вершины компоненты. Из него
вытекает также, что любой цикл в G должен быть целиком составлен из
вершин данной сильной компоненты, либо, наоборот, целиком составлен из
вершин G, ей не принадлежащих. В самом деле, если бы существовал цикл,
содержащий вершину v сильной компоненты и вершину ω, не
принадлежащую ей, то мы могли бы добавлением ω расширить сильную
компоненту без потери сильной связности, что противоречит определению.
Это свойство используется для выделения сильных компонент: вначале в G
находят цикл, а затем насколько возможно расширяют его, исследуя другие
циклы.
    Слабо связный орграф G = (V, E) можно разбить на сильные компоненты
C1, C2,…, Cs с непересекающимися множествами вершин. Если G сам сильно
связан, то s=1, и сильная компонента только одна. В противном случае G
допускает разбиение и s>1. Ребро (v → ω) является выходом или оно исходит
из сильной компоненты C=(Vc,Ec), если v0Vc, а ω⌠ Vc. Ребро (v → ω) есть вход