Graf cyklus

Cyklus

Toppe	n
ribben	n
Omkreds	n
Automorfismer	2n ( Dn ) _ _
Kromatisk tal	3 hvis n er ulige og 2 hvis lige
Kromatisk indeks	3 hvis n er ulige og 2 hvis lige
Spektrum	{2 cos(2 k π / n ), k =1, ... , n } [1]
Ejendomme	2-regulær vertex-transitiv kant-transitiv med konstant afstand en Hamiltonian Euler
Mediefiler på Wikimedia Commons

I grafteori er en grafcyklus en graf, der består af en enkelt cyklus , eller med andre ord, et vist antal hjørner forbundet med en lukket kæde. En cyklusgraf med n toppunkter betegnes som C n . Antallet af toppunkter i C n er lig med antallet af kanter, og hvert toppunkt har grad 2 , det vil sige, at ethvert toppunkt er indfaldende med præcis to kanter.

Terminologi

Graph-cycle har mange synonymer. Begreberne simpel cyklusgraf og cyklisk graf bruges, selvom sidstnævnte udtryk ikke er almindeligt brugt, fordi det kan referere til grafer, der ikke er acykliske . Udtrykkene cyklus , polygon eller n - gon bruges nogle gange . En cyklus med et lige antal hjørner kaldes en lige cyklus , og med et ulige antal hjørner, en ulige cyklus .

Egenskaber

graf cyklus:

tilsluttet
2-almindelige
Euler
hamiltonsk
vi farver det i to farver, hvis og kun hvis det har et lige antal hjørner. En graf er todelt, hvis og kun hvis den ikke har nogen ulige cyklusser (som undergrafer) ( König , 1936).
kant-2-farverbar , hvis og kun hvis den har et lige antal hjørner.
Vertex-farvning med 3 farver og kant-3-farvning til et vilkårligt antal hjørner.
med konstant afstandsenhed

Ud over:

Fordi cyklusgrafer kan tegnes som regulære polygoner , er symmetrierne af en cyklus med n toppunkter de samme som for en regulær polygon med n sider, det vil sige en dihedral gruppe af orden 2n . Især er der symmetrier, der tager et hvilket som helst toppunkt til et hvilket som helst andet toppunkt og enhver kant til en hvilken som helst anden kant, således at en n -cyklus er en symmetrisk graf .

Styret grafcyklus

En rettet cyklusgraf er en rettet version af en cyklusgraf, hvor alle buer peger i samme retning.

I en rettet graf kaldes det sæt af buer, der indeholder mindst én bue fra hver rettet cyklus, det rivende sæt af buer . På samme måde kaldes et sæt toppunkter, der indeholder mindst ét toppunkt fra hver orienteret cyklus, et cyklusskærende toppunktsæt .

En rettet grafcyklus har en konstant indegrad 1 og en konstant udgrad 1 .

Styrede cyklusgrafer er Cayley-graferne for cykliske grupper (se f.eks. Trevisan ) .

Se også

Noter

↑ Nogle simple grafspektre Arkiveret 1. juli 2014 på Wayback Machine . win.tue.nl