Cykel | |
---|---|
Toppar | n |
revben | n |
Omkrets | n |
Automorfismer | 2n ( Dn ) _ _ |
Kromatiskt nummer | 3 om n är udda och 2 om jämnt |
Kromatiskt index | 3 om n är udda och 2 om jämnt |
Spektrum | {2 cos(2 k π / n ), k =1, ... , n } [1] |
Egenskaper |
2-reguljär
Euler |
Mediafiler på Wikimedia Commons |
I grafteorin är en grafcykel en graf som består av en enda cykel , eller, med andra ord, ett visst antal hörn sammankopplade med en sluten kedja. En cykelgraf med n hörn betecknas som C n . Antalet hörn i C n är lika med antalet kanter, och varje hörn har grad 2 , det vill säga varje hörn faller in med exakt två kanter.
Graph-cycle har många synonymer. Termerna enkel cykelgraf och cyklisk graf används, även om den senare termen inte är vanligt förekommande eftersom den kan hänvisa till grafer som inte är acykliska . Termerna cykel , polygon eller n -gon används ibland . En cykel med ett jämnt antal hörn kallas en jämn cykel , och med ett udda antal hörn, en udda cykel .
grafcykel:
För övrigt:
En riktad cykelgraf är en riktad version av en cykelgraf där alla bågar pekar i samma riktning.
I en riktad graf kallas uppsättningen av bågar som innehåller minst en båge från varje riktad cykel för rivningsuppsättningen av bågar . På liknande sätt kallas en uppsättning av hörn som innehåller minst en vertex från varje orienterad cykel en cykelskärande vertexuppsättning .
En riktad grafcykel har en konstant grad 1 och en konstant utgrad 1 .
Riktade cykelgrafer är Cayley-graferna för cykliska grupper (se till exempel Trevisan ) .