Cicli in un grafo

Un ciclo in un grafo è un percorso chiuso, ovvero una sequenza di vertici in cui il primo e l'ultimo vertice sono lo stesso e ogni coppia di vertici consecutivi nel percorso è connessa da un'arco.

In altre parole, un ciclo è un percorso che inizia e termina sullo stesso vertice senza attraversare alcun vertice più di una volta, ad eccezione del vertice di partenza/arrivo che è lo stesso.

Ci sono due tipi principali di grafi dove i cicli possono essere considerati: i grafi non orientati e i grafi orientati (o digrafi).

• Nei grafi non orientati, un ciclo è una sequenza di vertici connessi da archi dove l'ultimo vertice si ricollega al primo senza ripetere archi o vertici, eccetto il vertice iniziale/finale.
  
• Nei grafi orientati (digrafi), un ciclo (o ciclo diretto) segue la stessa regola, ma tenendo conto della direzione degli archi. Quindi, ogni arco deve "puntare" al vertice successivo nella sequenza fino a ritornare al punto di partenza.
  

I cicli sono significativi in molti contesti e applicazioni pratiche, come nell'ottimizzazione delle reti, nella grafica computerizzata nella ricerca di circuiti in reti di trasporto, nell'analisi di dipendenze in sistemi di pianificazione, e nella rilevazione di deadlock in sistemi operativi, ecc.

Per identificare un ciclo in un grafo, possono essere utilizzati diversi algoritmi, tra cui l'algoritmo DFS (Depth-First Search) che individua un ciclo se durante un percorso incontra un vertice già visitato che non è il genitore diretto del vertice corrente. Un altro algoritmo di ricerca dei cicli è  l'algoritmo BFS (Breadth-First Search).

La caratteristica distintiva di un ciclo in un grafo è proprio quella che ti permette di disporre i vertici in modo tale che formino un cerchio senza interruzioni o ripetizioni, ovvero un percorso chiuso dove ogni vertice è connesso al successivo e l'ultimo vertice si ricollega al primo.

Esempio

Immaginiamo di avere un semplice grafo non orientato rappresentato come segue:

Questo grafo contiene diversi cicli.

Ad esempio, il ciclo formato dai vertici A, B, C che ritorna ad A.

Il ciclo può essere rappresentato come una sequenza di vertici A-B-C-A o qualsiasi sua permutazione ciclica (ad es., B-C-A-B).

Un altro ciclo è composto dai vertici B, C, D che ritorna in B ecc.

 

Per trovare un ciclo in questo grafo, potremmo utilizzare l'algoritmo di ricerca in profondità (DFS).

Ecco come potrebbe funzionare in modo conciso:

1. Partiamo dal vertice A e lo segniamo come visitato nell'insieme V={A}.
   
2. Scegliamo un vertice adiacente a A, diciamo B, lo visitiamo e proseguiamo. Ora l'insieme dei vertici visitati è V={A,B).
   
3. Da B, procediamo al vertice adiacente C, che non è stato ancora visitato, quindi lo segniamo come visitato e continuiamo. L'insieme dei vertici visitati è V={A,B,C).
   
4. Da C, ci spostiamo al vertice adiacente A, che è anche il punto di partenza. Il vertice A è già presente nell'insieme dei vertici visitati V={A,B,C). Quindi, tornando ad A, abbiamo completato un ciclo.
   

Questo semplice esempio illustra il concetto di ciclo in un grafo non orientato e come un algoritmo come DFS può essere utilizzato per trovarlo.

In contesti più complessi, la logica di base rimane simile, ma potremmo dover gestire una maggiore complessità, come grafi con più cicli o la necessità di evitare il rilevamento di falsi cicli dovuti alla visita di vertici attraverso percorsi diversi.