Utente:Mazzespazze/Ipergrafo

An example of a hypergraph, with $X=\{v_{1},v_{2},v_{3},v_{4},v_{5},v_{6},v_{7}\}$ and $E=\{e_{1},e_{2},e_{3},e_{4}\}=$ $\{\{v_{1},v_{2},v_{3}\},$ $\{v_{2},v_{3}\},$ $\{v_{3},v_{5},v_{6}\},$ $\{v_{4}\}\}$.

In matematica, un ipergrafo è un grafo in cui un arco può essere legato a un qualunque numero di vertici. Formalmente, un ipergrafo $H$ è una coppia $H=(X,E)$ dove $X$ è un insieme di elementi chiamati nodi oppure vertici, e $E$ è un insieme formato da sottoinsiemi non vuoti $X$ chiamati iperarchi oppure archi. Pertanto, $E$ è un sottoinsieme di ${\mathcal {P}}(X)\setminus \{\emptyset \}$, dove ${\mathcal {P}}(X)$ è l' insieme potenza di $X$.

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 studio 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 o "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. 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.

Casi particolari di ipergrafi includono: k-uniform ones, come precedentemente discusso; clutters, dove nessun arco appare come sottoinsieme di un altro arco; e abstract simplicial complexes, che contiene tutti i sottoinsiemi di ogni arco.

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

Terminologia

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 $H=(X,E)$ l'ipergrafo che consiste dei vertici

$X=\lbrace x_{i}|i\in I_{v}\rbrace ,$

e avente come insieme arco

$E=\lbrace e_{i}|i\in I_{e},e_{i}\subseteq X\rbrace ,$

dove $I_{v}$ e $I_{e}$ sono gli insiemi indici dei vertici e degli archi, rispettivamente. Un sottoipergrafo è un ipergrafo con alcuni vertici rimossi. Formalmente, il sottoipergrafo $H_{A}$ indotto dal sottoinsieme $A$ di $X$ è definito come

$H_{A}=\left(A,\lbrace e_{i}\cap A|e_{i}\cap A\neq \varnothing \rbrace \right).$

Una estensione di un sottoipergrafo è un ipergrafo dove ogni iperarco di $H$ che è parzialmente contenuto nel sottoipergrafo $H_{A}$ è completamente contenuto dall'estensione $Ex(H_{A})$. Formalmente, $Ex(H_{A})=(A\cup A',E')$ con $A'=\cup _{e\in E}e\setminus A$ e $E'=\lbrace e\in E|e\subseteq (A\cup A')\rbrace$.

L' ipergrafo parziale è un ipergrafo con alcuni archi rimossi. Dato un sottoinsieme $J\subset I_{e}$ del set di indici dell'arco, l'ipergrafo parziale generato da $J$ è l'ipergrafo

$\left(X,\lbrace e_{i}|i\in J\rbrace \right).$

Dato un sottoinsieme $A\subseteq X$, la sezione dell'ipergrafo è l'ipergrafo parziale.

$H\times A=\left(A,\lbrace e_{i}|i\in I_{e},e_{i}\subseteq A\rbrace \right).$

Il duale $H^{*}$ di $H$ è un ipergrafo i cui vertici e archi sono scambiati, tale che i vertici sono dati da $\lbrace e_{i}\rbrace$ e i cui archi sono dati da $\lbrace X_{m}\rbrace$ dove

$X_{m}=\lbrace e_{i}|x_{m}\in e_{i}\rbrace .$

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

$\left(H^{*}\right)^{*}=H.$

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 componenta connessa G' di G è un ospite del corrispondente H'.

A ipergrafo bipartito se e solo se i suoi vertici possono essere partiti 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

Un ipergrafo H può essere rappresentato da un grafo bipartito BG come segue: gli insiemi X e E sono le partizioni di BG, e (x₁, e₁) sono connessi con un arco se e solo se il vertice x₁ è contenuto nell'arco e₁ 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à

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: 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 $v\neq v'$ di vertici e alcune coppie $f\neq f'$ di iperarchi tali che $v,v'\in f$ and $v,v'\in f'$, 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, 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 (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 database schema goda di alcune desiderabili proprietà se l'ipergrafo sottostande è α-acyclic. Besides, α-aciclicità è anche legata all'espressività del frammento custodito di logica di primo-ordine.

Possiamo testare in tempo lineare se un ipergrafo sia α-aciclico.

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 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 a una precedente definizione di Graham. 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 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.

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.

Un ipergrafo $H=(X,E)$ è isomorfico a un altro ipergrafo $G=(Y,F)$, scritto $H\simeq G$, se esiste una biezione

$\phi :X\to Y$

e una permutazione $\pi$ di $I$ tale che

$\phi (e_{i})=f_{\pi (i)}$

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

$H\simeq G$ if and only if $H^{*}\simeq G^{*}$.

Quando gli archi di un ipergrafo sono esplicitamente marcati, si presenta la nozione di ismomorfismo forte. Si dice che $H$ è fortemente isomorfico a $G$ se la permutazione è l'identità. Scritto: $H\cong G$. Naturalmente un grafo fortemennte isomorfico è anche un grafo isomorfico, 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 $H$ sia equivalente a $G$, e si scrive $H\equiv G$ se l'isomorfismo $\phi$ ha

$\phi (x_{n})=y_{n}$

e

$\phi (e_{i})=f_{\pi (i)}$

Si noti che

$H\equiv G$ se e solo se $H^{*}\cong G^{*}$

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

$\left(H^{*}\right)^{*}=H$

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 (= (X, E)) è un gruppo, chiamato gruppo automorfico di un ipergrafo, e scritto Aut(H).

Esempi

Considera l'ipergrafo $H$ con archi

$H=\lbrace e_{1}=\lbrace a,b\rbrace ,e_{2}=\lbrace b,c\rbrace ,e_{3}=\lbrace c,d\rbrace ,e_{4}=\lbrace d,a\rbrace ,e_{5}=\lbrace b,d\rbrace ,e_{6}=\lbrace a,c\rbrace \rbrace$

e

$G=\lbrace f_{1}=\lbrace \alpha ,\beta \rbrace ,f_{2}=\lbrace \beta ,\gamma \rbrace ,f_{3}=\lbrace \gamma ,\delta \rbrace ,f_{4}=\lbrace \delta ,\alpha \rbrace ,f_{5}=\lbrace \alpha ,\gamma \rbrace ,f_{6}=\lbrace \beta ,\delta \rbrace \rbrace$

Chiaramente $H$ e $G$ sono isomorfici (con $\phi (a)=\alpha$, etc.), ma non sono fortemente isomorfici. Quindi, per esempio, in $H$, il vertice $a$ incontra gli archi 1, 4 e 6, così che

$e_{1}\cap e_{4}\cap e_{6}=\lbrace a\rbrace$

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

$f_{1}\cap f_{4}\cap f_{6}=\varnothing$

In questo esempio, $H$ e $G$ sono equivalenti, $H\equiv G$, e i duali sono fortemente isomorfici $H^{*}\cong G^{*}$.

Ipergrafi Simmetrici

Il rank $r(H)$ di un ipergrafo $H$ è 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 $\phi (x)=y$. Due archi $e_{i}$ e $e_{j}$ sono detti simmetrici se esiste un automorfismo tale che $\phi (e_{i})=e_{j}$.

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

Secante

La secante (o "hitting set") di un ipergrafo H = (X, E) è un insieme $T\subseteq X$ che ha intersezioni non vuote con ogni arco. Una secante S è detta minimale se nessun sottoinsieme proprio di S è una secante. La secante di un ipergrafo H è l'ipergrafo (X, F) il cui insieme di archi F consiste di tutte le secanti minimali di H.

Calcolare la secante di un ipergrafo ha diverse applicazioni nell'ottimizzazione combinatoriale, nella teoria dei giochi, e in altre diverse aree dell'informatica quali machine learning, indicizzazione di basi di dati, problema di soffisfacibilità, data mining, e ottimizzazione di programmi.

Matrice di incidenza

Sia $V=\{v_{1},v_{2},~\ldots ,~v_{n}\}$ e $E=\{e_{1},e_{2},~\ldots ~e_{m}\}$. Ogni ipergrafo ha una $n\times m$ matrice di incidenza $A=(a_{ij})$ dove

$a_{ij}=\left\{{\begin{matrix}1&\mathrm {if} ~v_{i}\in e_{j}\\0&\mathrm {otherwise} .\end{matrix}}\right.$

La trasposta $A^{t}$ della matrice di incidenza definisce un ipergrafo $H^{*}=(V^{*},\ E^{*})$ detto duale di $H$, dove $V^{*}$ è un insieme m-elemento e $E^{*}$ è un insieme n-elementodi sottoinsiemi di $V^{*}$. Per $v_{j}^{*}\in V^{*}$ e $e_{i}^{*}\in E^{*},~v_{j}^{*}\in e_{i}^{*}$ se e solo se $a_{ij}=1$.

Colorazione

La colorazione classica di un ipergrafo prevede l'assegnamento di uno dei colori dall'insieme $\{1,2,3,...\lambda \}$ ad ogni vertice di un ipergrafo in modo tale che ogni iperarco contenga almeno due vertici di colori distinti. In altre parole, non esiste alcun iperarco monocromatico con cardinalità almeno 2. In tal senso si tratta di una generalizzazione diretta di una colorazione di un grafo. Il numero minimo di colori distinti da utilizzare, tra tutti i colori, viene definito come numero cromatico di un ipergrafo.

Gli ipergrafi per cui esiste una colorazione usando fino a k colori, sono riferiti come k-colorabili. Gli ipergrafi 2-colorabili sono i bipartiti.

Esistono diverse generalizzazione di colorazione classica di ipergrafi. Una di queste è la così chiamata colorazione di ipergrafo mista, ossia quando sono ammessi archi monocromatici. Alcuni ipergrafi misti sono non-colorabili per nessun numero di colori. Di fatto un criterio generale per l'incolorabilità non è noto. Quando un ipergrafo misto è colorabile, allora il numero minimo e massimo di colori utilizzati sono chiamati rispettivamente minorante e maggiorante cromatici. Per ulteriori dettagli http://spectrum.troy.edu/voloshin/mh.html.

Voci correlate

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file su Mazzespazze/Ipergrafo
• Grafo
• Greedoide
• Strutture incidenti
• Matroide
• Multigrafo
• Sistema P

Bibliografia

• 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
• Template:Springer
• 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.
• Template:PlanetMath attribution