Cesko.wiki Hypergraf
Author
Albert FloresHypergraf je pojem z oboru matematiky, který označuje graf, jehož hrany mohou spojovat více než dvě vrcholy. To znamená, že hypergraf je obecnější než běžný graf, který spojuje pouze dvojice vrcholů. Hrany hypergrafu jsou tedy hyperhrany, které spojují alespoň tři vrcholy. Díky tomu umožňuje hypergraf reprezentovat komplexnější vztahy a struktury mezi prvky. Hypergrafy se využívají ve více oborech, například v teorii grafových hyperzobrazení, v teorii množin, v databázových systémech či v umělé inteligenci. Existují různé typy hypergrafů, například obarvené, vahové či bipartitní hypergrafy. Práce s hypergrafy zahrnuje analýzu jejich vlastností, konstrukci a optimalizaci jejich struktury nebo nalezení nejkratších cest. Historie hypergrafů sahá až do 20. století, avšak jejich formalizace a důkladné studium se objevilo až v 70. a 80. letech. Dnes jsou hypergrafy důležitým nástrojem při zkoumání struktur a vztahů v různých oborech jako matematická analýza, teorie množin, počítačová věda a dalších.
Příklad hypergrafu, formálně X = \{v_1, v_2, v_3, v_4, v_5, v_6, v_7\}, E= \{e_1,e_2,e_3,e_4\} =\{\{v_1, v_2, v_3\}, \{v_2,v_3\}, \{v_3,v_5,v_6\},\{v_4\}\}. Hypergraf je pojem z teorie grafů. Jedná se o zobecnění pojmu graf. Rozdíl je v tom, že hrany hypergrafu (hyperhrany) mohou spojovat libovolný počet vrcholů, zatímco u grafu spojují hrany vždy dva vrcholy.
Definice
Hypergraf H je dvojice H = (X,E), kde X je množina vrcholů a E je množina některých podmnožin X, ty se nazývají hyperhrany. To lze stručněji zapsat tak, že E\subseteq\mathcal{P}(X) (kde \mathcal{P}(X) je potenční množina X).
Tato definice splývá s definicí pojmu množinového systému.
Varianty definice
Definice hypergrafu však není zcela ustálená, v literatuře se objevují následující varianty:
* Hyperhrana nesmí být prázdná. * Hypergraf nesmí obsahovat izolované vrcholy (aby duální hypergraf nesl veškerou informaci). +more * Hypergraf nesmí obsahovat dva vrcholy obsažené ve stejných hranách (aby duální hypergraf neměl multihyperhrany). * Pokud E je multimnožina, jedná se o multihypergraf.
Hypergraf jako bipartitní graf
Každý hypergraf se dá popsat jako bipartitní graf: první partita jsou vrcholy, druhá hyperhrany a hrany jsou mezi každým vrcholem a hranou, která ho obsahuje.
Duální hypergraf
Duální hypergraf H* vznikne „prohozením“ hyperhran a vrcholů. H*=(E,Y), přičemž Y jsou množiny hran, za každý vrchol je přidána množina všech hran, které vrchol obsahují. +more Pokud mají dva vrcholy stejnou takovou množinu, vznikne v duálu multihyperhrana.
Pokud H neobsahuje izolované vrcholy, pak H=H**.