| dbo:abstract
|
- 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 olyan 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, probléma. (hu)
- 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 olyan 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, probléma. (hu)
|
