Dijoin

I matematik är en dijoin en delmängd av kanterna på en riktad graf , med egenskapen att sammandragning av varje kant i dijoinen ger en starkt sammankopplad graf . På motsvarande sätt är en dijoin en delmängd av kanterna som för varje dicut inkluderar minst en kant som korsar dicuten. Här är en dicut en uppdelning av hörnen i två delmängder, så att varje kant som har en ändpunkt i båda delmängderna riktas från den första delmängden till den andra.

Woodalls gissning , ett olöst problem inom detta område, säger att i varje riktad graf är det minsta antalet kanter i en dicut (den ovägda minsta stängningen) lika med det maximala antalet disjunkta dijoins som kan hittas i grafen (en packning av dijoins) . En bråkvägd version av gissningen, ställd av Jack Edmonds och Rick Giles, vederlagdes av Alexander Schrijver .

Lucchesi -Younger-satsen säger att den minsta storleken på en dijoin, i en given riktad graf, är lika med det maximala antalet disjunkta dicuts som kan hittas i grafen. Minsta viktdijoin i en viktad graf kan hittas i polynomtid , och är ett specialfall av det submodulära flödesproblemet .

I plana grafer är dijoins och återkopplingsbåguppsättningar dubbla begrepp. Den dubbla grafen för en riktad graf, inbäddad i planet, är en graf med en vertex för varje yta av den givna grafen, och en dubbelkant mellan två dubbla hörn när de motsvarande två ytorna är åtskilda av en kant. Varje dubbelkant korsar en av de ursprungliga grafkanterna, vriden 90° medurs. En återkopplingsbågeuppsättning är en delmängd av kanterna som inkluderar minst en kant från varje riktad cykel. För en dijoin i den givna grafen bildar motsvarande uppsättning kanter ett riktat snitt i den dubbla grafen och vice versa. Detta förhållande mellan dessa två problem gör att återkopplingsbåguppsättningsproblemet kan lösas effektivt för plana grafer, även om det är NP-svårt för andra typer av grafer.