Hypergraf

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání
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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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**.