Hypergraph

Gli ipergrafi sono oggetti matematici che generalizzano il concetto grafico . Sono stati chiamati così da Claude Berge negli anni '60.

Gli ipergrafi generalizzano la nozione di grafo non orientato nel senso che i bordi non connettono più uno o due vertici, ma un numero qualsiasi di vertici (compreso tra uno e il numero di vertici dell'ipergrafo).

Alcuni teoremi della teoria dei grafi sono naturalmente generalizzati agli ipergrafi, per esempio il teorema di Ramsey .

Gli ipergrafi vengono gestiti in tutte le aree in cui viene utilizzata la teoria dei grafi: risoluzione dei problemi di soddisfazione dei vincoli , elaborazione delle immagini, ottimizzazione delle architetture di rete, modellazione , ecc.

Definizioni

Hypergraph

Un ipergrafo è una coppia che è impostato non vuota (solitamente finito) ed è una famiglia di parti non vuoto . $H$ $(V, E)$ ${\ displaystyle V = \ {v_ {1}, v_ {2}, ..., v_ {n} \}}$ ${\ displaystyle E = E_ {1}, E_ {2}, ..., E_ {m}}$ $V$

Come i grafici, diciamo che:

Gli elementi di sono i vertici di . $V$ $H$
Il numero di vertici è l' ordine dell'ipergrafo. $non$
Gli elementi di sono i bordi di . $E$ $H$

Gli ipergrafi corrispondono precisamente a matrici con coefficienti 0 o 1 (ciascuna delle quali ha almeno un 1). In effetti, qualsiasi ipergrafo corrisponde in modo univoco alla matrice come: $H$ ${\ displaystyle {\ mathcal {A}} _ {n, m} \,}$

{\ displaystyle \ forall a_ {i, j} \ in {\ mathcal {A}}, \ quad a_ {i, j} = {\ begin {cases} 1 & {\ text {si}} ~ v_ {i} \ in E_ {j} \\ 0 & {\ text {altrimenti}} \ end {case}}}

Ipergrafo uniforme

Tra le "nuove" proprietà degli ipergrafi rispetto ai grafici ci sono due concetti associati.

Chiamiamo il rango di un ipergrafo il numero massimo di vertici di uno spigolo: ${\ displaystyle \ operatorname {rang} (H) = \ max _ {i \ in \ {1, \ ldots, m \}} | E_ {i} |}$ Il grado di un ipergrafo è aumentato dal suo ordine. Se , allora è un grafico . ${\ displaystyle \ mathrm {rank} (H) = 2}$ $H$
Chiamiamo anti-rango di un ipergrafo il numero minimo di vertici di uno spigolo: ${\ Displaystyle \ operatorname {anti-rang} (H) = \ min _ {i \ in \ {1, \ ldots, m \}} | E_ {i} |}$

Per definizione di un ipergrafo, gli spigoli sono parti non vuote dell'insieme dei vertici dell'ipigrafo. L'anti-rango di un ipergrafo è quindi diverso da zero.

Si dice che un ipergrafo sia uniforme quando il suo rango e il suo antirango sono uguali.

Parliamo anche di ipergrafo r-uniforme per denotare un ipergrafo uniforme di rango . $r$

Esempio: l'ipergrafo dell'aereo di Fano

L'ipergrafo del piano di Fano ha sette vertici chiamati punti {0,1,2,3,4,5,6} e sette bordi chiamati rette (013, 045, 026, 124, 346, 325, 516). L'ordine (numero di vertici) è 7.

La riga e l'anti-riga sono uguali a 3 (numero di vertici di uno spigolo). Pertanto, l'ipergrafo dell'aereo di Fano è un ipergrafo a 3 uniformi.

Ipergrafo parziale e subipergrafo

Come i grafici, diciamo che:

Un ipergrafo parziale di un ipergrafo è tale che: ${\ displaystyle H_ {p} = (V, E_ {p})}$ ${\ displaystyle H = (V, E)}$ ${\ displaystyle E_ {p} \ subset E}$ .
Un sottoipergrafo di un ipergrafo è tale che: H′=(V′,E′){\ displaystyle H '= (V', E ')} $H '= (V', E ')$ H=(V,E){\ displaystyle H = (V, E)} ${\ displaystyle H = (V, E)}$
- ${\ displaystyle V '\ subseteq V}$ e
- ${\ displaystyle \ forall E_ {i} \ in E ', \ quad E_ {i} \ subseteq V' \ land E_ {i} \ in E}$ .

Queste nozioni generalizzano le nozioni di grafo parziale e sottografo alla teoria degli ipergrafi.

Semplice ipergrafo

Come i grafici (non orientati), diciamo che un ipergrafo è semplice se non ha più bordi (vedi articolo grafico semplice ).

Chiamiamo la famiglia di Sperner (o disordine in inglese) un semplice ipergrafo il cui nessun bordo è contenuto in un altro.

Doppio ipergrafo

O tale che . ${\ displaystyle V ^ {*} = \ {V_ {j} \ mid j = 1,2, \ ldots, | V | \}}$ ${\ displaystyle V_ {j} = \ {E_ {i} \ mid (E_ {i} \ in E) \ wedge (v_ {j} \ in E_ {i}) \}}$

Quindi l'ipergrafo definito da è chiamato doppio ipergrafo di . Corrisponde alla trasposizione della matrice. La nozione non coincide con quella di doppio grafo , anche nel caso in cui l'ipigrafo risulta essere un grafo. ${\ displaystyle H ^ {*} = (E, V ^ {*})}$ $H$

Esempi:

${\ displaystyle (\ {1,2 \}, \ {1,3 \}, \ {2,3 \})}$ è sia autodual che autotransversal .
${\ displaystyle (\ {1,2,3 \}, \ {1,4,5 \}, \ {1,6,7 \}, \ {2,4,6 \}, \ {2,5, 7 \}, \ {3,4,7 \}, \ {3,5,6 \})}$ è un piano proiettivo , autotrasversale, uniforme, regolare e autoduale.

Ipergrafo, ripristino, partizione

L'insieme degli spigoli di un ipergrafo non è necessariamente una sovrapposizione , perché un vertice può essere di grado zero, cioè non essere connesso da alcun bordo; in questo caso l'unione degli spigoli non copre tutti i vertici. Ad esempio, nell'ipergrafo tale che e , il vertice è di grado zero; non appare in nessuno dei sottoinsiemi di , impedisce che sia una sovrapposizione. L'insieme di bordi di un ipergrafo è solo una sovrapposizione se ogni vertice è almeno di grado 1. ${\ displaystyle V = \ {v_ {1}, v_ {2}, v_ {3}, v_ {4}, v_ {5}, v_ {6}, v_ {7} \}}$ ${\ displaystyle 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} \} \}}$ $v_7$ $e_i$ $E$ $E$

Di conseguenza, c'è una partizione se l'insieme di archi è una sovrapposizione e nessun vertice è connesso da due archi, cioè se un vertice è esattamente di grado 1.

Vedi anche

Note e riferimenti

Claude Berge , Graphs et Hypergraphes , Dunod, Collection Monograph Universitaires de Mathématiques n ° 37, gennaio 1970.

Claude Berge , Hypergraphs. Combinatoria degli insiemi finiti , Gauthier-Villars, 1987 ( ISBN 2-04-016906-7 ) .