Vertex cykelskydd

I matematik är ett vertexcykelomslag (vanligtvis kallat helt enkelt cykelomslag ) av en graf G en uppsättning cykler som är subgrafer av G och innehåller alla hörn av G .

Om lockets cykler inte har några hörn gemensamma kallas locket vertex-disjunkt eller ibland helt enkelt disjoint cycle cover . Detta är ibland känt som exakt vertex cycle cover. I detta fall utgör uppsättningen av cyklerna en spännande subgraf av G. En osammanhängande cykel täckning av en oriktad graf (om den finns) kan hittas i polynomtid genom att omvandla problemet till ett problem att hitta en perfekt matchning i en större graf.

Om kåpans cykler inte har några gemensamma kanter kallas kåpan kant-disjunkt eller helt enkelt disjoint cycle cover .

Liknande definitioner finns för digrafer , i termer av riktade cykler. Att hitta en vertex-disjunkt cykeltäckning av en riktad graf kan också utföras i polynomtid genom en liknande reduktion till perfekt matchning . Men att lägga till villkoret att varje cykel ska ha en längd på minst 3 gör problemet NP-svårt .

Egenskaper och applikationer

Permanent

Permanenten för en (0,1)-matris är lika med antalet av hörn-disjunkande cykelöverdrag för en riktad graf med denna närliggande matris . Detta faktum används i ett förenklat bevis som visar att beräkningen av permanenten är #P-komplett .

Minimalt osammanhängande cykelskydd

Problemen med att hitta ett topp- och kantdisjunkt cykelöverdrag med minimalt antal cykler är NP-kompletta . Problemen är inte i komplexitetsklassen APX . Varianterna för digrafer finns inte heller i APX.

Se även

• Edge cycle cover , en samling cykler som täcker alla kanter av G