Il cappio (o loop) in un grafo

In un grafo un cappio, noto anche come loop o anello, è un arco che collega un vertice a se stesso.

Un cappio (o loop) può essere considerato un ciclo di lunghezza 1.

Questa concezione nasce dall'idea che un ciclo in un grafo è definito come un percorso chiuso dove il punto di partenza coincide con il punto di arrivo, e non ci sono altri vertici ripetuti lungo il percorso.

Esempio

Per esempio, consideriamo il caso di una rete di computer in cui un nodo rappresenta un computer e un arco una connessione diretta tra due computer.

Un cappio in questo contesto potrebbe rappresentare un'auto-connessione di un computer, una sorta di ciclo di feedback interno o una configurazione speciale.

Questo è solo un esempio di come la teoria dei grafi possa essere applicata a situazioni reali.

In un grafo non orientato un cappio contribuisce di due al grado del vertice, poiché, nella definizione del grado, un cappio è considerato come se il vertice fosse connesso a se stesso due volte. Il grado di un vertice in un grafo non orientato è il numero totale di archi che vi incidono, includendo i cappi.  Quindi, se un vertice ha n cappi, ciascun cappio contribuisce con 2 al grado del vertice. Per essere precisi, se un vertice ha un grado naturale \(d\) (cioè, il numero di archi esclusi i cappi) e \(n\) cappi, allora il grado totale del vertice sarà \(d + 2n\), non \(n + 2\). Questo perché ogni cappio aggiunge 2 al grado del vertice, quindi se un vertice ha, ad esempio, 3 cappi, il contributo dei cappi al suo grado sarà \(2 \times 3 = 6\).

Facciamo un altro esempio.

Immaginiamo di utilizzare la teoria dei grafi per analizzare la struttura di un social network, dove i vertici rappresentano gli utenti e gli archi indicano le connessioni tra di loro, come i like.

Un cappio in questo contesto simboleggia un'azione che un utente compie su se stesso, ad esempio, l'autolike a un proprio post o la creazione di un promemoria personale visibile solo a sé stessi all'interno della piattaforma.

Questo semplice modello ci aiuta a comprendere come le interazioni su una piattaforma social possano essere mappate e analizzate attraverso la teoria dei grafi.

Ad esempio, analizzando la presenza di cappi e altri pattern nel grafo, potremmo identificare comportamenti degli utenti, come l'auto-promozione o la gestione di contenuti personali, che sono fondamentali per comprendere l'engagement sulla piattaforma.

In generale, la teoria dei grafi offre un potente strumento per analizzare e ottimizzare le dinamiche sociali sia online che offline.

La presenza di un cappio non implica che il grafo sia connesso

La presenza di un cappio in un grafo indica semplicemente che esiste un arco che collega un vertice a se stesso, ma non implica necessariamente che il grafo sia connesso.

Un grafo si dice connesso se per ogni coppia di vertici nel grafo esiste un percorso (una sequenza di archi consecutivi) che li collega.

Quindi, la connessione in un grafo dipende dalla presenza di percorsi tra tutte le coppie di vertici, non dalla presenza di cappi.

Esempio. Per illustrare meglio, immaginiamo un grafo composto da due componenti connesse separate: la prima componente contiene un vertice con un cappio, e la seconda componente contiene alcuni vertici senza cappi.

Questo grafo non è connesso perché non esiste un percorso che collega i vertici della prima componente con quelli della seconda componente, nonostante la presenza di un cappio nella prima componente.

La confusione potrebbe derivare dal considerare un vertice con un cappio come "auto-connesso", ma questo non influisce sulla connettività generale del grafo rispetto agli altri vertici.

Pertanto, la connettività di un grafo deve essere valutata sulla base della presenza di percorsi tra tutti i vertici, indipendentemente dai cappi.