Párosítás-kizárási szám
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.[1] 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.[2]
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.[2] 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.[3][4]
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.[5]
Kapcsolódó fogalmak
szerkesztésAz 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).[6]
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
szerkesztés- Ez a szócikk részben vagy egészben a Matching preclusion című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.
Jegyzetek
szerkesztés- ↑ Brigham, Robert C.; Harary, Frank & Violin, Elizabeth C. et al. (2005), "Perfect-matching preclusion", Congressus Numerantium (Utilitas Mathematica Publishing, Inc.) 174: 185–192.
- ↑ a b Cheng, Eddie & Lipták, László (2007), "Matching preclusion for some interconnection networks", Networks 50 (2): 173–180, DOI 10.1002/net.20187.
- ↑ Cheng, Eddie; Lesniak, Linda & Lipman, Marc J. et al. (2009), "Conditional matching preclusion sets", Information Sciences 179 (8): 1092–1101, DOI 10.1016/j.ins.2008.10.029.
- ↑ Park, Jung-Heum & Son, Sang Hyuk (2009), "Conditional matching preclusion for hypercube-like interconnection networks", Theoretical Computer Science 410 (27-29): 2632–2640, DOI 10.1016/j.tcs.2009.02.041.
- ↑ Dourado, Mitre Costa; Meierling, Dirk & Penso, Lucia D. et al. (2015), "Robust recoverable perfect matchings", Networks 66 (3): 210–213, DOI 10.1002/net.21624.
- ↑ Mao, Yaping; Wang, Zhao & Cheng, Eddie et al. (2018), "Strong matching preclusion number of graphs", Theoretical Computer Science 713: 11–20, DOI 10.1016/j.tcs.2017.12.035.