Grafi bipartiti

<aside> 💡 Un grafo non direzionato è bipartito se l’insieme di nodi può essere partizionato in due sottoinsiemi $X$ e $Y$ tali che ciascun arco del grafo ha una delle due estremità in $X$ e l’altra in $Y$

</aside>

Possiamo colorare i nodi con due colori in modo tale che ogni arco ha un’estremità di un colore e l’altra dell’altro

Testare se un grafo è bipartito

Dato un grafo $G$, vogliamo scoprire se è bipartito

//problema fondamentale: trovare il massimo matching → insieme di archi di dimensione max in modo tale che ciascun vertice è toccato al più da un arco (i due insiemi saranno di cardinalità uguale) (esempio scheduling: macchina - processo)

Molti problemi su grafi diventano:

• più facili se il grafo sottostante è bipartito (matching: sottoinsieme di archi tali che non hanno estremità in comune)
• trattabili se il grafo è bipartito (max insieme indipendente)

Se volessimo considerare tutti i possibili modi di colorare i nodi con due colori dovremmo considerare $2^{n-1}$ possibilità

Lemma

<aside> 💡 Se un grafo $G$ è bipartito, non può contenere un ciclo dispari

</aside>

In pratica vale l’implicazione: $G$ bipartito → nessun ciclo dispari in $G$

Osservazione

Sia $G$ un grafo connesso e siano $L_0, .., L_k$ i livelli prodotti da un’esecuzione di BFS a partire dal nodo $s$

Può avvenire che si verifichi:

1. nessun arco di $G$ collega due nodi sullo stesso livello
2. un arco di $G$ collega due nodi sullo stesso livello

Nel caso 1 il grafo è bipartito, nel caso 2 il grafo non è bipartito

Algoritmo che usa BFS per determinare se un grafo è bipartito