Průnikový graf

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

Na tuto kapitolu je přesměrováno heslo Kružnicový graf.
Kružnicový graf a jemu odpovídající neorientovaný graf.

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.