Gallai – Edmondsův rozklad - Gallai–Edmonds decomposition

v teorie grafů, Gallai – Edmondsův rozklad je rozdělení vrcholů grafu do podmnožin splňujících určité vlastnosti. Jedná se o zobecnění Dulmage – Mendelsohnův rozklad od bipartitních grafů po obecné grafy.^[1]

Nezávisle to prokázal Tibor Gallai a Jack Edmonds.

Najdete jej pomocí algoritmus květu.

Rozšíření věty o rozkladu Gallai – Edmonds na shody s více hranami je uvedeno v „Capacitated Rank-Maximal Matchings“ od Katarzyny Paluch.^[2]

Reference

^ Szabó, Jácint; Loebl, Martin; Janata, Marek (14. února 2005). „Edmonds – Gallaiův rozklad pro k-Piece Balení Problém ". Electronic Journal of Combinatorics. 12. doi:10.37236/1905. S2CID 11992200.
^ Paluch, Katarzyna (22. května 2013). Maximalizované shody s hodnocením. Algoritmy a složitost. Přednášky z informatiky. 7878. Springer, Berlín, Heidelberg. 324–335. doi:10.1007/978-3-642-38233-8_27. ISBN 978-3-642-38232-1.

Tento článek týkající se matematiky je pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.

[1] Szabó, Jácint; Loebl, Martin; Janata, Marek (14. února 2005). „Edmonds – Gallaiův rozklad pro k-Piece Balení Problém ". Electronic Journal of Combinatorics. 12. doi:10.37236/1905. S2CID 11992200.

[2] Paluch, Katarzyna (22. května 2013). Maximalizované shody s hodnocením. Algoritmy a složitost. Přednášky z informatiky. 7878. Springer, Berlín, Heidelberg. 324–335. doi:10.1007/978-3-642-38233-8_27. ISBN 978-3-642-38232-1.

[1]

[2]