Dulmage–Mendelsohn dekompozicija

U teoriji grafova, Dulmage-Mendelsohn dekompozicija je jedinstvena kompozicija bipartitivnog grafa uz poštovanje maksimalnog poklapanja po Dulmage-Mendelsohn-u.

Neka je G =(V⁺, V^-; A) bipartitivni graf sa skupom čvorova koji se sastoje od dva dela V⁺ i V^- u skupu grana A, gde su grane usmerene od V⁺ ka V^-. Za M(⊆A) označavamo

M je upareni podskup od A takav da nijedne dve grane iz M ne dele isti čvor.