Grafo bipartito completo

Questa voce sull'argomento matematica dell'informazione e della comunicazione è solo un abbozzo.

Contribuisci a migliorarla secondo le convenzioni di Wikipedia.

Nella teoria dei grafi, si definisce grafo bipartito completo un grafo bipartito ${\displaystyle \,G=\langle (V_{1};V_{2}),E\rangle }$, con ${\displaystyle V_{1}}$ e ${\displaystyle V_{2}}$ ad indicare i sottoinsiemi dei nodi, tale che:

${\displaystyle \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 ${\displaystyle V_{1}}$ e il secondo nell'insieme ${\displaystyle 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.

• Per ogni k, K_1,k è chiamato stella. Tutti i grafi bipartiti completi che sono alberi sono stelle.
• Il grafo K_1,3 è chiamato artiglio.
• Il grafo K_3,3 è chiamato grafo dei servizi.

• Wikimedia Commons contiene immagini o altri file su grafo bipartito completo

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