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.

Spoljašnje veze[уреди]