2026 Kolokwium 2

Zadanie 1

Wierzchołki grafu \(G_n\) są etykietowane ciągami długości \(n\) nad alfabetem \(\{A, B, C\}\). Dwa wierzchołki są połączone krawędzią wtedy i tylko wtedy, gdy odpowiadające im ciągi różnią się na dokładnie jednej pozycji.

1. Rozstrzygnij, dla jakich \(n\) graf \(G_n\) ma cykl Hamiltona.
2. Znajdź liczbę chromatyczną grafu \(G_{2026}\).

Zadanie 2

Graf Knesera \(K(n, r)\) ma wierzchołki etykietowane \(r\)-podzbiorami \(n\)-zbioru; dwa wierzchołki są połączone krawędzią, jeśli odpowiadające im podzbiory są rozłączne. Rozstrzygnij, czy graf \(K(7, 3)\) jest planarny.

Zadanie 3

Oblicz \( \displaystyle \sum_{k=0}^{666} 5^k \bmod 7056 \).