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 \textstyle\binom{n}{k}
Povezave \textstyle\binom{n}{k} \binom{n - k}{k} / 2
Kromatično število \left\{\begin{array}{ll}n - 2 k + 2 & n \ge 2 k\\ 1 & \text{drugače}\end{array}\right.
Ulomljeno kromatično števlo n/k
Značilnosti \textstyle\binom{n - k}{k}-regularen
simetričen
Označba KG_{n,k},\, K(n,k)
Petersenov graf je Kneserjev graf.

Kneserjev graf KG_{n,k} (ali tudi kar K_{n,k}) 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 KG_{n,1} je polni graf na n točkah. Kneserjev graf KG_{5,2} je znan kot Petersenov graf.

Kneserjev graf KG_{2n-1,n-1} je znan kot neparni graf O_n.

Komplement Kneserjevega grafa je znan kot Johnsonov graf.

Število točk v Kneserjevem grafu je enako:

 {2n+k \choose n} \!\,

in vsaka je stopnje:

 {n+k \choose n} \!\, .

Število povezav je enako:

{1\over 2} {2n+k \choose n} {n+k \choose n} \!\, .

Kromatično število Kneserjevega grafa je enako χ(KG) = n-2k+2.

Zunanje povezave[uredi | uredi kodo]