Cykel (grafteori)

En bild med flera olika grafer med cykler
En bild med flera olika cykelgrafer. Graferna från höger till vänster är C 3 {\textstyle C_{3}} , C 4 {\textstyle C_{4}} , C 5 {\textstyle C_{5}} och C 6 {\textstyle C_{6}} .

Inom grafteori, är en cykel en hörnföljd där varje hörn passeras exakt en gång, och första och sista hörnet är likadana. Om hela grafen (alltså alla dess hörn och alla dess kanter) ingår i cykeln, så kallas den en cykelgraf.

Definition

En cykel är en stig som börjar och slutar i samma hörn, vilket innebär att den är sluten. Om hörnen är platser blir då en cykel en rundvandring, det vill säga vi börjar på en plats som vi sedan kommer tillbaka till.

Beteckning

Om v {\textstyle v} är ett heltal sådant att v ≥ 3 {\textstyle v\geq 3} så betecknas cykelgrafen med v {\textstyle v} hörn C v {\textstyle C_{v}} .

Referenser

  • Eriksson, Kimmo; Hillevi Gavel (2002). Diskret matematik och diskreta modeller. Lund: Studentlitteratur. sid. 141. ISBN 91-44-02465-7 
  • Trudeau, Richard J. (2015). Introduction to graph theory. Dover Publications. ISBN 9780486678702. OCLC 979079531. http://worldcat.org/oclc/979079531. Läst 12 mars 2019