Grafo bipartito completo

Da Wikipedia, l'enciclopedia libera.

Nella teoria dei grafi, si definisce grafo bipartito completo un grafo bipartito \,G=\langle (V_1;V_2),E \rangle, con V_1 e V_2 ad indicare i sottoinsiemi dei nodi, tale che:

\forall\; (v_i,v_j) : [(v_i \in V_1) \land (v_j \in V_2)] \;\exists \;\{v_i;v_j\}

È quindi un grafo bipartito in cui esistono tutti gli archi che connettono gli elementi di un insieme a quelli dell'altro, o, come dice la definizione, per ogni coppia di vertici di cui il primo nell'insieme V_1 e il secondo nell'insieme V_2 esiste un arco che abbia inizio nel primo e termine nel secondo.

Questo genere di grafi è utilizzato in alcuni algoritmi, in particolare nella soluzione di problemi di assegnamento.

Esempi[modifica | modifica wikitesto]

I grafi stellati S3, S4, S5 e S6.
Grafo dei servizi K3,3
  • Per ogni k, K1,k è chiamato stella. Tutti i grafi bipartiti completi che sono alberi sono stelle.
  • Il grafo K1,3 è chiamato artiglio.
  • Il grafo K3,3 è chiamato grafo dei servizi.
matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica