Grafo bipartito

Un grafo bipartito è un tipo particolare di grafo in cui i vertici possono essere divisi in due distnti insiemi indipendenti tali che ogni arco collega un vertice di un insieme con un vertice dell'altro insieme e non ci sono archi che collegano vertici all'interno dello stesso insieme. 

Un grafo è considerato bipartito se l'insieme dei suoi vertici (nodi) può essere suddiviso in due sottoinsiemi distinti A e B tali che:

• Insiemi disgiunti
  I due insiemi di vertici A e B non hanno vertici in comune. Questo significa che ogni vertice del grafo appartiene esclusivamente a uno dei due insiemi.
• Spigoli solo fra gli insiemi
  Tutti gli spigoli del grafo collegano un vertice in A con uno in B. Non ci sono spigoli che collegano vertici all'interno dello stesso insieme A o B.

Questi due insiemi sono spesso chiamati partite sets.

Ad esempio, in questo grafo l'insieme di vertici {A,B,C} rappresenta tre lavoratori mentre l'insieme {1,2,3} rappresenta tre distinti lavori.

Gli spigoli rappresentano solo relazioni incrociate tra i due insiemi distinti e connettono persone a lavori per cui sono qualificate .

In questo esempio il grafo bipartito indica che il lavoratore A è qualificato per il lavoro 1, il lavoratore B per i lavori 1 e 3, infine il lavoratore C è qualificato a svolgere il lavoro 2.

Questo è un esempio classico di grafo bipartito dove nessuna delle persone è connessa direttamente a un'altra persona e nessun lavoro è connesso direttamente a un altro lavoro.

In un grafo bipartito è possibile assegnare uno dei due colori a ogni vertice in modo che due vertici collegati da un arco abbiano colori differenti.

In altri termini, un grafo bipartito può essere colorato con due colori, solitamente blu e rosso, in modo tale che nessun nodo direttamente collegato (adiacente) abbia lo stesso colore.

Questo implica che il suo numero cromatico, la quantità minima di colori necessari per colorare i vertici del grafo in modo che due vertici connessi da un arco abbiano colori diversi, è 2.

Questo è possibile se e solo se il grafo non contiene cicli dispari, ovvero cicli con un numero dispari di spigoli (o vertici).

La presenza di un eventuale ciclo dispari in un grafo preclude la possibilità che il grafo sia bipartito, perché non sarebbe possibile colorare i vertici seguendo le regole senza finire con almeno un spigolo che collega due vertici dello stesso colore.

Ad esempio, inserendo la connessione 1-3 nel grafo precedente creiamo un ciclo dispari B→1→3  con due vertici adiacenti (1 e 3) che hanno lo stesso colore.

Pertanto, un grafo che contiene cicli dispari non può essere bipartito.

E' invece possibile che in un grafo bipartito ci siano cicli pari, ovvero cicli composti da un numero pari di spigoli (o vertici). Ad esempio, modifichiamo il grafo precedente inserendo due nuovi spigoli B-2 e C-3. Questa modifica genera un ciclo pari B→2→C→3 senza snaturare il grafo bipartito.

Questa proprietà li rende molto utili per situazioni in cui si vogliono evitare accoppiamenti diretti o conflitti, come nei problemi di schedulazione o nell'assegnazione delle risorse.

Quali sono le applicazioni dei grafi bipartiti?

I grafi bipartiti hanno diverse applicazioni pratiche in vari campi, ecco alcune in sintesi:

Possono essere usati per risolvere problemi di scheduling o negli algoritmi di accoppiamento (matchmaking) per abbinare elementi di due insiemi distinti.

Ad esempio, evitare conflitti di orario, come nella pianificazione delle lezioni o nell'assegnazione delle sale riunioni.

Spesso sono usati per assegnare compiti a macchine dove i compiti sono in un insieme e le macchine in un altro.