Ipergrafo: differenze tra le versioni

Versione delle 01:32, 13 ott 2023

Versione attuale delle 15:13, 17 mar 2025

(2 versioni intermedie di 2 utenti non mostrate)

Riga 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–11-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\{\varnothing\}</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''-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 [[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 [[Colorazione dei grafi|colorabilità]], mentre la [[teoria degli insiemi]] tende a occuparsi di domande non inerenti alla teoria dei grafi, quali la [[Teorema di Sperner|teoria di Sperner]].

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

Riga 27:

|rivista= [[Discrete and Computational Geometry]]

| mr = 884223

|pp= 127–151127-151

|titolo= ε-nets and simplex range queries

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

Riga 73:

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.

Riga 176:

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.