Ipergrafo: differenze tra le versioni

Versione delle 19:37, 5 mag 2018

Versione delle 19:43, 5 mag 2018

Riga 77:

:<math>\left(H^*\right)^* = H.</math>

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 componentacomponente 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.

Riga 91:

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 indagata 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]] godagode di alcune desiderabili proprietà se l'ipergrafo sottostante è α-acyclicaciclico.<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]].

Si può provare 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>

Riga 112:

La biezione <math>\phi</math> è in seguito chiamato [[isomorfismo]] dei grafi. Notare che

:<math>H \simeq G</math> ifse ande only ifsolo se<math>H^* \simeq G^*</math>.

Quando gli archi di un ipergrafo sono esplicitamente marcati, si presenta la nozione di ''ismomorfismo forte''. Si dice che <math>H</math> è '''fortemente isomorfico''' a <math>G</math> se la permutazione è l'identità. Scritto: <math>H \cong G</math>. Naturalmente un grafo fortemennte isomorfico è anche un grafo isomorfico, ma non viceversa.