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.

Polni graf na n točkah je Kneserjev graf .

Komplement povezavnega grafa polnega grafa na n točkah je Kneserjev graf . Za k = 2 je komplement Kneserjevega grafa znan kot Johnsonov graf .

Kneserjev graf je znan kot lihi graf . Lihi graf je izomorfen Petersenovemu grafu.

Š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]