Kantdeksel - Edge cover
I grafteori er et kantdeksel av en graf et sett med kanter slik at hvert toppunkt i grafen faller inn i minst en kant av settet. Innen datavitenskap er det minste kantdekselproblemet problemet med å finne et kantdeksel av minste størrelse. Det er et optimaliseringsproblem som tilhører klassen dekkproblemer og kan løses i polynomisk tid .
Definisjon
Formelt en kant deksel for en graf G er et sett med kanter C slik at hver node i G er innfallende med minst en kant i C . Settet C sies å dekke hjørnene i G . Følgende figur viser eksempler på kantbelegg i to grafer.
Et minimum kantbelegg er et kantbelegg av minst mulig størrelse. Den kant som dekker tall er på størrelse med et minimalt kant dekker. Følgende figur viser eksempler på minimum kantbelegg.
Merk at figuren til høyre ikke bare er et kantdeksel, men også en matchende . Spesielt er det en perfekt tilpasning : en samsvar M hvor hver node er innfallende med nøyaktig den ene kant i M . En perfekt matching (hvis den finnes) er alltid et minimum kantbelegg.
Eksempler
- Settet med alle kanter er et kantdeksel, forutsatt at det ikke er noen grad-0 hjørner.
- Den komplette todelte grafen K m , n har kantdekningstall maks ( m , n ).
Algoritmer
Et minste kantdeksel finner du på polynomisk tid ved å finne maksimal samsvar og utvide det grådig slik at alle hjørner er dekket. I den følgende figuren er en maksimal samsvar markert med rødt; de ekstra kantene som ble lagt til for å dekke umatchede noder er merket med blått. (Figuren til høyre viser en graf der en maksimal matching er perfekt matchende . Derfor dekker den allerede alle toppunktene og det var ikke behov for ekstra kanter.)
På den annen side er det relaterte problemet med å finne et minste toppdeksel et NP-vanskelig problem.
Se også
- Vertex deksel
- Sett deksel - kantdekselproblemet er et spesielt tilfelle av settet dekkproblemet: elementene i universet er hjørner, og hvert delsett dekker nøyaktig to elementer.