<tex>V' = V \cup \{s, t\}</tex>
Обазначим Обозначим доли исходного графа как <tex>L</tex> и <tex>R</tex>. Тогда <tex>E' = {(s,u): u \in L} \cup {(u, v): u \in L, v \in R} \cup {(v, t): v \in R} </tex>
1) Будем искать путь из <tex>s</tex> в <tex>t</tex> поиском в глубину.
