Kryt hrany - Edge cover - Wikipedia

v teorie grafů, an okrajový kryt a graf je sada hrany takové, že každý vrchol grafu dopadá alespoň na jeden okraj sady. v počítačová věda, minimální problém s krytem hrany je problém najít okrajový kryt minimální velikosti. Je to optimalizační problém která patří do třídy pokrývající problémy a lze je vyřešit v polynomiální čas.

Definice

Formálně okrajová obálka grafu G je sada hran C tak, aby každý vrchol v G je incident s alespoň jednou hranou v C. Sada C říká se Pokrýt vrcholy G. Následující obrázek ukazuje příklady krytů hran ve dvou grafech.

A minimální krytí hran je krycí hrana nejmenší možné velikosti. The číslo pokrývající hranu ${ displaystyle rho (G)}$ je velikost minimálního pokrytí hrany. Následující obrázek ukazuje příklady minimálního pokrytí hran.

Všimněte si, že obrázek vpravo není jen okrajový kryt, ale také a vhodný. Jedná se zejména o perfektní shoda: shoda M ve kterém každý vrchol dopadá s přesně jednou hranou dovnitř M. Dokonalé přizpůsobení (pokud existuje) je vždy minimální krytí hran.

Příklady

Sada všech hran je krytem hran, za předpokladu, že neexistují žádné vrcholy stupně 0.
The kompletní bipartitní graf K._m,n má maximální počet krycích hran (m, n).

Algoritmy

Nejmenší okrajový kryt najdete v polynomiální čas vyhledáním a maximální shoda a chamtivě ji rozšiřovat tak, aby byly pokryty všechny vrcholy.^[1]^[2] Na následujícím obrázku je maximální shoda označena červeně; další hrany, které byly přidány k pokrytí nepřizpůsobených uzlů, jsou označeny modře. (Obrázek vpravo ukazuje graf, ve kterém je maximální shoda a perfektní shoda; proto již pokrývá všechny vrcholy a nebyly potřeba žádné další hrany.)

Na druhé straně související problém najít nejmenší vrcholový kryt je NP-tvrdé problém.^[1]

Viz také

Vrcholový kryt
Nastavit kryt - problém s okrajovým krytem je zvláštním případem problému s nastaveným krytem: prvky vesmír jsou vrcholy a každý podmnožina pokrývá přesně dva prvky.

Poznámky

^ ^A ^b Garey & Johnson (1979), str. 79, používá okrajový kryt a vrcholový kryt jako jeden příklad dvojice podobných problémů, z nichž jeden může být vyřešen v polynomiálním čase, zatímco druhý je NP-tvrdý. Viz také str. 190.
^ Lawler, Eugene L. (2001), Kombinatorická optimalizace: sítě a matroidy, Dover Publications, s. 222–223, ISBN 978-0-486-41453-9.

Reference

Weisstein, Eric W. "Edge Cover". MathWorld.
Garey, Michael R.; Johnson, David S. (1979), Počítače a neodolatelnost: Průvodce po teorii NP-úplnosti, W.H. Freemane, ISBN 0-7167-1045-5.

[gt79-1] A ^b Garey & Johnson (1979), str. 79, používá okrajový kryt a vrcholový kryt jako jeden příklad dvojice podobných problémů, z nichž jeden může být vyřešen v polynomiálním čase, zatímco druhý je NP-tvrdý. Viz také str. 190.

[2] Lawler, Eugene L. (2001), Kombinatorická optimalizace: sítě a matroidy, Dover Publications, s. 222–223, ISBN 978-0-486-41453-9.

[1]

[2]