Grafo k-partito

Un grafo è detto grafo k-partito se l'insieme dei suoi vertici può essere partizionato in k sottoinsiemi disgiunti chiamati partizioni o classi.

I k sottoinsiemi sono disgiunti, quindi in un grafo k-partito non esistono spigoli tra vertici dello stesso sottoinsieme (partizione).

Ogni spigolo nel grafo collega vertici appartenenti a sottoinsiemi diversi (partizioni diverse).

Inoltre, ogni vertice è in una e una sola partizione.

Un grafo k-partito è un'estensione del concetto di grafo bipartito. Mentre un grafo bipartito può essere diviso in due insiemi disgiunti tali che ogni spigolo collega un vertice in un insieme a un vertice nell'altro, senza spigoli all'interno dello stesso insieme, un grafo k-partito generalizza questa idea a k insiemi disgiunti.

In altre parole, in un grafo k-partito, i vertici sono divisi in k categorie, e i collegamenti (o spigoli) sono permessi solo tra categorie diverse, non all'interno della stessa categoria.

Esempio

Immaginiamo un semplice scenario in cui ci sono tre tipi di entità: `Studenti`, `Corsi` e `Insegnanti`.

Possiamo rappresentare questo scenario con un grafo tripartito ovvero un grafo con k=3 (grafo 3-partito) come segue:

Dove l'insieme {S1, S2, S3, S4, S5} è composto da cinque studenti, l'insieme  {C1, C2} è composto da due corso e l'insieme {I1, I2} è composto da due insegnanti.

• I collegamenti tra `Studenti` e `Corsi` indicano a quali corsi è iscritto ogni studente.
• I collegamenti tra `Corsi` e `Insegnanti` (es. C1-I1, C2-I2) indicano qual è l'insegnante che tiene un corso.

Ad esempio, c'è uno studente (S3) che è iscritto a entrambi i corsi C1 e C2. Gli altri studenti sono, invece, iscritti a un solo corso. Ogni corso è tenuto da un insegnante dedicato.

In questo grafo tripartito, non ci sono spigoli tra vertici dello stesso insieme. Ad esempio, non ci sono spigoli diretti tra studenti, tra corsi, o tra insegnanti, ma solo tra insiemi diversi.

Il numero cromatico di un grafo k-partito è al massimo k, perché è possibile assegnare un colore diverso a ciascuno dei k insiemi partiti, assicurando che non ci siano due vertici adiacenti dello stesso colore.

Quali sono le applicazioni dei grafi k-partiti?

I grafi k-partiti sono utili in molte applicazioni che richiedono di modellare relazioni tra più tipi di oggetti o entità, come nella programmazione di eventi, nell'organizzazione di risorse, o nella modellazione di sistemi di raccomandazione.