Ipergrafo: differenze tra le versioni

Versione delle 15:56, 8 giu 2021

Versione delle 16:01, 8 giu 2021

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 reguiniregioni, 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.