Cтраница 3
Недостатки этого метода совершенно очевидны. I увеличивается) каждый элемент матрицы Рг будет состоять из все большего числа членов вплоть до некоторого критического значения Z, после которого число членов снова начнет уменьшаться. Это происходит вследствие того, что для малых значений I и для графов, обычно встречающихся на практике, число цепей длины I 1, как правило, больше, чем число цепей длины I, а для больших значений I имеет место обратная картина. Кроме того, так как длина каждого члена внутреннего произведения вершин увеличивается на единицу, когда I увеличивается на единицу, то объем памяти, необходимый для хранения матрицы Рг, растет очень быстро вплоть до максимума при некотором критическом значении I, после которого этот объем снова начинает уменьшаться. [31]
Недостатки этого метода совершенно очевидны. I увеличивается) каждый элемент матрицы Р; будет состоять из все большего числа членов вплоть до некоторого критического значения I, после которого число членов снова начнет уменьшаться. Это происходит вследствие того, что для малых значений I и для графов, обычно встречающихся на практике, число цепей длины I - - 1, как правило, больше, чем число цепей длины I, а для больших значений I имеет место обратная картина. Кроме того, так как длина каждого члена внутреннего произведения вершин увеличивается на единицу, когда I увеличивается на единицу, то объем памяти, необходимый для хранения матрицы Р (, растет очень быстро вплоть до максимума при некотором критическом значении /, после которого этот объем снова начинает уменьшаться. [32]
Вспомогательной сети равен единице. Нетрудно заметить, что увеличивающая кратная цепь, найденная на каждой итерации главного цикла процедуры MAXPSA ( см. предыдущий раздел), имеет вид одиночной увеличивающей цепи. Теперь ясно, что во вспомогательной бескон-туриой сети длины / 2 поток идет вдоль максимального множества путей длины / 2 из s в t с попарно непересекающимися множествами промежуточных вершин. Этому множеству есте-ств нным образом соответствует максимальное множество чере - ДУКщихся цепей длины / с попарно непересекающимися множествами вершин ( под максимальным мы подразумеваем такое множество, которое нельзя увеличить на дополнительную чередующуюся цепь длины / и на множество вершин, не содер-жа. [33]