Ipergrafo: differenze tra le versioni

Versione delle 16:17, 1 mag 2018

Versione delle 04:25, 5 mag 2018

Riga 12:

]]

In [[matematica]], un '''ipergrafo''' è un [[Grafo | 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>.

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.

Riga 87:

==Aciclicità==

In contrasto con ordinari grafi sconnessi per i quali esiste una singola nozione naturale di [[cycle (graph theory)|cicli]] e [[Forest (graph theory)|grafi aciclici]], esistono multiple definizioni non-equivalenti di aciclicità per ipergrafi che è in contrasto con l'ordinaria aciclicità dei grafi, nel caso particolare di grafi ordinari.

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 testata 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 un [[database schema]] goda di alcune desiderabili proprietà se l'ipergrafo sottostande è α-acyclic.<ref>[[Serge Abiteboul|S. Abiteboul]], [[Richard B. Hull|R. B. Hull]], [[Victor Vianu|V. Vianu]], ''Foundations of Databases''</ref> Besides, α-aciclicità è anche legata all'espressività del [[frammento custodito]] di [[logica di primo-ordine]].

Possiamo testare 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 notareche 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 [[diagrammi di Bachman]]. Sia β-aciclicità che γ-aciclicità possono essere testate in [[PTIME|tempo polinomiale]].

Queste quattro nozioni di aciclicità possono essere comparate: Berge-aciclicità implica γ-aciclicità che implica β-aciclicità che implica α-aciclicità. Tuttavia nessuna delle precedenti proprietà può essere applicata biettivamente, e pertanto considerate aciclitià differenti.<ref name="fagin1983degrees" />

== Isomorfismi e uguaglianza ==

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