Grafo bipartito

Da Wikipedia, l'enciclopedia libera.

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=\langle V,E \rangle; 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 \langle V_1 \dot\cup V_2 , E \rangle.

Esempi[modifica | modifica sorgente]

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 \langle V_1 \dot\cup V_2 , E \rangle 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).

Grafo bipartito.jpg

Caratterizzazioni[modifica | modifica sorgente]

Proprietà[modifica | modifica sorgente]

Applicazioni[modifica | modifica sorgente]

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 \,\langle P\dot\cup M,E\rangle 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[modifica | modifica sorgente]

Altri progetti[modifica | modifica sorgente]

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