Hipergrafo minimal
Aparència
En teoria de hipergrafos, el hipergrafo minimal o simplement minimal d'un hipergrafo H definit sobre un conjunt base A, és el hipergrafo μ(H) conformat per totes les hiperaristas mínimes de H, és dir, aquelles tal que cap atra és subconjunt d'elles. Formalment, donat un hipergrafo H definit sobre un conjunt base A, el minimal de H és l'operador definit com:
Note que μ(H) és subconjunt de H.
El minimal d'una estructura de hipergrafos G:=(H, K) es definix com:
Complexitat computacional
Un hipergrafo minimal pot determinar-se en temps polinòmic en funció del tamany de l'entrada (siga esta H o G). En efecte, n'hi ha prou en recórrer cada hiperarista de cada hipergrafo, i anar verificant si una és o no subconjunt de l'atra.
Referències
- Este artícul conté una traducció derivada de «Hipergrafo minimal» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.