Grafo ciclo

Da Wikipedia, l'enciclopedia libera.
Vai alla navigazione Vai alla ricerca
Un grafo ciclo di lunghezza 6

Nella teoria dei grafi, un grafo ciclo o grafo circolare è un grafo che consiste di un unico ciclo o, in altre parole, di un certo numero di vertici connessi in una catena chiusa. Il grafo ciclo con n vertici è chiamato Cn. Il numero di vertici in Cn uguaglia il numero di spigoli, e ogni vertice ha grado 2; ossia, ogni vertice ha esattamente due spigoli incidenti con esso.

Esistono molti sinonimi di "grafo ciclo". Questi comprendono grafo ciclo semplice e grafo ciclico, sebbene il secondo termine sia usato meno spesso, perché può riferirsi a grafi che semplicemente non sono aciclici. Tra i teorici dei grafi, si usano spesso anche ciclo, poligono o n-gono. Un ciclo con un numero pari di vertici è chiamato ciclo pari; un ciclo con un numero dispari di vertici è chiamato ciclo dispari.

Un grafo ciclo è:

In aggiunta:

  • Poiché i grafi ciclo possono essere disegnati come poligoni regolari, le simmetrie di un n-ciclo sono le stesse di un poligono regolare con n lati, il gruppo diedrico di ordine 2n. In particolare, esistono simmetrie che portano qualsiasi vertice a qualsiasi altro vertice, e qualsiasi spigolo a qualsiasi altro spigolo, perciò l'n-ciclo è un grafo simmetrico.

Grafo ciclo diretto

[modifica | modifica wikitesto]
Un grafo ciclo diretto di lunghezza 8

Un grafo ciclo diretto è una versione diretta di un grafo ciclo, con tutti gli spigoli orientati nella stessa direzione.

In un grafo diretto, un insieme di spigoli che contiene almeno uno spigolo (o arco) di ciascun ciclo diretto è chiamato insieme di archi in retroazione. Similmente, un insieme di vertici contenente almeno un vertice di ciascun ciclo diretto è chiamato insieme di vertici in retroazione.

Un grafo ciclo diretto ha grado in entrata uniforme 1 e grado in uscita uniforme 1.

I grafi ciclo diretti sono grafi di Cayley per i gruppi ciclici (vedi ad es. Trevisan).


Voci correlate

[modifica | modifica wikitesto]

Altri progetti

[modifica | modifica wikitesto]

Collegamenti esterni

[modifica | modifica wikitesto]
  Portale Matematica: accedi alle voci di Wikipedia che trattano di Matematica