Průnikový graf

Průnikový graf rovinných objektů

Průnikový graf množinového systému je graf, kde vrcholům odpovídají množiny systému a hrany jsou právě mezi těmi, které mají neprázdný průnik.

Kromě průnikových grafů obecných množinových systémů se zkoumají například průnikové grafy geometrických objektů, jako úseček na přímce, křivek či polygonů v rovině nebo koulí a obecných těles v prostoru libovolné dimenze.

Kružnicový graf

Kružnicový graf a jemu odpovídající neorientovaný graf. +more Kružnicový graf je průnikový graf množiny tětiv v kružnici. Každá tětiva reprezentuje vrchol neorientovaného grafu. Dvě tětivy v kružnicovém grafu se protnou, právě když jsou v původním grafu jim odpovídající vrcholy spojeny hranou.

Kategorie:Typy grafů