náhled|upright=2|Příklad hypergrafu, formálně ,
. 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 , kde je množina vrcholů a je množina některých podmnožin , ty se nazývají hyperhrany. To lze stručněji zapsat tak, že (kde je potenční množina ).
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). 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í. Pokud mají dva vrcholy stejnou takovou množinu, vznikne v duálu multihyperhrana.
Pokud H neobsahuje izolované vrcholy, pak H=H**.
Externí odkazy
Kategorie:Teorie grafů
de:Graph (Graphentheorie)#Hypergraph