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.

Kneserjev graf
Kneserjev graf KG5,2,
izomorfen Petersenovemu grafu
ImeMartin Kneser
Točke
Povezave
Kromatično število
Ulomljeno kromatično števlo
Značilnosti-regularen
simetričen
Označba
Petersenov graf je Kneserjev graf.

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

  • Weisstein, Eric Wolfgang. »Kneser Graph«. MathWorld.