Dalmage-Mendelsohns sönderdelning i grafteorin är uppdelningen av hörnen av en tvådelad graf i delmängder med egenskapen att 2 angränsande hörn hör till samma mängd om och bara om de är tillsammans med varandra i en grafmatchning. Nedbrytningen var uppkallad efter A. L. Dalmage och Nathan Mendelsohn , som publicerade den 1958.
Låt G=(U, V, E) vara en bigraf och låt D vara en icke-tom uppsättning av hörn eller noder i G som inte motsvarar minst en största matchning av G. Då är D nödvändigtvis en oberoende mängd. Så G kan delas med 3 delar:
Varje största kombination i G består av kombinationer i den första och andra delen som matchar alla grannar till D, tillsammans med matchningen av de återstående hörnen.
Den tredje uppsättningen av hörn i den utökade sönderdelningen (eller alla hörn i en graf med perfekt matchning) kan vara ytterligare underuppsättning enligt följande:
För att se att denna delinställning kännetecknar kanterna som hör till en perfekt matchning, anta att två hörn u och v i G tillhör samma nedbrytningsdelmängd, men ännu inte har mappats till den ursprungliga perfekta matchningen. Då har H en starkt sammankopplad komponent innehållande kanten uv. Denna kant måste tillhöra en enkel cykel i H (enligt definitionen av en stark koppling) som nödvändigtvis motsvarar en variabel cykel i G (en cykel vars kanter växlar mellan matchande och icke-matchande kanter). Denna interfolierade slinga kan användas för att modifiera den initiala perfekta matchningen för att producera en ny matchning som innehåller uv-kanter.
En kant uv av en graf G tillhör alla perfekta matchningar av G om och endast om u och v är de enda medlemmarna av deras mängd i nedbrytningen. En sådan kant finns om och endast om grafen som motsvarar undantaget är lika med en.
Denna nedbrytning används för att dela gitter, i finita elementanalys, och för att bestämma givna, specifika ekvationer i system av olinjära ekvationer.