Kantcykelskydd
Inom matematik är ett kantcykelomslag (ibland kallat helt enkelt cykelomslag ) av en graf en familj av cykler som är subgrafer av G och innehåller alla kanter av G.
Om lockets cykler inte har några hörn gemensamma kallas locket vertex-disjunkt eller ibland helt enkelt disjoint cycle cover . I detta fall utgör uppsättningen av cyklerna en spännande subgraf av G.
Om kåpans cykler inte har några gemensamma kanter, kallas locket kant-disjunkt eller helt enkelt disjoint cycle cover .
Egenskaper och applikationer
Cykelskydd för minimivikt
För en viktad graf är MWCCP-problemet (Minimum-Weight Cycle Cover Problem) problemet med att hitta ett cykelskydd med minimal summa av vikter av kanter i alla cykler av locket.
För brygglösa plana grafer kan MWCCP lösas i polynomtid .
Cykel k-kåpa
En cykel k -omslag av en graf är en familj av cykler som täcker varje kant av G exakt k gånger. Det har bevisats att varje brygglös graf har cykel k -täckning för vilket heltal som helst även heltal k≥4 . För k=2 är den välkända cykeldubbeltäckningsförmodan ett öppet problem inom grafteorin. Cykeldubbeltäckningsförmodan säger att det i varje brolös graf finns en uppsättning cykler som tillsammans täcker varje kant av grafen två gånger .