Grafo bipartito

Esempio di grafo bipartito senza cicli

Un grafo bipartito completo con m = 5 e n = 3

Nella teoria dei grafi, un grafo bipartito è un grafo tale che l'insieme dei suoi vertici si può partizionare in due sottoinsiemi tali che ogni vertice di una di queste due parti è collegato solo a vertici dell'altra.

Più formalmente, consideriamo un grafo non orientato $G=⟨V,E⟩$; esso si dice grafo bipartito se il suo insieme dei vertici $V$ può essere bipartito in due sottoinsiemi disgiunti $V=V_1\dot{\cup }{V}_2$ tali che ogni arco in $E$ ha la forma $\{v_1,v_2\}$ con $v_1\in V_1$ e $v_2\in V_2$.

Un grafo bipartito può essere efficacemente presentato con una notazione della forma $⟨V_1\dot{\cup }{V}_2,E⟩$.

Esempi

Gli alberi sono particolari grafi bipartiti; più in generale, tutti i grafi non orientati aciclici sono bipartiti.

I grafi ciclo con un numero pari di vertici sono grafi bipartiti.

Esempio di grafo bipartito $⟨V_1\dot{\cup }{V}_2,E⟩$ Nel quale $V_1=\{v1,v2,v3,v4,v5\}$ e $V_2=\{u1,u2,u3,u4\}$, in cui le due partizioni sono visivamente separate (ciascun vertice a sinistra collegato solo a vertici a destra).

Caratterizzazioni

• I grafi bipartiti sono i grafi con numero cromatico dei vertici uguale a 2.
• I grafi bipartiti sono i grafi privi di cicli dispari.

Proprietà

• La cardinalità della copertura dei vertici minima coincide con la cardinalità dell'accoppiamento massimo.
• La somma della cardinalità dell'insieme indipendente massimo e di quella dell'accoppiamento massimo è uguale al numero dei vertici.
• L'unione di grafi bipartiti è un grafo bipartito. Per una classificazione dei grafi bipartiti quindi hanno interesse primario i grafi bipartiti connessi.
• Per un grafo bipartito connesso la cardinalità della copertura minima degli spigoli è uguale a quella dell'insieme indipendente massimo.
• Per un grafo bipartito connesso la somma della cardinalità della copertura minima degli spigoli e di quella della copertura minima dei vertici è uguale al numero dei vertici.

Applicazioni

I grafi bipartiti costituiscono buoni modelli per i problemi di accoppiamento. Un esempio è fornito dai problemi di assegnazione di mansioni, problemi formulati in termini come i seguenti.
Supponiamo di avere un insieme di persone P e un insieme di mansioni M che richiedono competenze specifiche in modo che non tutte le persone sono in grado di svolgere tutte le mansioni. Una particolare situazione si può modellare con un grafo bipartito della forma $⟨P\dot{\cup }M,E⟩$ con l'insieme degli spigoli ottenuto inserendo per ciascuna persona p gli spigoli $\{p,m\}$ relativi a tutte le mansioni m che p è in grado svolgere.

Il teorema dei matrimoni fornisce una caratterizzazione dei grafi bipartiti che ammettono accoppiamenti perfetti.

Voci correlate

• Grafo bipartito completo

Collegamenti esterni

• Template:Collegamenti esterni