Ipergrafo

Da Wikipedia, l'enciclopedia libera.
Jump to navigation Jump to search
Un esempio di ipergrafo con e .

In matematica, un ipergrafo è un grafo in cui un arco può essere collegato a un qualunque numero di vertici. Formalmente, un ipergrafo è una coppia dove è un insieme di elementi chiamati nodi oppure vertici, e è un insieme formato da sottoinsiemi non vuoti chiamati iperarchi oppure archi. Pertanto, è un sottoinsieme di , dove è l' insieme potenza di .

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.

Un ipergrafo è anche chiamato insieme sistema o anche famiglia di insiemi presa da insieme universo X. La differenza tra un insieme sistema e un ipergrafo è una domanda che spesso sorge spontanea. La teoria degli ipergrafi tende ad occuparsi di questioni simili a quelle della teoria dei grafi, quali connettività e colorability, mentre la teoria degli insiemi tende ad occuparsi di domande di ambito non grafo-teorico, quali Sperner theory.

Esistono diverse definizioni; a volte gli archi non devono essere vuoti, e a volte archi multipli, con lo stesso insieme di noti, sono ammessi.

Gli ipergrafi possono essere visti come strutture incidenti. In particulare, esiste un "grafo incidente" biparito or "Levi graph" corrispondente a ogni ipergrafo, al contrario, la maggior parte, ma non tutti, dei grafi bipartiti possono essere considerati come grafi di incidenza, o ipergrafi.

Gli ipergrafi hanno tanti altri nomi. In geometria computazionale, un ipergrafo può a volte essere definito come range space, e gli iperarchi vengono chiamati ranges.[1] 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.[2]

Tra i casi particolari di vi sono : k-uniform ones, come precedentemente discusso; clutters, dove nessun arco appare come sottoinsieme di un altro arco; e complesso simpliciale astratto, che contiene tutti i sottoinsiemi di ogni arco.

La collezione di ipergrafi è una category, avente un ipergrafo omomorfo come morphisms.

Terminologia[modifica | modifica wikitesto]

Dato che i collegamenti degli ipergrafi possono avere una cardinalità qualsiasi, esistono diverse nozioni al concetto di sottografo, chiamato sottoipergrafo, ipergrafo parziale e sezione di ipergrafo.

Sia l'ipergrafo che consiste dei vertici

e avente come insieme arco

dove e sono gli insiemi indici dei vertici e degli archi, rispettivamente. Un sottoipergrafo è un ipergrafo con alcuni vertici rimossi. Formalmente, il sottoipergrafo indotto dal sottoinsieme di è definito come

Una estensione di un sottoipergrafo è un ipergrafo dove ogni iperarco di che è parzialmente contenuto nel sottoipergrafo è completamente contenuto dall'estensione . Formalmente, con e .

L' ipergrafo parziale è un ipergrafo con alcuni archi rimossi. Dato un sottoinsieme del set di indici dell'arco, l'ipergrafo parziale generato da è l'ipergrafo

Dato un sottoinsieme , la sezione dell'ipergrafo è l'ipergrafo parziale.

Il duale di è un ipergrafo i cui vertici e archi sono scambiati, tale che i vertici sono dati da e i cui archi sono dati da dove

Quando una nozione di uguaglianza è propriamente definite, come quella seguenta, l'operazione di prendere il duale di un ipergrafo è un'involuzione, i.e.,

Un grafo connesso G con lo stesso insieme vertice di un ipergrafo connesso H è un grafo ospite per H se ogni iperarco di H induce a un sottografo connesso in G. Per un ipergrafo disconnesso H, G è un grafo ospite se esiste una funzione biettiva tra le componenti connesse di G e di H, tale che ogni componente connessa G' di G è un ospite del corrispondente H'.

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.

La sezione-2 (o cricca, grafo di rappresentazione, grafo primale, grafo di Gaifman) di un ipergrafo è il grafo con gli stessi vertici dell'ipergrafo, e con gli archi tra tutte le coppie di vertici contenute nello stesso iperarco.

Modello di un grafo bipartito[modifica | modifica wikitesto]

Un ipergrafo H può essere rappresentato da un grafo bipartito BG come segue: gli insiemi X e E sono le partizioni di BG, e (x1, e1) sono connessi con un arco se e solo se il vertice x1 è contenuto nell'arco e1 in H. Contrariamente, ogni grafo bipartito con parti fissate e alcun nodo sconnesso nella seconda parte, rappresenta l'idea di ipergrafo appena descritta. Questo esempio di grafo bipartito viene anche chiamato grafo di incidenza.

Aciclicità[modifica | modifica wikitesto]

In contrasto con ordinari grafi sconnessi per i quali esiste una singola nozione naturale di cicli e 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:[3] 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 di vertici e alcune coppie di iperarchi tali che and , 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,[4] 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 cordale; esso è anche equivalente alla riducibilità di un grafo vuoto tramite GYO algorithm[5][6] (anche noto come algoritmo di Graham), un processo iterativo confluente che rimuove gli iperarchi utilizzando una definizione generica di ears. Entrando nel dominio della teoria delle basi di dati, è noto che un schema di database gode di alcune desiderabili proprietà se l'ipergrafo sottostante è α-aciclico.[7] 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.[8]

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[9] 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[9] a una precedente definizione di Graham.[6] 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 esplorate in tempo polinomiale.

Queste quattro nozioni di aciclicità possono essere confrontate: la Berge-aciclicità implica γ-aciclicità che a sua volta implica β-aciclicità che implica α-aciclicità. Tuttavia nessuna delle precedenti implicazioni può essere invertita, e pertanto sono considerate aciclitià differenti.[9]

Isomorfismi e uguaglianza[modifica | modifica wikitesto]

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

Un ipergrafo è isomorfo a un altro ipergrafo , scritto , se esiste una biezione

e una permutazione di tale che

La biezione è in seguito chiamato isomorfismo dei grafi. Notare che

se e solo se.

Quando gli archi di un ipergrafo sono esplicitamente marcati, si presenta la nozione di ismomorfismo forte. Si dice che è fortemente isomorfo a se la permutazione è l'identità. Scritto: . Naturalmente un grafo fortemente isomorfo è anche un grafo isomorfio, ma non viceversa.

Quando i vertici di un ipergrafo sono esplicitamente marcati, si presenta la nozione di equivalenza, e anche di uguaglianza. Si dice che è equivalente a , e si scrive se l'isomorfismo ha

e

Si noti che

se e solo se

Se, in aggiunta, la permutazione è l'identità, si dice che eguagli , e si scrive . Si noti che, con tale definizione di uguaglianza, i grafi sono auto-duali

Un automorfismo su un ipergrafo è un isomorfismo da un insieme di vertici a un altro, che è una rimarcatura di vertici. L'insieme di automorfismi di un ipergrafo H (= (XE)) è un gruppo, chiamato gruppo di automorfismi di un ipergrafo, e scritto Aut(H).

Esempi[modifica | modifica wikitesto]

Si consideri l'ipergrafo con archi

e

Chiaramente e sono isomorfi (con , etc.), ma non sono fortemente isomorfi. Quindi, per esempio, in , il vertice incontra gli archi 1, 4 e 6, così che

Nel grafo , non esiste alcun vertice che incontri gli archi 1, 4 e 6:

In questo esempio, e sono equivalenti, , e i duali sono fortemente isomorfi .

Ipergrafi Simmetrici[modifica | modifica wikitesto]

Il rango di un hypergraph è la cardinalità massima che di un arco nell'ipergrafo. Se tutti gli archi hanno stessa cardinalità k, l'ipergrafo viene detto uniforme o anche k-uniforme, o anche chiamato k-ipergrafo. Un grafo si tratta di un ipergrafo 2-uniforme.

Il grado d(v) di un vertice v è il numero di archi in cui è contenuto. H è k-regulare se ogni vertice ha grado k.

Il duale di un ipergrafo uniforme è regolare, e viceversa

Due vertici x e y di H sono chiamati simmetrici se esiste un automorfismo tale che . Due archi e sono detti simmetrici se esiste un automorfismo tale che .

Un ipergrafo è detto vertice-transitivo (o vertice-simmetrico) se tutti i suoi vertici sono simmetrici. Ne segue che un ipergrafo si dice arco-transitivo se tutti gli archi sono simmetrici. Se un ipergrafo è sia arco-simmetrico che vertice-simmetrico, allora l'ipergrafo si dice transitivo.

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

Note[modifica | modifica wikitesto]

  1. ^ David Haussler e Emo Welzl, ε-nets and simplex range queries, in Discrete and Computational Geometry, vol. 2, nº 2, 1987, pp. 127–151, DOI:10.1007/BF02187876, MR 884223..
  2. ^ Judea Pearl, in HEURISTICS Intelligent Search Strategies for Computer Problem Solving, Addison Wesley (1984), p. 25.
  3. ^ Claude Berge, Graphs and Hypergraphs
  4. ^ C. Beeri, R. Fagin, D. Maier, M. Yannakakis, On the Desirability of Acyclic Database Schemes
  5. ^ 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
  6. ^ a b M. H. Graham. On the universal relation. Technical Report, University of Toronto, Toronto, Ontario, Canada, 1979
  7. ^ Serge Abiteboul, Richard B. Hull, Victor Vianu, Foundations of Databases
  8. ^ R. E. Tarjan, 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.
  9. ^ a b c Ronald Fagin, Degrees of Acyclicity for Hypergraphs and Relational Database Schemes

Bibliografia[modifica | modifica wikitesto]

  • Claude Berge, "Hypergraphs: Combinatorics of finite sets". North-Holland, 1989.
  • Claude Berge, Dijen Ray-Chaudhuri, "Hypergraph Seminar, Ohio State University 1972", Lecture Notes in Mathematics 411 Springer-Verlag
  • (EN) Hypergraph, in Encyclopaedia of Mathematics, Springer e European Mathematical Society, 2002.
  • Alain Bretto, "Hypergraph Theory: an Introduction", Springer, 2013.
  • Vitaly I. Voloshin. "Coloring Mixed Hypergraphs: Theory, Algorithms and Applications". Fields Institute Monographs, American Mathematical Society, 2002.
  • Vitaly I. Voloshin. "Introduction to Graph and Hypergraph Theory". Nova Science Publishers, Inc., 2009.
  • (EN) Hypergraph, in PlanetMath.

Voci correlate[modifica | modifica wikitesto]

Altri progetti[modifica | modifica wikitesto]

Matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica
Controllo di autoritàLCCN (ENsh85063697 · GND (DE4161063-5 · BNF (FRcb119790981 (data)