Топ-100
Indietro

ⓘ Ipergrafo. In matematica, un ipergrafo è un grafo in cui un arco può essere collegato a un qualunque numero di vertici. Formalmente, un ipergrafo H {\displaysty ..




Ipergrafo
                                     

ⓘ Ipergrafo

In matematica, un ipergrafo è un grafo in cui un arco può essere collegato a un qualunque numero di vertici. Formalmente, un ipergrafo H {\displaystyle H} è una coppia H = {\displaystyle H=} dove X {\displaystyle X} è un insieme di elementi chiamati nodi oppure vertici, E {\displaystyle E} è un insieme formato da sottoinsiemi non vuoti X {\displaystyle X} chiamati iperarchi oppure archi. Pertanto, E {\displaystyle E} è un sottoinsieme di P ∖ { ∅ } {\displaystyle {\mathcal {P}}\setminus \{\emptyset \}}, dove P {\displaystyle {\mathcal {P}}} è l insieme potenza di X {\displaystyle 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 ipergrafi dove tutti gli iperarchi hanno la stessa cardinalità; un ipergrafo k-uniforme è un ipergrafo in cui tutti gli iperarchi hanno grandezza k. 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. 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.

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 categoria, avente un ipergrafo omomorfo come morfismo.

                                     

1. 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 {\displaystyle H=X,E} lipergrafo che consiste dei vertici

X = { x i | i ∈ I v }, {\displaystyle X=\lbrace x_{i}|i\in I_{v}\rbrace,}

e avente come insieme arco

E = { e i | i ∈ I e, e i ⊆ X }, {\displaystyle E=\lbrace e_{i}|i\in I_{e},e_{i}\subseteq X\rbrace,}

dove I v {\displaystyle I_{v}} e I e {\displaystyle 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 {\displaystyle H_{A}} indotto dal sottoinsieme A {\displaystyle A} di X {\displaystyle X} è definito come

H A = A, { e i ∩ A | e i ∩ A ≠ ∅ }. {\displaystyle H_{A}=\leftA,\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 {\displaystyle H} che è parzialmente contenuto nel sottoipergrafo H A {\displaystyle H_{A}} è completamente contenuto dallestensione E x H A {\displaystyle ExH_{A}}. Formalmente, E x H A = A ∪ A ′, E ′ {\displaystyle ExH_{A}=A\cup A,E} con A ′ = ∪ e ∈ e ∖ A {\displaystyle A=\cup _{e\in E}e\setminus A} E ′ = { e ∈ E | e ⊆ A ∪ A ′ } {\displaystyle E=\lbrace e\in E|e\subseteq A\cup A\rbrace }.

Lipergrafo parziale è un ipergrafo con alcuni archi rimossi. Dato un sottoinsieme J ⊂ I e {\displaystyle J\subset I_{e}} del set di indici dellarco, lipergrafo parziale generato da J {\displaystyle J} è lipergrafo

X, { e i | i ∈ J }. {\displaystyle \leftX,\lbrace e_{i}|i\in J\rbrace \right.}

Dato un sottoinsieme A ⊆ X {\displaystyle A\subseteq X}, la sezione dellipergrafo è lipergrafo parziale.

H × A =. {\displaystyle H\times A=\leftA,\lbrace e_{i}|i\in I_{e},e_{i}\subseteq A\rbrace \right.}

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

X m = { e i | x m ∈ e i }. {\displaystyle X_{m}=\lbrace e_{i}|x_{m}\in e_{i}\rbrace.}

Quando una nozione di uguaglianza è propriamente definite, come quella seguenta, loperazione di prendere il duale di un ipergrafo è uninvoluzione, i.e.,

H ∗ ∗ = H. {\displaystyle \leftH^{*}\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 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 di un ipergrafo è il grafo con gli stessi vertici dellipergrafo, e con gli archi tra tutte le coppie di vertici contenute nello stesso iperarco.

                                     

2. Modello di un grafo bipartito

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

                                     

3. 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 lordinaria 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 ≠ v ′ {\displaystyle v\neq v} di vertici e alcune coppie f ≠ f ′ {\displaystyle f\neq f} di iperarchi tali che v, v ′ ∈ f {\displaystyle v,v\in f} and v, v ′ ∈ f ′ {\displaystyle v,v\in f}, 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, 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 schema di database gode di alcune desiderabili proprietà se lipergrafo sottostante è α-aciclico. Inoltre, α-aciclicità è anche legata allespressività del frammento custodito di logica del primo ordine.

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



                                     

4. Isomorfismi e uguaglianza

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

Un ipergrafo H = X, E {\displaystyle H=X,E} è isomorfo a un altro ipergrafo G = Y, F {\displaystyle G=Y,F}, scritto H ≃ G {\displaystyle H\simeq G}, se esiste una biezione

ϕ: X → Y {\displaystyle \phi:X\to Y}

e una permutazione π {\displaystyle \pi } di I {\displaystyle I} tale che

ϕ e i = f π i {\displaystyle \phi e_{i}=f_{\pi i}}

La biezione ϕ {\displaystyle \phi } è in seguito chiamato isomorfismo dei grafi. Notare che

H ≃ G {\displaystyle H\simeq G} se e solo se H ∗ ≃ G ∗ {\displaystyle H^{*}\simeq G^{*}}.

Quando gli archi di un ipergrafo sono esplicitamente marcati, si presenta la nozione di ismomorfismo forte. Si dice che H {\displaystyle H} è fortemente isomorfo a G {\displaystyle G} se la permutazione è lidentità. Scritto: H ≅ G {\displaystyle H\cong G}. 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 H {\displaystyle H} è equivalente a G {\displaystyle G}, e si scrive H ≡ G {\displaystyle H\equiv G} se lisomorfismo ϕ {\displaystyle \phi } ha

ϕ x n = y n {\displaystyle \phi x_{n}=y_{n}}

e

ϕ e i = f π i {\displaystyle \phi e_{i}=f_{\pi i}}

Si noti che

H ≡ G {\displaystyle H\equiv G} se e solo se H ∗ ≅ G ∗ {\displaystyle H^{*}\cong G^{*}}

Se, in aggiunta, la permutazione π {\displaystyle \pi } è lidentità, si dice che H {\displaystyle H} eguagli G {\displaystyle G}, e si scrive H = G {\displaystyle H=G}. Si noti che, con tale definizione di uguaglianza, i grafi sono auto-duali

H ∗ ∗ = H {\displaystyle \leftH^{*}\right^{*}=H}

Un automorfismo su un ipergrafo è un isomorfismo da un insieme di vertici a un altro, che è una rimarcatura di vertici. Linsieme di automorfismi di un ipergrafo H = X, E) è un gruppo, chiamato gruppo di automorfismi di un ipergrafo, e scritto AutH.

                                     

4.1. Isomorfismi e uguaglianza Esempi

Si consideri lipergrafo H {\displaystyle H} con archi

H = { e 1 = { a, b }, e 2 = { b, c }, e 3 = { c, d }, e 4 = { d, a }, e 5 = { b, d }, e 6 = { a, c } } {\displaystyle 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 }

e

G = { f 1 = { α, β }, f 2 = { β, γ }, f 3 = { γ, δ }, f 4 = { δ, α }, f 5 = { α, γ }, f 6 = { β, δ } } {\displaystyle 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 }

Chiaramente H {\displaystyle H} e G {\displaystyle G} sono isomorfi con ϕ a = α {\displaystyle \phi a=\alpha }, etc), ma non sono fortemente isomorfi. Quindi, per esempio, in H {\displaystyle H}, il vertice a {\displaystyle a} incontra gli archi 1, 4 e 6, così che

e 1 ∩ e 4 ∩ e 6 = { a } {\displaystyle e_{1}\cap e_{4}\cap e_{6}=\lbrace a\rbrace }

Nel grafo G {\displaystyle G}, non esiste alcun vertice che incontri gli archi 1, 4 e 6:

f 1 ∩ f 4 ∩ f 6 = ∅ {\displaystyle f_{1}\cap f_{4}\cap f_{6}=\varnothing }

In questo esempio, H {\displaystyle H} e G {\displaystyle G} sono equivalenti, H ≡ G {\displaystyle H\equiv G}, e i duali sono fortemente isomorfi H ∗ ≅ G ∗ {\displaystyle H^{*}\cong G^{*}}.

                                     

5. Ipergrafi Simmetrici

Il rango r H {\displaystyle rH} di un hypergraph H {\displaystyle H} è la cardinalità massima che di un arco nellipergrafo. Se tutti gli archi hanno stessa cardinalità k, lipergrafo viene detto uniforme o anche k -uniforme, o anche chiamato k -ipergrafo. Un grafo si tratta di un ipergrafo 2-uniforme.

Il grado dv di un vertice v è il numero di archi in cui è contenuto. H è k -regolare 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 ϕ x = y {\displaystyle \phi x=y}. Due archi e i {\displaystyle e_{i}} e j {\displaystyle e_{j}} sono detti simmetrici se esiste un automorfismo tale che ϕ e i = e j {\displaystyle \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 lipergrafo si dice transitivo.

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



                                     

6. Rappresentazione grafica di ipergrafi

Sebbene gli ipergrafi siano più difficili da rappresentare graficamente rispetto ai grafi, diversi ricercatori hanno studiato modi per visualizzare ipergrafi.

Una possibile rappresentazione visuale di ipergrafi, simile a quella standard in cui delle curve sul piano sono utilizzato per rappresentare gli archi, i vertici degli ipergrafi sono rappresentati come punti, dischi, rettangoli, e gli iperarchi sono alberi che hanno i vertici come foglie. Se i vertici sono rappresentati come punti, gli iperarchi possono essere curve che connettono insieme di punti, o curve chiuse che racchiudono insiemi di punti.

Un altro stile di visualizzazione degli ipergrafi, la suddivisione modella la rappresentazione dellipergrafo, il piano è suddiviso in reguini, ognuna delle quali rappresenta un singolo vertice dellipergrafo. Gli iperarchi dellipergrafo sono rappresentati da sottoinsiemi contigui di tali regioni, che possono essere rappresentati dal colore, da contorni intorno ad esse o da entrambi. Un diagramma di Venn, ad esempio, può suddivere un ipergrafo in iperarchi le curve chiuse definiscono il diagramma e 2 n - 1 vertici rappresentati dalle regioni in cui queste curve suddividono il piano. Diversamente dal tempo polinomiale per riconoscere grafi planari, il suo tempo NP-completo per determinare in che modo un ipergrafo ha possa avere una suddivisione planare. Lesistenza di una rappresentazione di questo tipo può essere testato efficacemente quando il modello di adiacenza delle regioni è vincolato in un percorso, un ciclo o un albero.

Una rappresentazione alternativa dellipergrafo chiamata PAOH, mostrata nella seconda figura di questo articolo. Gli archi sono linee verticali che collegano i vertici. I vertici sono allineati a sinistra. La legenda sulla destra mostra i nomi degli archi. Sebbene tale tecnica sia stato pensata per visualizzare gli ipergrafi dinamici, può essere utilizzata anche per gli ipergrafi semplici.

                                     
  • L ipergrafia è una condizione comportamentale caratterizzata dall intenso desiderio di scrivere e o disegnare. Le forme di ipergrafia possono variare
  • di componenti artistici diversi. Nelle sue rappresentazioni - definite ipergrafie - la moda, la pittura, la scultura e la fotografia si mescolano in libertà
  • Erdős e Hanani sull impacchettamento degli ipergrafi lo sviluppo del lemma di regolarità degli ipergrafi insieme a Brendan Nagle, Mathias Schacht e
  • la dissertazione sulla generalizzazione del lemma di regolarità degli ipergrafi proposto da Endre Szemerédi. Dopo il PhD, collaborò come ricercatore e
  • rappresentazioni geometriche e di intersezione ecc. 05C63 grafi infiniti 05C65 ipergrafi 05C69 insiemi dominanti, insiemi indipendenti, cricche 05C70 fattorizzazione
  • prestazioni HyperGraphDB - un database a grafo open source LPGL che supporta ipergrafi generalizzati dove gli archi possono puntare ad altri archi HyperGraphDB
  • Covering teoria dei grafi Hitting set, una naturale generalizzazione per ipergrafi Altri progetti Wikimedia Commons Wikimedia Commons contiene immagini
  • termine che inventarono per questo tipo di scrittura è ipergrafia Un primo esempio di ipergrafia è il dipinto del 1951 Sans Titre di Gabriel Pomerand
  • dalle suggestioni delle teorie insiemistiche, la calligrafia orientale, l ipergrafia lettrista e la scrittura musicale. Sempre lontana dalle mode come dagli
  • Grafi planari  Colorazione dei grafi e teorema dei quattro colori Ipergrafi Grafi e gruppi  Digrafo  Flussi nei grafi  Passeggiate a caso sui
  • Grafi planari  Colorazione dei grafi e teorema dei quattro colori Ipergrafi Grafi e gruppi  Digrafo  Flussi nei grafi  Passeggiate a caso sui
  • Grafi planari  Colorazione dei grafi e teorema dei quattro colori Ipergrafi Grafi e gruppi  Digrafo  Flussi nei grafi  Passeggiate a caso sui