Ipergrafo: differenze tra le versioni

Versione delle 19:49, 5 mag 2018

Versione attuale delle 15:13, 17 mar 2025

(17 versioni intermedie di 15 utenti non mostrate)

Riga 1:

{{T|lingua=eninglese|argomento=matematica|data=maggio 2018|commento = vi sono lacerti di frase non ancora tradotti}}

{{w|matematica|aprile 2018}}

{{T|lingua=en|argomento=matematica|data=maggio 2018|commento = vi sono lacerti di frase non ancora tradotti}}

[[File:Hypergraph-wikipedia.svg|frame|destra|

Riga 11 ⟶ 10:

<math>\{v_4\}\}</math>.

]]

[[File:PAOH representation of the hypergraph.png|alt=Rappresentazione alternativa dell'ipergrafo riportato nella figura precedente, chiamata PAOH. Gli archi sono linee verticali che collegano i vertici. I vertici sono allineati a sinistra. La legenda a destra mostra i nomi degli archi.|miniatura|263x263px|Rappresentazione alternativa dell'ipergrafo riportato nella figura precedente, chiamata PAOH<ref name=":0">{{Cita pubblicazione|nome=P.|cognome=Valdivia|data=2019|titolo=Analyzing Dynamic Hypergraphs with Parallel Aggregated Ordered Hypergraph Visualization|rivista=IEEE Transactions on Visualization and Computer Graphics|pp=1-1|accesso=2019-10-28|doi=10.1109/TVCG.2019.2933196|url=https://ieeexplore.ieee.org/document/8789484/|nome2=P.|cognome2=Buono|nome3=C.|cognome3=Plaisant}}</ref>. Gli archi sono linee verticali che collegano i vertici. I vertici sono allineati a sinistra. La legenda a destra mostra i nomi degli archi.]]

In [[matematica]], un '''ipergrafo''' è un [[grafo]] in cui un arco può essere collegato a un qualunque numero di [[Vertice (teoria dei grafi)| vertici]]. Formalmente, un ipergrafo <math>H</math> è una coppia <math>H = (X,E)</math> dove <math>X</math> è un insieme di elementi chiamati ''nodi'' oppure ''vertici'', e <math>E</math> è un insieme formato da sottoinsiemi non vuoti <math>X</math> chiamati '''[[iperarchi]]''' oppure '''archi'''. Pertanto, <math>E</math> è un sottoinsieme di <math>\mathcal{P}(X) \setminus\{\emptysetvarnothing\}</math>, dove <math>\mathcal{P}(X)</math> è l' [[insieme potenza]] di <math>X</math>.

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''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.

In [[matematica]], un '''ipergrafo''' è un [[grafo]] in cui un arco può essere collegato a un qualunque numero di [[Vertice (teoria dei grafi)| vertici]]. Formalmente, un ipergrafo <math>H</math> è una coppia <math>H = (X,E)</math> dove <math>X</math> è un insieme di elementi chiamati ''nodi'' oppure ''vertici'', e <math>E</math> è un insieme formato da sottoinsiemi non vuoti <math>X</math> chiamati '''[[iperarchi]]''' oppure '''archi'''. Pertanto, <math>E</math> è un sottoinsieme di <math>\mathcal{P}(X) \setminus\{\emptyset\}</math>, dove <math>\mathcal{P}(X)</math> è l' [[insieme potenza]] di <math>X</math>.

Un ipergrafo è anche chiamato '''insieme sistema''' o anche '''[[famiglia di insiemi]]''' 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 [[Grafo #Connettività |connettività]] e [[graphColorazione coloringdei grafi|colorabilitycolorabilità]], mentre la [[teoria degli insiemi]] tende ada occuparsi di domande dinon ambitoinerenti nonalla grafo-teoricoteoria dei grafi, quali la [[Sperner'sTeorema di theorem|Sperner|teoria theorydi Sperner]].

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.

Esistono diverse definizioni;: a volte gli archi non devono essere vuoti, e a volte archi multipli, con lo stesso insieme di notinodi, sono ammessi.

Un ipergrafo è anche chiamato '''insieme sistema''' o anche '''[[famiglia di insiemi]]''' 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 [[Grafo #Connettività |connettività]] e [[graph coloring|colorability]], mentre la teoria degli insiemi tende ad occuparsi di domande di ambito non grafo-teorico, quali [[Sperner's theorem|Sperner theory]].

Gli ipergrafi possono essere visti come [[strutture incidenti]]. In particulareparticolare, esiste un "grafo incidente" biparito oro "[[Levigrafo graphdi Levi]]" corrispondente a ogni ipergrafo, al contrario, la maggior parte, ma non tutti, dei [[grafo bipartito|grafi bipartiti]], ma non tutti, possono essere considerati come grafi di incidenza, o ipergrafi.

Esistono diverse definizioni; a volte gli archi non devono essere vuoti, e a volte archi multipli, con lo stesso insieme di noti, sono ammessi.

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''.<ref>{{citationCita pubblicazione|cognome1= Haussler |nome1= David |wkautore1= David Haussler

Gli ipergrafi possono essere visti come [[strutture incidenti]]. In particulare, esiste un "grafo incidente" biparito or "[[Levi graph]]" corrispondente a ogni ipergrafo, al contrario, la maggior parte, ma non tutti, dei [[grafi bipartiti]] possono essere considerati come grafi di incidenza, o ipergrafi.

| last2 cognome2= Welzl | first2 nome2= Emo | author2-link wkautore2= Emo Welzl

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''.<ref>{{citation

| last1 = Haussler | first1 = David | author1-link = David Haussler

| last2 = Welzl | first2 = Emo | author2-link = Emo Welzl

| doi = 10.1007/BF02187876

| issue numero= 2

| journal rivista= [[Discrete and Computational Geometry]]

| mr = 884223

|pp= 127-151

| pages = 127–151

| title titolo= ε-nets and simplex range queries

|url= https://archive.org/details/sim_discrete-computational-geometry_1987_2_2/page/127 |volume= 2

| volume = 2

| year anno= 1987}}.</ref>

Nella teoria dei [[giochi cooperativi]], 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 '''iperlinks'iperlink'' o '''connettori'''.<ref>Judea Pearl, in ''HEURISTICS Intelligent Search Strategies for Computer Problem Solving'', Addison Wesley (1984), p. 25.</ref>

Tra i casi particolari di vi sono : i [[HypergraphIpergrafo#Symmetric hypergraphsIpergrafi_simmetrici|grafi ''k''-uniform onesuniformi]], come precedentemente discusso; i [[clutter (mathematicsmatematica)|clutter]]s, dove nessun arco appare come sottoinsieme di un altro arco; e i [[complesso simpliciale astratto|complessi simpliciali astratti]], che contiene tutti i sottoinsiemi di ogni arco.

La collezione didegli ipergrafi è una [[CategoryTeoria (mathematics)delle categorie|categorycategoria]], avente un ipergrafogli [[omomorfoIpergrafo#Morfismi e isomorfismi|omomorfismi di ipergrafi]] come [[morphismmorfismo|morfismi]]s.

==Terminologia==

Riga 51 ⟶ 49:

dove <math>I_v</math> e <math>I_e</math> sono gli [[insiemi indici]] dei vertici e degli archi, rispettivamente.

Un '''sottoipergrafo''' è un ipergrafo con alcuni vertici rimossi. Formalmente, il sottoipergrafo <math>H_A</math> indotto dal sottoinsieme <math>A</math> di <math>X</math> è definito come

:<math>H_A=\left(A, \lbrace e_i \cap A |e_i \cap A \neq \varnothing \rbrace \right).</math>

e_i \cap A \neq \varnothing \rbrace \right).</math>

Un'estensione di un sottoipergrafo è un ipergrafo dove ogni iperarco di <math>H</math> che è parzialmente contenuto nel sottoipergrafo <math>H_A</math> è completamente contenuto dall'estensione <math>Ex(H_A)</math>. Formalmente, <math>Ex(H_A) = (A \cup A', E' )</math> con <math>A' = \cup_{e \in E} e \setminus A</math> e <math>E' = \lbrace e \in E | e \subseteq (A \cup A') \rbrace</math>.

Una '''estensione''' di un '''sottoipergrafo''' è un ipergrafo dove ogni

iperarco di <math>H</math> che è parzialmente contenuto nel sottoipergrafo <math>H_A</math> è completamente contenuto dall'estensione <math>Ex(H_A)</math>.

Formalmente, <math>Ex(H_A) = (A \cup A', E' )</math> con <math>A' = \cup_{e \in E} e \setminus A</math> e <math>E' = \lbrace e \in E | e \subseteq (A \cup A') \rbrace</math>.

L' '''ipergrafo parziale''' è un ipergrafo con alcuni archi rimossi. Dato un sottoinsieme <math>J \subset I_e</math> del setdell'insieme di indici dell'arco, l'ipergrafo parziale generato da <math>J</math> è l'ipergrafo

:<math>\left(X, \lbrace e_i | i\in J \rbrace \right).</math>

Dato un sottoinsieme <math>A\subseteq X</math>, la '''sezione dell'ipergrafo''' è l'ipergrafo parziale.

:<math>H \times A = \left(A, \lbrace e_i | i\in I_e, e_i \subseteq A \rbrace \right).</math>

i\in I_e, e_i \subseteq A \rbrace \right).</math>

Il '''duale''' <math>H^*</math> di <math>H</math> è un ipergrafo i cui vertici e archi sono scambiati, tale che i vertici sono dati da <math>\lbrace e_i \rbrace</math> e i cui archi sono dati da <math>\lbrace X_m \rbrace</math> dove

:<math>X_m = \lbrace e_i | x_m \in e_i \rbrace. </math>

Quando una nozione di uguaglianza è propriamente definitedefinita, come quella seguentaseguente, l'operazione di prendere il duale di un ipergrafo è un'[[involuzione (matematicateoria degli insiemi)|involuzione]], i.e.,cioè

:<math>\left(H^*\right)^* = H.</math>

Un [[grafo connesso]] ''G'' con lo stesso insieme vertice di un ipergrafo connesso ''H'' è un '''grafo ospite''' per ''H'' se ogni iperarco di ''H'' [[sottografo indotto| induce ]] a un sottografo connesso in ''G''. Per un ipergrafo disconnesso ''H'', ''G'' è un grafo ospite se esiste una funzione biettiva tra le [[Componente connessa (teoria dei grafi)|componenti connesse]] di ''G'' e di ''H'', tale che ogni componente connessa ''G<nowiki>'</nowiki>'' di ''G'' è un ospite del corrispondente ''H<nowiki>'</nowiki>''.

A ipergrafo '''bipartito''' [[se e solo se]] i suoi vertici possono essere divisi in due classi, ''U'' e ''V'', in modo tale che ogni iperarco di cardinalità almeno 2 contenga almeno un vertice da entrambe le classi.

La '''sezione-2''' (o '''cricca''', '''grafo di rappresentazione''', '''grafo primale''', '''grafo di Gaifman''') di un ipergrafo è il grafo con gli stessi vertici dell'ipergrafo, e con gli archi tra tutte le coppie di vertici contenute nello stesso iperarco.

==Modello di un grafo bipartito==

Un ipergrafo ''H'' può essere rappresentato da un [[grafo bipartito]] ''BG'' come segue: gli insiemi ''X'' e ''E'' sono le partizioni di ''BG'', e (''x₁'', ''e₁'') sono connessi con un arco se e solo se il vertice ''x₁'' è contenuto nell'arco ''e₁'' in ''H''. Contrariamente, ogni grafo bipartito con parti fissate e alcun nodo sconnesso nella seconda parte, rappresenta l'idea di ipergrafo appena descritta. Questo esempio di grafo bipartito viene anche chiamato [[grafo di incidenza]].

==Aciclicità==

Riga 91 ⟶ 85:

Una prima definizione di aciclicità per ipergrafi viene data da [[Claude Berge]]:<ref>[[Claude Berge]], ''Graphs and Hypergraphs''</ref> un ipergrafo è Berge-aciclico se il suo [[grafo di incidenza]] (il [[grafo bipartito]] sopra definito) è aciclico. Tale definizione è molto restrittiva: per esempio, se un ipergrafo ha una coppia <math>v \neq v'</math> di vertici e alcune coppie <math>f \neq f'</math> di iperarchi tali che <math>v, v' \in f</math> and <math>v, v' \in f'</math>, allora esso è Berge-ciclico. La Berge-cyclicità può ovviamente essere indagata in [[tempo lineare]] esplorando un grafo di incidenza.

Possiamo utilizzare una definizione più debole di aciclicità di ipergrafo,<ref>C. Beeri, [[Ronald Fagin|R. Fagin]], D. Maier, [[Mihalis Yannakakis|M. Yannakakis]], ''On the Desirability of Acyclic Database Schemes''</ref> in seguito chiamata α-aciclicità. Tale nozione di aciclicità è equivalente a quella di un ipergrafo conforme (ogni cricca del grafo originario è coperta da alcuni iperarchi) e avente grafo originario [[chordal graph|cordale]]; esso è anche equivalente alla riducibilità di un grafo vuoto tramite [[GYO algorithm]]<ref>C. T. Yu and M. Z. Özsoyoğlu. ''An algorithm for tree-query membership of a distributed query''. In Proc. IEEE COMPSAC, pages 306-312, 1979</ref><ref name="graham1979universal">M. H. Graham. ''On the universal relation''. Technical Report, University of Toronto, Toronto, Ontario, Canada, 1979</ref> (anche noto come algoritmo di Graham), un processo iterativo [[confluence (abstract rewriting)|confluente]] che rimuove gli iperarchi utilizzando una definizione generica di [[ear (graph theory)|ears]]. Entrando nel dominio della [[teoria delle basi di dati]], è noto che ununo [[schema di database]] gode di alcune desiderabili proprietà se l'ipergrafo sottostante è α-aciclico.<ref>[[Serge Abiteboul]], [[Richard B. Hull]], [[Victor Vianu]], ''Foundations of Databases''</ref> Inoltre, l'α-aciclicità è anche legata all'espressività del [[frammento custodito]] di [[logica del primo ordine]].

Si può provare verificare in [[tempo lineare]] se un ipergrafo sia α-aciclico.<ref>[[Robert Tarjan|R. E. Tarjan]], [[Mihalis Yannakakis|M. Yannakakis]]. ''Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs''. SIAM J. on Computing, 13(3):566-579, 1984.</ref>

Bisogna però far notarechenotare che l'α-aciclicità ha la seguente proprietà contro intuitiva: aggiungere iperarchi a un ipergrafo α-ciclico può renderlo α-aciclico (per esempio, aggiungere un iperarco contenente tutti i vertici dell'ipergrafo lo renderà sempre α-aciclico). Tale limite viene in parte motivato, [[Ronald Fagin]]<ref name="fagin1983degrees">[[Ronald Fagin]], ''Degrees of Acyclicity for Hypergraphs and Relational Database Schemes''</ref> definì le nozioni più forti di β-aciclicità e γ-aciclicità. Possiamo definire la β-aciclicità come il requisito affinché tutti i sottoipergrafi di un ipergrafo siano α-aciclici, che è equivalente<ref name="fagin1983degrees"/> a una precedente definizione di Graham.<ref name="graham1979universal"/> La nozione di γ-aciclicità è una condizione più restrittiva, che è equivalente a diverse proprietà desiderabili di uno schema di una base di dati ed è legato ai [[Diagramma di Bachman|diagrammi di Bachman]]. Sia β-aciclicità che γ-aciclicità possono essere esplorate in [[tempo polinomiale]].

Queste quattro nozioni di aciclicità possono essere confrontate: la Berge-aciclicità implica la γ-aciclicità che a sua volta implica la β-aciclicità che implica l'α-aciclicità. Tuttavia nessuna delle precedenti implicazioni può essere invertita, e pertanto sono considerate aciclitiàaciclicità differenti.<ref name="fagin1983degrees" />

== IsomorfismiMorfismi e uguaglianzaisomorfismi ==

Un ipergrafoomomorfismo [[omomorfo]]di ipergrafi è una associazione dall'insieme dei vertici di un ipergrafo a un altro, tale che ogni arco è associato a un altro arco.

Un ipergrafo <math>H=(X,E)</math> è '''isomorfo''' a un altro ipergrafo <math>G=(Y,F)</math>, scritto <math>H \simeq G</math>, se esiste una [[biezione]]

:<math>\phi:\colon X \to Y</math>

e una [[permutazione]] <math>\pi</math> di <math>I</math> tale che

:<math>\phi(e_i) = f_{\pi(i)}.</math>

La biezione <math>\phi</math> è in seguito chiamato [[isomorfismo]] dei grafi. Notare che

:<math>H \simeq G</math> se e solo se <math>H^* \simeq G^*</math>.

Quando gli archi di un ipergrafo sono esplicitamente marcati, si presenta la nozione di ''ismomorfismoisomorfismo forte''. Si dice che <math>H</math> è '''fortemente isomorfo''' a <math>G</math> se la permutazione è l'identità. Scritto:e si indica <math>H \cong G</math>. Un Naturalmenteisomorfismo unforte grafodi fortemente isomorfografi è anche un grafoisomorfismo di isomorfiografi, ma non viceversa.

Quando i vertici di un ipergrafo sono esplicitamente marcati, si presenta la nozione di ''equivalenza'', e anche di ''uguaglianza''. Si dice che <math>H</math> è '''equivalente''' a <math>G</math>, e si scrive <math>H\equiv G</math> se l'isomorfismo <math>\phi</math> ha

:<math>\phi(x_n) = y_n</math>

Riga 122 ⟶ 116:

e

:<math>\phi(e_i) = f_{\pi(i)}.</math>

Si noti che

:<math>H\equiv G</math> se e solo se <math>H^* \cong G^*.</math>

Se, in aggiunta, la permutazione <math>\pi</math> è l'identità, si dice che <math>H</math> eguagli <math>G</math>, e si scrive <math>H=G</math>. Si noti che, con tale definizione di uguaglianza, i grafi sono auto-duali

:<math>\left(H^*\right) ^* = H.</math>

Un [[automorfismo]] su un ipergrafo è un isomorfismo da un insieme di vertici a un altro, che è una rimarcatura di vertici. L'insieme di automorfismi di un ipergrafo ''H'' (= (''X'',&nbsp;''E'')) è un [[Gruppo (matematica)|gruppo]], chiamato [[gruppo di automorfismi]] di un ipergrafo, e scritto Aut(''H'').

===Esempi===

Riga 164 ⟶ 158:

In questo esempio, <math>H</math> e <math>G</math> sono equivalenti, <math>H\equiv G</math>, e i duali sono fortemente isomorfi <math>H^*\cong G^*</math>.

==Ipergrafi Simmetricisimmetrici==

Il rango <math>r(H)</math> di un hypergraphipergrafo <math>H</math> è la cardinalità massima che di un arco nell'ipergrafo. Se tutti gli archi hanno stessa cardinalità ''k'', l'ipergrafo viene detto '''uniforme''' o anche '''''k''-uniforme''', o anche chiamato '''''k''-ipergrafo'''. Un grafo sinel trattasenso diclassico può essere visto come un ipergrafo 2-uniforme.

Il grado ''d(v)'' di un vertice ''v'' è il numero di archi in cui è contenuto. Un ipergrafo ''H'' è '''''k''-regulare'''regolare se ogni vertice ha grado ''k''.

Il duale di un ipergrafo uniforme è regolare, e viceversa.

Due vertici ''x'' e ''y'' di ''H'' sono chiamati '''simmetrici''' se esiste un automorfismo tale che <math>\phi(x)=y</math>. Due archi <math>e_i</math> e <math>e_j</math> sono detti '''simmetrici''' se esiste un automorfismo tale che <math>\phi(e_i)=e_j</math>.

Un ipergrafo è detto '''vertice-transitivo''' (o '''vertice-simmetrico''') se tutti i suoi vertici sono simmetrici. Ne segue che un ipergrafo si dice '''arco-transitivo''' se tutti gli archi sono simmetrici. Se un ipergrafo è sia arco-simmetrico che vertice-simmetrico, allora l'ipergrafo si dice '''transitivo'''.

Data la dualità di un ipergrafo, lo studio della arco-transitività è collegato allo studio della vertice-transitività.

== Rappresentazione grafica di ipergrafi ==

Sebbene gli ipergrafi siano più difficili da rappresentare graficamente rispetto ai grafi, diversi ricercatori hanno studiato modi per visualizzare ipergrafi.

Una possibile rappresentazione visuale di ipergrafi, simile a quella standard in cui delle curve sul piano sono utilizzato per rappresentare gli archi, i vertici degli ipergrafi sono rappresentati come punti, dischi, rettangoli, e gli iperarchi sono alberi che hanno i vertici come foglie. Se i vertici sono rappresentati come punti, gli iperarchi possono essere curve che connettono insieme di punti, o curve chiuse che racchiudono insiemi di punti.

Un altro stile di visualizzazione degli ipergrafi, la suddivisione modella la rappresentazione dell'ipergrafo, il piano è suddiviso in regioni, ognuna delle quali rappresenta un singolo vertice dell'ipergrafo. Gli iperarchi dell'ipergrafo sono rappresentati da sottoinsiemi contigui di tali regioni, che possono essere rappresentati dal colore, da contorni intorno ad esse o da entrambi. Un [[diagramma di Venn]], ad esempio, può suddividere un ipergrafo in iperarchi (le curve chiuse definiscono il diagramma) e 2ⁿ - 1 vertici (rappresentati dalle regioni in cui queste curve suddividono il piano). Diversamente dal tempo polinomiale per riconoscere grafi planari, il suo tempo NP-completo per determinare in che modo un ipergrafo ha possa avere una suddivisione planare. L'esistenza di una rappresentazione di questo tipo può essere testato efficacemente quando il modello di adiacenza delle regioni è vincolato in un percorso, un ciclo o un albero.

Una rappresentazione alternativa dell'ipergrafo chiamata PAOH<ref name=":0" />, mostrata nella seconda figura di questo articolo. Gli archi sono linee verticali che collegano i vertici. I vertici sono allineati a sinistra. La legenda sulla destra mostra i nomi degli archi. Sebbene tale tecnica sia stato pensata per visualizzare gli ipergrafi dinamici, può essere utilizzata anche per gli ipergrafi semplici.

==Note==

Riga 182 ⟶ 185:

==Bibliografia==

* Claude Berge, "Hypergraphs: Combinatorics of finite sets". North-Holland, 1989.

* Claude Berge, Dijen Ray-Chaudhuri, "Hypergraph Seminar, Ohio State University 1972", ''Lecture Notes in Mathematics'' '''411''' Springer-Verlag

* {{springerEOM|titolo=Hypergraph|autore= }}

* Alain Bretto, "Hypergraph Theory: an Introduction", Springer, 2013.

* Vitaly I. Voloshin. "Coloring Mixed Hypergraphs: Theory, Algorithms and Applications". Fields Institute Monographs, American Mathematical Society, 2002.

* Vitaly I. Voloshin. "Introduction to Graph and Hypergraph Theory". Nova Science Publishers, Inc., 2009.

* {{PlanetMath|3508|Hypergraph}}

==Voci correlate==

* [[Grafo]]

* [[Greedoide]]

* [[Incidence structure]]

* [[Matroide]]

* [[Multigraph]]

* [[P system]]

* [[Sparse matrix-vector multiplication]]

== Altri progetti ==

{{Interprogetto}}

== Collegamenti esterni ==

{{Portale|matematica}}

* {{Collegamenti esterni}}

* {{PlanetMath|3508|Hypergraph}}

{{controllo di autorità}}

{{wPortale|matematica|aprile 2018}}

[[Categoria:Teoria dei grafi]]

[[de:Graph (Graphentheorie)#Hypergraph]]