Primi elementi della teoria dei grafi

Le relazioni tra gli elementi di un grafo

Un grafo è detto nullo se è formato solo da vertici.

Due vertici di un grafo si dicono adiacenti se c'è uno spigolo che li congiunge, due spigoli sono incidenti se hanno un vertice in comune, un vertice si dice isolato se non ci sono spigoli che dipartono da quel vertice.

Il grado o valenza di un vertice è il numero di spigoli che da esso si dipartono. Un vertice isolato ha grado zero e un cappio conta due nel calcolo del grado di un vertice. Un vertice che ha per grado un numero pari è detto vertice pari altrimenti è detto vertice dispari.

Se sommiamo i gradi dei vertici di un grafo otteniamo sempre un numero pari, questo accade perchè ogni spigolo congiunge due vertici e perciò nella somma complessiva dei gradi ogni spigolo è conteggiato due volte. Da questa considerazione deriva un principio che è valido per tutti i grafi: un grafo non può avere un numero dispari di vertici dispari. Questo vincolo è noto con il nome lemma delle strette di mano perchè se un dato numero di persone si stringono la mano il numero complessivo delle mani che si stringono è sempre pari (ogni stretta di mano è costituita da una coppia di mani). Se i vertici di un grafo hanno tutti lo stesso grado il grafo si dice regolare.

Naturalmente, se due grafi sono isomorfi la corrispondenza biunivoca tra vertici e lati deve valere anche per le relazioni di adiacenza e dei gradi. Ad esempio, i due grafi in figura

hanno lo stesso numero di vertici e di spigoli e hanno anche lo stesso numero di vertici dello stesso grado eppure non rappresentano la stessa informazione e quindi non sono isomorfi. Nel primo grafo i vertici di grado 2 non sono adiacenti mentre nel secondo grafo ci sono due coppie di vertici con grado 2 adiacenti. I due grafi in figura sono isomorfi, hanno lo stesso numero di vertici, lo stesso numero di spigoli, e sono entrambi regolari di grado quattro e sono rispettate le relazioni di adiacenza.

Un grafo semplice è detto completo se ha uno spigolo per ogni coppia di vertici.

In un grafo completo con n vertici il numero degli spigoli è

Un grafo completo con n vertici viene indicato di solito con il simbolo K_n. Si può facilmente osservare che i grafi completi K_n sono grafi regolari di grado n-1.

Il grafo che contiene gli spigoli (con i vertici agli estremi) che mancano a un grafo G per essere completo è detto grafo complementare di G. Ad esempio, in figura è rappresentato un grafo e il suo complementare.

Quindi se a un grafo con n vertici aggiungiamo il suo complementare si forma il grafo completo K_n.

Un grafo semplice i cui vertici possono essere suddivisi in due parti tali che ogni vertice di una parte è collogata solo a vertici dell'altra parte è detto grafo bipartito

In un grafo bipartito se tutti gli m vertici di una parte sono collegati con tutti gli n vertici dell'altra parte il grafo è detto bipartito completo e si indica con il simbolo K_m,n.

In un grafo bipartito completo K_m,n il numero dei vertici è m+n e il numero degli spigoli è m*n. Grafi bipartiti completi del tipo K_1,n vengono detti grafi a stella, ad esempio in figura è rappresentato il grafo a stella K_1,5.

Se da un grafo G si tolgono alcuni spigoli o alcuni vertici (e gli spigoli incidenti su di essi) si ottiene un grafo G₁ che è detto sottografo di G. Possiamo anche dire che il grafo G₁ è contenuto in G oppure che G contiene una copia di G₁.