Lucchesi–Yngre teorem

I matematiken för riktade grafer är Lucchesi –Younger-satsen ett förhållande mellan dicuts och dijoins . Den publicerades av Cláudio L. Lucchesi och Daniel H. Younger 1978. Deras bevis löste en gissning som hade framställts ungefär ett decennium tidigare av Younger, och i opublicerat arbete av Neil Robertson, motiverat av dualiteten i plana grafer mellan dijoins och återkopplingsbågeuppsättningar .

En dicut är en partition av hörnen i två delmängder så att alla kanter som korsar partitionen gör det i samma riktning. En dijoin är en delmängd av kanter som, när de dras samman, ger en starkt sammankopplad graf ; på motsvarande sätt är det en delmängd av kanter som inkluderar minst en kant från varje dicut.

Om en samling av dicuts alla är osammanhängande, måste alla dijoin ha minst en kant från var och en av dessa dicuts, och måste ha en storlek som är minst lika med storleken på samlingen. Därför måste det maximala antalet disjunkta dicuts i en graf vara mindre än eller lika med minimistorleken för en dicut. Lucchesi–Younger-satsen säger att detta förhållande alltid är en likhet. Den minsta storleken på en dijoin är lika med det maximala antalet disjunkta dicuts som kan hittas i en given graf.