ipergrafo

In matematica, un ipergrafo è un grafo in cui un arco può essere collegato a un qualunque numero di vertici. Formalmente, un ipergrafo è una coppia dove è un insieme di elementi chiamati nodi oppure vertici, e è un insieme formato da sottoinsiemi non vuoti chiamati oppure archi. Pertanto, è un sottoinsieme di , dove è l'insieme potenza di . Mentre in un grafo gli archi sono formati da una coppia di nodi, gli iperarchi sono insieme di nodi di grandezza arbitraria, e pertanto possono contenere qualsivoglia numero intero positivo di nodi. Tuttavia, è spesso desiderabile il caso di ipergrafi dove tutti gli iperarchi hanno la stessa cardinalità; un ipergrafo k-uniforme è un ipergrafo in cui tutti gli iperarchi hanno grandezza k. In altre parole, un ipergrafo di questo genere è una collezione di insiemi, in cui ogni insieme è un iperarco connesso a k nodi. Ne segue che un ipergrafo 2-uniforme è un grafo, un ipergrafo 3-uniforme è una collezione di triple non ordinata, e così via. Un ipergrafo è anche chiamato insieme sistema o anche presa da insieme universo X. La differenza tra un insieme sistema e un ipergrafo è una domanda che spesso sorge spontanea. La teoria degli ipergrafi tende ad occuparsi di questioni simili a quelle della teoria dei grafi, quali connettività e colorabilità, mentre la teoria degli insiemi tende a occuparsi di domande non inerenti alla teoria dei grafi, quali la . Esistono diverse definizioni: a volte gli archi non devono essere vuoti e a volte archi multipli, con lo stesso insieme di nodi, sono ammessi. Gli ipergrafi possono essere visti come . In particolare, esiste un "grafo incidente" biparito o "" corrispondente a ogni ipergrafo, al contrario, la maggior parte dei grafi bipartiti, ma non tutti, possono essere considerati come grafi di incidenza, o ipergrafi. Gli ipergrafi hanno tanti altri nomi. In geometria computazionale, un ipergrafo può a volte essere definito come range space, e gli iperarchi vengono chiamati ranges.Nella teoria dei , gli ipergrafi vengono anche chiamati giochi semplici (voting games); questa nozione viene applicata per risolvere problemi in ambito della teoria della scelta sociale. In alcuni articoli, gli archi vengono chiamati anche iperlink o connettori. Tra i casi particolari di vi sono: i grafi k-uniformi, come precedentemente discusso; i , dove nessun arco appare come sottoinsieme di un altro arco; e i , che contiene tutti i sottoinsiemi di ogni arco. La collezione degli ipergrafi è una categoria, avente gli omomorfismi di ipergrafi come morfismi.