Hüpergraafid

Hüpergraafid on matemaatiline struktuur, mis laiendab tavapärast graafi, võimaldades ühendusi, mida nimetatakse hüperäärideks. Ta koosneb kahest osast: tipudest V ja hüperääride kogumikust E, kus iga hüperäär e on mitte-tühi alamhulk V-st. Formaalne definitsioon kõlab: H = (V, E) kus V on lõplik ja E ⊆ P(V). Iga e ∈ E ühendab kõik selle hulka kuuluvad tipud. Erinevalt tavapärastest graafidest võivad hüperäärid sisaldada rohkem kui kaks tipu.

Hüpergraafi inkidentsusgraaf on bipartitiline graaf, mille moodustavad tipud V ja hüperäärid E ning kus ühendused I ⊆ V × E tähistavad, et v ∈ e kui ja ainult kui v kuulub hüperäärile e. Inkidentsusgraafi kaudu saab hüpergraafi struktuuri kajastada tavagraafina.

Tüübid ja omadused: kui iga hüperäär e sisaldab täpselt k tipu, nimetatakse hüpergraafi k-uniformseks. Kui kõik hüperäärid on sama suurusega, on tegemist üldiselt ühtlasema suurusega hüpergraafiga; rohkematel juhtudel kasutatakse mõistet uniform vs. general. Lisaks võivad hüpergraafid olla regulaarsed, kui kõik tipud kuuluvad sama arvuga hüperääridest.

Aktiivsus ja tsüklid: hüpergraafidel kasutatakse tsüklite mõisteid, näiteks Berge-tsüklid. Erinevad aktsiad mõisted (näiteks Berge-, α-, β- ja γ-acyclicity) kirjeldavad struktuuri lihtsust ja tsüklilisi omadusi ning on oluliseks tööriistaks teoreetilises informatsiooni- ja andmebaasiteoorias.

Rakendused ja probleemid: hüpergraafe kasutatakse andmebaasiteoorias konjunktsionaalsete päringute modelleerimisel ja hypertree‑dekompositsioonide abil päringute optimeerimisel, samuti klasterdamises ja võrguanalüüsis. Üldiselt on paljud probleemid hüpergraafides NP-hard, kuid piiratud klassidel on lahendused või efektiivsemad heuristika-tüübid.