LabASD - Controlla se un grafo è 2-colorabile

Moreno Marzolla moreno.marzolla@unibo.it

Ultimo aggiornamento: 2021-04-30

Un grafo non orientato \(G = (V, E)\) è 2-colorabile se è possibile assegnare a ciascun nodo un colore scelto tra due alternative, in modo che nodi adiacenti abbiano colori diversi. Formalmente, un grafo è 2-colorabile se esiste una funzione \(c: V \rightarrow \{1, 2\}\) che assegna a ogni nodo \(v \in V\) un colore scelto tra \(\{1, 2\}\) tale che:

\[ c(u) \neq c(v)\ \mbox{per ogni arco}\ \{u,v\} \in E \]

Ad esempio, il grafo (a) in Figura 1 è 2-colorabile, mentre il grafo (b) non lo è.

Figura 1: Esempio di grafo 2-colorabile e non 2-colorabile
Figura 1: Esempio di grafo 2-colorabile e non 2-colorabile

Scrivere un programma che, dato un grafo non orientato, determina se è 2-colorabile oppure no. Attenzione: il grafo potrebbe essere non connesso.

Suggerimento

È possibile risolvere questo problema applicando un algoritmo di visita (BFS oppure DFS) al grafo \(G\). La visita inizia assegnando un colore arbitrario ad un nodo qualunque; successivamente, i nodi adiacenti ricevono il colore opposto a quello appena usato. Se si tenta di applicare un colore diverso ad un nodo già colorato, allora il grafo non è 2-colorabile. Si presti attenzione al fatto che il grafo \(G\) non è necessariamente connesso, quindi occorre ripetere il procedimento per ogni componente connessa.

File