Hipergraf

Izvor: Wikipedia

U matematici, hipergraf predstavlja generalizaciju grafa, gde grane grafa mogu da povezuju bilo koji broj čvorova. Formalno, hipergraf je par (X,E) gde je X skup elemenata, čvorova, a E je skup podskupova od X, koji se nazivaju hipergrane. Grane grafa su predstavljene parovima čvorova koje one spajaju, dok su hipergrane proizvoljni skupovi čvorova, koji stoga mogu da sadrže proizvoljan broj čvorova.

Hipergraf se takođe naziva sistemom skupa ili familijom skupova izvučenih iz univerzalnog skupa X. Hipergrafovi se mogu posmatrati kao incidentne strukture, i obratno.

Mnoge teoreme koje se tiču grafova su primenjive i na hipergrafove. Remzijeva teorema je tipičan primer. Neke metode za proučavanje simetrija grafova se mogu proširiti na hipergrafove. Na primer, homomorfizam hipergrafova je preslikavanje iz skupa čvorova jednog hipergrafa u drugi, takvo da se svaka grana preslikava u drugu granu. Izomorfizam hipergrafova je inverzibilni homomorfizam. Automorfizam hipergrafova je izomorfizam jednog skupa čvorova u samog sebe, to jest, preimenovanje čvorova.

Za razliku od grafova, hipergrafove je teško nacrtati na papiru, tako da se oni obično izučavaju pomoću nomenklature teorije skupova pre nego korišćenjem vizuelnih prikaza (poput 'drveta', 'šuma' ili 'ciklova') iz teorije grafova.