Loading AI tools
grafo che consiste in un unico ciclo Da Wikipedia, l'enciclopedia libera
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:
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).
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.