Kneserjev graf

Kneserjev graf $K G_{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.

Polni graf na n točkah je Kneserjev graf $K G_{n, 1}$ .

Komplement povezavnega grafa polnega grafa na n točkah je Kneserjev graf $K G_{n, 2}$ . Za k = 2 je komplement Kneserjevega grafa $K G_{n, 2}$ znan kot Johnsonov graf $J_{n, 2}$ .

Kneserjev graf $K G_{2 n - 1, n - 1}$ je znan kot lihi graf $O_{n}$ . Lihi graf $O_{3} = K G_{5, 2}$ je izomorfen Petersenovemu grafu.

Število točk v Kneserjevem grafu je enako:

(\binom{2 n + k}{n})

in vsaka je stopnje:

(\binom{n + k}{n}) .

Število povezav je enako:

\frac{1}{2} (\binom{2 n + k}{n}) (\binom{n + k}{n}) .

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

Zunanje povezave

Predloga:MathWorld

Predloga:Math-stub

Kneserjev graf

Zunanje povezave

Navigacijski meni

Iskanje