ipergrafo

ipergrafo

ipergrafo generalizzazione della nozione di → grafo. Si definisce come una coppia (X, A) in cui X è un insieme finito di elementi detti nodi o vertici dell’ipergrafo e A = {A_i} è una famiglia di sottoinsiemi non vuoti di X tali che

Tali sottoinsiemi costituiscono gli archi dell’ipergrafo. Rispetto al grafo, l’ipergrafo si caratterizza per il fatto che sono ammessi archi non costituiti soltanto da coppie di nodi, ma da sottoinsiemi dell’insieme dei nodi. Si dice numero cromatico di un ipergrafo il minimo numero di colori che occorrono per colorare i suoi nodi in modo tale che nodi distinti di uno stesso arco non abbiano lo stesso colore. Ciò corrisponde a realizzare una partizione dei nodi tale che nodi adiacenti non appartengano alla stessa classe della partizione.