Hypergraf

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.

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}\}\}$.

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).
• 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

• Obrázky, zvuky či videa k tématu hypergraf na Wikimedia Commons

Autoritní data	NKC: ph1153721 PSH: 7175 BNF: cb119790981 (data) GND: 4161063-5 LCCN: sh85063697 NLI: 987007536189705171 SUDOC: 027834808