Ipergrafo: differenze tra le versioni

Versione delle 18:45, 21 giu 2019

Versione delle 20:48, 28 ott 2019

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–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\{\emptyset\}</math>, dove <math>\mathcal{P}(X)</math> è l' [[insieme potenza]] di <math>X</math>.

Riga 174:

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

== Rappresentazone 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 reguini, 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ò suddivere 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==