Matchande preklusion

I grafteorin , en gren av matematiken, är det matchande preklusionsnumret för en graf G (betecknad mp( G )) det minsta antalet kanter vars radering resulterar i att en perfekt matchning eller nästan perfekt matchning förstörs (en matchning som täcker alla utom ett hörn i en graf med ett udda antal hörn). Matchningspreclusion mäter robustheten hos en graf som en kommunikationsnätstopologi för distribuerade algoritmer som kräver att varje nod i det distribuerade systemet matchas med en angränsande partnernod.

I många grafer är mp( G ) lika med den lägsta graden av någon vertex i grafen, eftersom borttagning av alla kanter som faller in på en enda vertex förhindrar att den matchas. Denna uppsättning kanter kallas en trivial matchande preclusionsuppsättning. En variantdefinition, preklusionsnumret för villkorad matchning , frågar efter det minsta antalet kanter vars radering resulterar i en graf som varken har en perfekt eller nästan perfekt matchning eller några isolerade hörn.

Det är NP-komplett att testa om det matchande preklusionsnumret för en given graf ligger under en given tröskel.

Det starka matchande preklusionsnumret (eller helt enkelt SMP-numret) är en generalisering av det matchande preklusionsnumret; SMP-numret för en graf G , smp( G ) är det minsta antalet hörn och/eller kanter vars radering resulterar i en graf som varken har perfekta eller nästan perfekta matchningar.

Andra siffror som definieras på liknande sätt genom kantradering i en oriktad graf inkluderar kantanslutningen , det minsta antalet kanter som ska raderas för att koppla bort grafen och det cyklomatiska antalet , det minsta antalet kanter som ska raderas för att eliminera alla cykler.