Odpovídající vyloučení - Matching preclusion

v teorie grafů, obor matematiky, odpovídající číslo vyloučení grafu G (označeno mp (G)) je minimální počet hran, jejichž odstranění má za následek zničení a perfektní shoda nebo téměř dokonalá shoda (shoda, která pokrývá všechny vrcholy v grafu kromě jednoho s lichým počtem vrcholů).[1] Odpovídající prekluze měří robustnost grafu jako a komunikační síť topologie pro distribuované algoritmy které vyžadují, aby každý uzel distribuovaného systému byl spárován se sousedním partnerským uzlem.[2]

V mnoha grafech mp (G) se rovná minimu stupeň jakéhokoli vrcholu v grafu, protože smazání všech hran dopadajících na jeden vrchol znemožňuje jeho shodu. Tato sada hran se nazývá triviální shodná sada vyloučení.[2] Varianta definice, číslo vyloučení podmíněné shody, požaduje minimální počet hran, jejichž smazání má za následek graf, který nemá ani dokonalé nebo téměř dokonalé shody, ani žádné izolované vrcholy.[3][4]

to je NP-kompletní otestovat, zda je shodné číslo vyloučení daného grafu pod danou prahovou hodnotou.[5]

Silné odpovídající číslo vyloučení (nebo jednoduše číslo SMP) je zobecněním odpovídajícího čísla vyloučení; číslo SMP grafu G, smp (G) je minimální počet vrcholů a / nebo hran, jejichž odstranění má za následek graf, který nemá ani dokonalé shody, ani téměř dokonalé shody.[6]

Další čísla definovaná podobným způsobem odstraněním hrany v neorientovaném grafu zahrnují okrajová konektivita, minimální počet hran, které se mají odstranit za účelem odpojení grafu, a cyklomatické číslo, minimální počet hran, které se mají odstranit, aby se vyloučily všechny cykly.

Reference

  1. ^ Brigham, Robert C .; Harary, Franku; Housle, Elizabeth C .; Yellen, Jay (2005), „Dokonale sladěná prekluze“, Congressus Numerantium, Utilitas Mathematica Publishing, Inc., 174: 185–192.
  2. ^ A b Cheng, Eddie; Lipták, László (2007), „Porovnávací vyloučení pro některé propojovací sítě“, Sítě, 50 (2): 173–180, doi:10.1002 / net.20187.
  3. ^ Cheng, Eddie; Lesniak, Linda; Lipman, Marc J .; Lipták, László (2009), „Podmíněné párování sad vyloučení“, Informační vědy, 179 (8): 1092–1101, doi:10.1016 / j.ins.2008.10.029.
  4. ^ Park, Jung-Heum; Son, Sang Hyuk (2009), „Podmíněná shoda vyloučení pro propojovací sítě podobné hyperkrychlím“, Teoretická informatika, 410 (27–29): 2632–2640, doi:10.1016 / j.tcs.2009.02.041.
  5. ^ Dourado, Mitre Costa; Meierling, Dirk; Penso, Lucia D .; Rautenbach, Dieter; Protti, Fabio; de Almeida, Aline Ribeiro (2015), „Robustní obnovitelné perfektní párování“, Sítě, 66 (3): 210–213, doi:10,1002 / net.21624.
  6. ^ Mao, Yaping; Wang, Zhao; Cheng, Eddie; Melekian, Christopher (2018), „Strong matching matching preclusion number of graphs“, Teoretická informatika, 713: 11–20, doi:10.1016 / j.tcs.2017.12.035.