Kneserjev graf

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje
Kneserjev graf
Kneser graph KG(5,2).svg
Kneserjev graf KG5,2,
izomorfen Petersenovemu grafu
Ime Martin Kneser
Točke
Povezave
Kromatično število
Ulomljeno kromatično števlo
Značilnosti -regularen
simetričen
Označba
Petersenov graf je Kneserjev graf.

Kneserjev graf (ali tudi kar ) pri n ≥ 2k+1 je v teoriji grafov graf, katerega točke 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 Martinu Kneserju, ki ga je prvi raziskoval leta 1955.

Graf je polni graf na n točkah. Kneserjev graf je znan kot Petersenov graf.

Kneserjev graf je znan kot neparni 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.

Zunanje povezave[uredi | uredi kodo]