Grafo semplice

Nella teoria dei grafi un grafo semplice è un tipo particolare di grafo senza cappi e lati multipli.

Dove i cappi (loop) sono archi che collegano un vertice a se stesso, mentre i lati multipli sono due o più archi che collegano la stessa coppia di vertici

I grafi semplici si distinguono da altre tipologie di grafi, come i multigrafi, che possono includere entrambe queste caratteristiche (cappi e/o lati multipli).

Esempio

Per illustrare meglio il concetto di grafo semplice, possiamo pensare a una rete di computer in cui ogni computer è rappresentato da un vertice e può essere connesso con altri computer attraverso un singolo cavo di rete che, invece, viene rappresentato da un arco.

In questo scenario, non ha senso collegare un computer a se stesso con un cavo di rete (evitando così i cappi), né utilizzare più cavi di rete per collegare direttamente la stessa coppia di computer (evitando così i lati multipli).

Ad esempio, non ha alcuna utilità collegare il computer A con un cavo a se stesso. A cosa serve? Non ha alcun senso nemmeno collegare il computer A al computer B tramite due cavi anziché uno. In questo caso, sia i loop che i lati multipli non hanno utilità pratica.

Quindi, la rappresentazione di questa rete di computer può essere fatta utilizzando un grafo semplice.

Il grafo semplice è quindi una rappresentazione astratta utile per modellare relazioni binarie simmetriche tra oggetti distinti in cui ogni coppia di oggetti è connessa al massimo da un'unica relazione diretta.

In un grafo semplice, un lato è considerato come una coppia non ordinata di vertici distinti, perché la connessione tra i vertici è bidirezionale (o non direzionale). Quindi, non ci sono distinzioni di direzione o sequenza tra i due vertici collegati.

Questo approccio semplifica la rappresentazione delle relazioni, poiché elimina la necessità di specificare l'ordine dei vertici nel lato e l'orientamento nei collegamenti del grafo.

Ad esempio, in questo grafo semplice il lato tra due vertici \(A\) e \(B\) può essere rappresentato come una coppia  non ordinata. Non importa se scriviamo \(\{A, B\}\) o \(\{B, A\}\), oppure $ AB $ o $ BA $, il significato rimane lo stesso: \(A\) e \(B\) sono connessi. E' una sorta di relazione di amicizia perché la relazione "essere amici" è reciproca e non implica una direzione o una sequenza nell'associazione tra \(A\) e \(B\).

Ignorare la formalità della relazione che associa i vertici ai lati in un grafo semplice aiuta a concentrarsi sull'esistenza stessa del collegamento tra i vertici, piuttosto che sulle specifiche del collegamento.

Questa proprietà rende i grafi semplici particolarmente adatti a rappresentare strutture e sistemi nei quali le connessioni doppie o i collegamenti interni a un singolo elemento non sono ammessi o non sono rilevanti per l'analisi in questione, dove l'unico aspetto rilevante delle relazioni tra le coppie di oggetti è capire se esistono o meno.