Ipergrafo: differenze tra le versioni

Versione delle 19:20, 5 mag 2018

Versione delle 19:29, 5 mag 2018

Riga 35:

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''' o '''connettori'''.<ref>Judea Pearl, in ''HEURISTICS Intelligent Search Strategies for Computer Problem Solving'', Addison Wesley (1984), p. 25.</ref>

CasiTra i casi particolari di ipergrafivi sono includono: [[Hypergraph#Symmetric hypergraphs|''k''-uniform ones]], come precedentemente discusso; [[clutter (mathematics)|clutter]]s, dove nessun arco appare come sottoinsieme di un altro arco; e [[abstract simplicial complex]]es, che contiene tutti i sottoinsiemi di ogni arco.

La collezione di ipergrafi è una [[Category (mathematics)|category]], avente un ipergrafo [[omomorfo]] come [[morphism]]s.

Riga 89:

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

PossiamoSi può provare 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 [[Diagramma di Bachman|diagrammi di Bachman]]. Sia β-aciclicità che γ-aciclicità possono essere testateesplorate in [[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" />