Grafo bipartito

Da Wikipedia, l'enciclopedia libera.
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 ; esso si dice grafo bipartito se il suo insieme dei vertici può essere bipartito in due sottoinsiemi disgiunti tali che ogni arco in ha la forma con e .

Un grafo bipartito può essere efficacemente presentato con una notazione della forma .

Esempi[modifica | modifica wikitesto]

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 Nel quale e , in cui le due partizioni sono visivamente separate (ciascun vertice a sinistra collegato solo a vertici a destra).

Grafo bipartito.jpg

Caratterizzazioni[modifica | modifica wikitesto]

Proprietà[modifica | modifica wikitesto]

Applicazioni[modifica | modifica wikitesto]

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 con l'insieme degli spigoli ottenuto inserendo per ciascuna persona p gli spigoli 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[modifica | modifica wikitesto]

Altri progetti[modifica | modifica wikitesto]

Matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica