Едмондсов алгоритам
From Wikipedia, the free encyclopedia
Овај чланак је о алгоритму оптималног гранања. За алгоритам максималног поклапања погледајте Алгоритам максималног упаривања.
У теорији графова, грани математике, Едмондсов алгоритам или Чу-Лиу/Едмондсов алгоритам је алгоритам за проналажење максималног или минималног оптималног гранања. Овај алгоритам је сличан проблему минималног разапињућег стабла, који се тиче неусмерених графова. Ипак, када су чворови повезани усмереним гранама са тежинским коефицијентима, алгоритам минималног разапињућег стабла се не може користити.
Алгоритам оптималног гранања су предложили независно Јенг-јин Чу (Yoeng-jin Chu) и Ценг-хонг Лиу (Tseng-hong Liu) 1965. године, а затим и Едмондс 1967. године. За проналазак путање максималне дужине, узима се грана са највећим тежинским коефицијентом и повезују се одговарајућа два чвора, затим се узима следећа грана по тежини, итд. Ако одабрана грана прави петљу, уклања се и бира се наредна грана. Проналазак путање минималне дужине се врши аналогно, одабиром гране са најмањом тежином.