Kneserjev graf
Iz Wikipedije, proste enciklopedije
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, ki ga je prvi raziskoval leta 1955.
Graf KGn,1 je popolni graf (polni graf) na n točkah. Kneserjev graf KG5,2 je znan kot Petersenov graf.
Kneserjev graf KG2n − 1,n − 1 je znan kot neparni graf On.
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.
