| dbo:abstract
|
- 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. (ca)
- 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. (ca)
|
| rdfs:comment
|
- 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 . La col·lecció dels hipergrafs és una categoria amb homomorfismes d'hipergrafs com a morfismes. (ca)
- 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 . La col·lecció dels hipergrafs és una categoria amb homomorfismes d'hipergrafs com a morfismes. (ca)
|
