Primi elementi della teoria dei grafi

Percorsi e cicli

Se ci spostiamo con l'auto da una città a un'altra città di solito consultiamo una mappa stradale per conoscere il tragitto cioè, una possibile sequenza di strade e di paesi da percorrere. Ad esempio, se il viaggio è da Brescia a Pavia possiamo scegliere il percorso rappresentato nella seguente mappa stradale.

In un grafo una sequenza di spigoli (tutti distinti) e di vertici (non necessariamente distinti) che determinano un tragitto da un vertice ad un altro vertice è detta percorso o cammino. In un grafo semplice per descrivere un cammino è sufficiente indicare solo la sequenza dei vertici.

In un cammino se il vertice di partenza è lo stesso di quello di arrivo il cammino è detto chiuso o circuito o ciclo, altrimenti è detto aperto. Un circuito si dice semplice se tutti i vertici (tranne il primo e l'ultimo) che lo compongono sono diversi.

I poligoni sono esempi di grafi ciclici semplici; il triangolo è un grafo ciclico con 3 vertici, 3 spigoli e regolare di grado 2, un quadrilatero è un grafo ciclico con 4 vertici, 4 spigoli e regolare di grado 2. In generale un poligono di n lati è un grafo ciclico semplice con n vertici, n spigoli e regolare di grado 2 e si indica con C_n.

Naturalmente, due grafi isomorfi devono contenere anche gli stessi cicli semplici. Ad esempio, i due grafi in figura hanno lo stesso numero di vertici e di spigoli e sono entrambi regolari di grado 3 eppure non sono isomorfi.

Non è difficile vedere che il secondo grafo contiene cicli C₄ mentre il primo grafo non contiene cicli C₄. Invece, i due grafi in figura hanno lo stesso numero di vertici e di spigoli, sono entrambi regolari di grado 3 e contengono gli stessi cicli semplici C₅, C₆, C₈, C₉ e sono isomorfi.

Un grafo bipartito se contiene dei cicli questi hanno sempre un numero di spigoli pari, ad esempio il grafo K_2,2 è un grafo ciclico C₄, il grafo K_3,3 contiene nove cicli C₄ e un ciclo C₆.

Se esiste un percorso che collega ogni vertice ad ogni altro vertice il grafo è detto connesso.

Un grafo connesso e privo di cicli è detto albero cosí in un albero esiste uno e uno solo percorso possibile tra ogni coppia di nodi. Ecco ad esempio, tutti i possibili alberi con cinque vertici.

Come si vede in tutti e tre gli alberi con cinque vertici numero degli spigoli è sempre quattro, ed è facile constatare che un albero con n vertici ha esattamente n-1 spigoli. L'albero è il grafo connesso con il minor numero di spigoli mentre il grafo completo è il grafo con il maggior numero di spigoli pertanto in un grafo semplice e connesso con n vertici il numero m degli spigoli deve essere