A matematika, azon belül a gráfelmélet területén egy G gráf mp(G)-vel jelölt párosítás-kizárási száma (matching preclusion number) az élek minimális száma, melyek törlésével a gráf teljes párosítása vagy majdnem teljes párosítása (páratlan csúccsal rendelkező gráfban egy csúcson kívül az összeset lefedő párosítás) lehetetlenné válik.. A párosítás-kizárási szám a gráf robusztusságát méri elosztott algoritmusok olyan telekommunikációs hálózati topológiái esetén, ahol az elosztott rendszer minden csomópontjának egy szomszédos partnerrel kell kommunikálnia.
Sok gráfra igaz, hogy mp(G) megegyezik a csúcsok minimális fokszámával, mivel bármely csúcsba vezető összes él kitörlése lehetetlenné teszi annak párosítását. Az ilyen élhalmazt triviális párosítás-kizárási halmaznak (trivial matching preclusion set) nevezik.. A definíció egy változatában szereplő feltételes párosítás-kizárási szám (conditional matching preclusion number) azon élek minimális számára kérdez rá, melynek törlésével a gráfnak nem lesz teljes párosítása, majdnem teljes párosítása és izolált csúcsa sem...
Annak meghatározása, hogy adott gráf párosítás-kizárási száma adott küszöbnél kisebb-e, NP-teljes probléma..
Kapcsolódó fogalmak Az erős párosítás-kizárási szám (strong matching preclusion number), smp(G) a párosítás-kizárási szám általánosítása, amennyiben élek törlésén kívül csúcsok törlését is megengedi (azon élek/csúcsok minimális száma, melyek törlésével a gráf teljes párosítása vagy majdnem teljes párosítása lehetetlenné válik)..
Az irányítatlan gráfok éltörlési műveletével definiált egyéb számok közé tartozik az élösszefüggőség, a gráf összefüggőségének megszüntetéséhez törölni szükséges élek minimális száma, és a ciklomatikus szám, a körök felbontásához törölni szükséges élek minimális száma.
Fordítás
Jegyzetek
Kategória:Gráfinvariánsok Kategória:Párosítás