frame| Exemple d'un hipergraf, en el qual i
. En matemàtiques, i més concretament en teoria de grafs, un hipergraf és una generalització d'un graf en la qual les arestes poden connectar un nombre qualsevol de vèrtexs. Formalment, un hipergraf és un parell de conjunts , on és el conjunt d'elements anomenat nodes o vèrtexs i és un conjunt de subconjunts no-buits de anomenats hiperarestes o simplement arestes. Per tant, és un subconjunt de , on és el conjunt de les parts de .
Mentre que les arestes d'un graf són parells de vèrtexs, les hiperarestes són conjunts arbitraris de vèrtexs i, per tant, poden contenir un nombre arbitrari de vèrtexs. Tanmateix, sovint és interessant estudiar hipergrafs on totes les hiperarestes tenen la mateixa cardinalitat; un hipergraf k-uniforme és un hipergraf on totes les hiperarestes tenen grandària k (en altres paraules, un tal hipergraf és una col·lecció de conjunts, on cadascun representa una hiperaresta que connecta k vèrtexs). Així, un hipergraf 2-uniforme és un graf, un hipergraf 3-regular és una col·lecció de triplets no ordenats, i així successivament.
Un hipergraf també es coneix com a sistema de conjunts o una família de conjunts escollits del conjunt universal X. La diferència entre un sistema de conjunts i un hipergraf és una qüestió encara ni tancada. La teoria d'hipergrafs tendeix a tractar qüestions simulars a les de la teoria de grafs, com la connectivitat o la coloració, mentre que la teoria de sistemes de conjunts acostuma a tractar aspectes no relacionats amb la teoria de grafs, com a la teoria de Sperner.
Existeixen diferents definicions per als hipergrafs; de vegades les arestes han de ser no buides, i de vegades es permeten arestes múltiples, que connecten el mateix conjunt de vèrtexs.
Els hipergrafs es poden veure com a estructures d'incidència. En particular, existeix un "graf d'incidència" o "graf de Levi" corresponent a cada hipergraf; recíprocament, la majoria de grafs bipartits, però no qualsevol, es poden interpretar com a grafs d'incidència d'hipergrafs.
Els hipergrafs tenen altres noms. En geometria computacional, un hipergraf es pot conèixer com a espai de rangs i les hiperarestes s'anomenen rangs. En teoria de jocs cooperatius, els hipergrafs es coneixen com a jocs simples (jocs de votació); aquesta noció s'aplica en la resolució de problemes de teoria de l'elecció social. Alguns autors es refereixen a les hiperarestes com a hiperenllaços o connectors.
Alguns tipus especials d'hipergrafs inclouen, a part dels k-uniformes, els clutters, on cap aresta apareix com a subconjunt de cap altra aresta; i els complexos simplicials abstractes, que contenen tots els subconjunts de cada aresta.
La col·lecció dels hipergrafs és una categoria amb homomorfismes d'hipergrafs com a morfismes.
Terminologia Com que les arestes d'un hipergraf poden tenir qualsevol cardinalitat, existeixen diferents nocions sobre el concepte de subgraf, anomenades subhipergrafs, hipergrafs parcials i hipergrafs de secció.
Sigui l'hipergraf que consisteix dels vèrtexs
i amb el conjunt d'arestes , on i són els conjunts d'índexs dels vèrtexs i de les arestes, respectivament.
Un subhipergraf és un hipergraf on s'han eliminat alguns dels vèrtexs. Formalment, el subhipergraf induït per un subconjunt de es defineix com .
Lhipergraf parcial és un hipergraf on s'han eliminat algunes arestes. Donat un subconjunt del conjunt d'índexs de les arestes, l'hipergraf parcial generat per és l'hipergraf .
Donat un subconjunt , lhipergraf de secció és l'hipergraf parcial .
El dual de és un hipergraf on s'han intercanviat els vèrtexs amb les arestes, de tal manera que els vèrtexs venen donats per i les arestes del qual venen donades per , on .
Quan es proporciona una noció d'igualtat definida adequadament, com es fa més endavant, l'operade passar al dual d'un hipergraf és una involució, és a dir, .
Un graf connex G amb el mateix conjunt de vèrtexs d'un hipergraf connex H és un graf histe de H si tota hiperaresta de H indueix un subgraf connex dins G. En el cas d'un hipergraf no connex H, G és un graf hoste si existeix una bijecció entre les components connexes de G i les de H, de tal manera que cada component connexa G de G és un hoste de la corresponent H.
Un hipergraf és bipartit si i només si els seus vèrtexs admeten una partició en dues classes U i V de tal manera que cada hiperaresta amb cardinalitat ≥2 conté, almenys, un vèrtex de cadascuna de les classes.
La 2-secció (o graf «clique», graf representant, graf primari, graf de Gaifman) d'un hipergraf és un graf amb els mateixos vèrtexs de l'hipergraf, i amb les arestes entre tots els parells de vèrtexs continguts en la mateixa hiperaresta.
Model de graf bipartit Un hipergraf H es pot representar mitjançant un graf bipartit BG de la següent forma: els conjunts X i E són les particions de BG, i (x1, e1) estan connectats per una aresta si i només si el vèrtex x1 està contingut en l'aresta e1 de H. Recíprocament, tot graf bipartit sense vèrtexs aïllats es pot descriure de la forma anterior. Aquest graf bipartit es coneix també com a graf d'incidència.
Aciclicitat En contrast amb els grafs no dirigits ordinaris, on existeix una única noció natural de cicles i grafs acíclics, existeixen diverses definicions naturals, no equivalents entre si, d'aciclicitat per a hipergrafs, que esdevenen l'aciclicitat ordinària de grafs en el cas especial que l'hipergraf sigui, de fet, un graf.
Una primera definició d'aciclicitat per a hipergrafs fou establerta per Claude Berge: un hipergraf és Berge-acíclic si el seu graf d'incidència (el graf bipartit definit abans) és acíclic. Aquesta definició és molt restrictiva: per exemple, si un hipergraf té un parell de vèrtexs i un parell d'hiperarestes tals que i , llavors és Berge-cíclic. La ciclicitat en el sentit de Berge es pot comprovar en temps lineal mitjançant l'exploració del graf d'incidència.
Hom pot definir una noció més feble d'hipergrafs sense cicles, coneguda com a α-aciclicitat. Aquesta noció d'aciclicitat és equivalent a la condició de què l'hipergraf sigui conforme (tot clique del graf primari està cobert per alguna hiperaresta) i que el seu graf primari sigui cordal; també és equivalent a la condició de ser reductible al graf buit mitjançant l'algorisme GYO (també conegut com a algorisme de Graham), un procés iteratiu confluent que elimina hiperarestes emprant una definició generalitzada d'orelles. En l'àmbit de la teoria de bases de dades, es coneix que un esquema té certes propietats desitjables si el seu hipergraf subjacent és α-acíclic.
Es pot comprovar en temps lineal si un hipergraf és α-acíclic.
Cal notar que l'α-aciclicitat té la propietat, contrària a la intuïció, de què, si s'afegeixen hiperarestes a un hipergraf α-cíclic, hom pot fer que esdevingui α-acíclic (per exemple, si s'afegeix una hiperaresta que contingui tots els vèrtexs, sempre farà que l'hipergraf esdevingui α-acíclic). Motivat en part per aquest inconvenient, Ronald Fagin definí les nocions de β-aciclicitat i γ-aciclicitat, més fortes que l'anterior. Hom pot establir la β-aciclicitat com el requeriment de què tots els subhipergrafs de l'hipergraf siguin α-acíclics, la qual cosa és equivalent a una definició anterior de Graham. La noció de γ-aciclicitat és una condició més restrictiva, equivalent a diverses propietats desitjables dels esquemes de bases de dades, i relacionada amb els diagrames de Bachman. Tant la β-aciclicitat com la γ-aciclicitat es poden verificar en temps polinòmic.
Aquestes quatre nocions d'aciclicitat són comparables: l'aciclicitat en el sentit de Berge implica la γ-aciclicitat, la qual implica la β-aciclicitat, i aquesta darrera implica la α-aciclicitat. Tanmateix, cap de les implicacions recíproques és certa, de tal manera que aquestes quatre nocions són diferents.
Isomorfisme i igualtat Un homomorfisme d'hipergrafs és una aplicació del conjunt de vèrtexs d'un hipergraf a un altre, de tal manera que s'envia cada aresta a una altra aresta.
Un hipergraf és isomorf a un hipergraf , escrit com , si existeixen una bijecció
i una permutació de tals que .
Hom diu llavors que la bijecció és l'isomorfisme entre els grafs. Observem que si i només si .
Quan les arestes d'un hipergraf estan etiquetades de forma explícita, hom té la noció addicional disomorfisme fort. Hom diu que és fortament isomorf a si la permutació és la identitat. Llavors s'escriu . Cal destacar que tot geaf fortament isomorf és isomorf, però el recíproc no és cert.
Quan els vèrtexs d'un hipergraf estan etiquetats de forma explícita, hom pot considerar les nocions dequivalència i digualtat. Es diu que és equivalent a , escrit , si l'isomorfisme compleix
i .
Observem que si i només si .
Si, a més, la permutació és la identitat, hom diu que és igual a , i s'escriu . Notem que, amb aquesta definició d'igualtat, els grafs són autoduals: .
Un automorfisme d'un hipergraf és un isomorfisme d'un conjunt de vèrtexs en ell mateix, de tal manera que és un reetiquetatge dels vèrtexs. El conjunt d'automorfismes d'un hipergraf H (= (X, E)) forma un grup amb la composició, anomenat el grup d'automorfismes, de l'hipergraf, simbolitzat per Aut(H).
Exemples Considerem l'hipergraf amb arestes
i
Clarament, i són isomorfs (amb , etc.), però no són fortament isomorfs: per exemple, a , el vèrtex forma part de les arestes 1, 4 i 6, és a dir, .
Però en el graf , no hi ha cap vèrtex compartit per les arestes 1, 4 i 6: .
En aquest exemple, i són equivalents, , i els duals són fortament isomorfs: .
Hipergrafs simètrics El d'un hipergraf és la màxima cardinalitat d'entre les arestes de l'hipergraf. Si totes les arestes tenen la mateixa cardinalitat k, es diu que l'hipergraf és uniforme o k-uniforme; també es parla d'un k-hipergraf. Un graf és, simplement, un hipergraf 2-uniforme.
El grau d(v) d'un vèrtex v és el nombre d'arestes que el contenen. Hom diu que H és k-regular si tots els vèrtexs tenen grau k.
El dual d'un hipergraf uniforme és regular, i viceversa.
Hom diu que dos vèrtexs x i y són simètrics si existeix un automorfisme tal que . Hom diu que dues arestes i són simètriques si existeix un automorfisme tal que .
Hom diu que un hipergraf és vèrtex-transitiu (o vèrtex-simètric) si tots els seus vèrtexs són simètrics. Anàlogament, un hipergraf és aresta-transitiu si totes les seves arestes són simètriques. Si un hipergraf és alhora aresta-transitiu i vèrtex-transitiu, llavors hom diu que l'hipergraf és transitiu.
Per les propietats de dualitat dels hipergrafs, l'estudi de l'aresta-transitivitat és idèntic a l'estudi de la vèrtex-transitivitat.
Transversals La transversal d'un hipergraf H = (X, E) és un conjunt que té una intersecció no buida amb tota aresta de l'hipergraf. Hom diu que una transversal T és mínima si cap subconjunt propi de T és transversal. Lhipergraf transversal de H és l'hipergraf (X, F) on el conjunt d'arestes F consisteix en totes les transversals mínimes de H.
El càlcul de l'hipergraf transversal té aplicacions en optimització combinatòria, en teoria de jocs, i en diversos camps de les ciències de la computació, com l'aprenentatge automàtic, l'indexat de bases de dades, el problema de satisfactibilitat, la mineria de dades, i l'optimització de codi.
Matriu d'incidència Siguin i . Tot hipergraf té una matriu d'incidència de dimensió on
La transposada de la matriu d'incidència defineix un hipergraf , anomenat dual de , on és un conjunt de m elements i és un conjunt de n elements de subcinjunts de . Donats i , es té que si i només si .
Coloració d'hipergrafs