Kneserjev graf
Iz Wikipedije, proste enciklopedije
Petersenov graf je Kneserjev graf.
Kneserjev graf KGn,k (ali tudi kar Kn,k) pri n ≥ 2k+1 je v teoriji grafov graf, katerega točke (vozlišča) ustrezajo podmnožici množice n elementov in kjer sta dve točki povezani, če in samo če sta odgovarjajoča seznama (množici) povezav disjunktna. Imenuje se po nemškem matematiku Hellmuthu Kneserju.
Graf KGn,1 je popolni graf (polni graf) na n točkah. Kneserjev graf KG5,2 je znan kot Petersenov graf.
Komplement Kneserjevega grafa je znan kot Johnsonov graf.
Število točk v Kneserjevem grafu je enako:
in vsaka je stopnje:
.
Število povezav je enako:
,
Kromatično število Kneserjevega grafa je enako χ(KG) = n-2k+2.
Ta matematični članek je škrbina. Slovenski Wikipediji lahko pomagate tako, da ga dopolnite z vsebino.


