Kafelkowania, Drzewa, Wyznaczniki

Prowadzący

Michał Kotowski

Opis

Głównym bohaterem zajęć będzie wyznacznik. Zobaczymy, w jaki sposób przydaje się on nie tylko do zabaw macierzami i algebry liniowej, ale do rozwiązywania problemów kombinatorycznych, a konkretnie do zliczania pewnych obiektów. Dwa główne pytania, jakimi się zajmiemy, to:

• Na ile sposóbów można pokryć prostokąt $m \times n$ kostkami domina (tak, jak na rysunku po prawej)? Liczba ta wynosi:

(1)

\begin{align} \prod\limits_{j=1}^{m} \prod\limits_{k=1}^{n} \left( 4 \cos^2 \frac{\pi j}{m+1} + 4 \cos^2 \frac{\pi k}{n+1} \right)^{1/4} \end{align}

"To jakiś kosmos! Dlaczego to w ogóle jest liczba całkowita?! Skąd iloczyn cosinusów?" - po warsztatach będziemy wiedzieć dlaczego ;)

• Ile drzew rozpinających ma zadany graf? Odpowiedzi udziela twierdzenie Kirchhoffa o drzewach rozpinających (Matrix Tree Theorem) - wystarczy policzyć wyznacznik macierzy zwanej laplasjanem grafu.

Zobaczymy też, jaki związek mają drzewa rozpinające z sieciami elektrycznymi i błądzeniami losowymi i dlaczego przydaje się to do generowania labiryntów takich, jak ten:

Zależnie od ilości czasu przewidziane są też desery.

Program zajęć

Poniższy plan to program maksimum. Poza dwoma głównymi problemami wspomnianymi powyżej zdążymy zapewne omówić tylko niektóre z dodatkowych tematów (oznaczonych [*]).

• wyznacznik macierzy, podstawowe własności, wartości własne macierzy
• zliczanie skojarzeń w grafach, permanent macierzy
• macierz Kasteleyna, zliczanie kafelkowań na kratce $m \times n$
• [*] metoda zliczania skojarzeń na ogólnym grafie planarnym
• [*] bijekcja Temperleya
• laplasjan grafu, twierdzenie Kirchhoffa o drzewach rozpinających
• sieci elektryczne i błądzenia losowe, losowe drzewa rozpinające a opór zastępczy, łańcuchy Markowa
• [*] generowanie losowych drzew rozpinających: algorytmy Aldousa-Brodera i Wilsona, labirynty
• [*] więcej zabaw wyznacznikiem: lemat Gessela-Viennota i jego zatosowania
• [*] więcej o kafelkowaniach: Aztec Diamond, asymptotyczny kształt losowego kafelkowania, "Arctic Circle Theorem"
• [*] algorytmy szukanie skojarzeń oparte na wyznaczniku

Wymagania

Rozumieć podstawową terminologią związaną z grafami i wiedzieć coś o liczbach zespolonych (wystarczy wiedzieć, co to pierwiastek $n$-tego stopnia z jedynki). Nie trzeba wiedzieć nic o algebrze liniowej, aczkolwiek oczywiście jeśli ktoś widział wcześniej macierze i wyznaczniki, to będzie miał łatwiej.

Zadania kwalifikacyjne

Należy spróbować rozwiązać jak najwięcej zadań - oczekuję, że każdy rozwiąże co najmniej pięć zadań spośród zadań 1-6 oraz co najmniej dwa z zadań 7-10 (aczkolwiek próg kwalifikacji będzie zależał od poziomu nadesłanych rozwiązań). Jeśli zadania okażą się trudne, daj znać, a zamieszczę wskazówki. Podobnie, jeśli zadania okażą się zbyt banalne, daj znać, a zamieszczę trudniejsze wersje.

Rozwiązania należy wysyłać na adres: moc.liamg|1ikswotok.lahcim#moc.liamg|1ikswotok.lahcim. Zachęcam do ich wcześniejszego przysyłania (nie tuż przed deadlinem) - będzie możliwość poprawiania rozwiązań. Jeśli masz jakiekolwiek pytania, wątpliwości, zauważysz błąd w treści zadania etc. - koniecznie napisz!

Zadanie 1

a) Wyobraźmy sobie prostokąt $2 \times n$, który chcemy pokryć kostkami domina o wymiarach $2 \times 1$ (każda kostka może być ustawiona pionowo lub poziomo). Na ile sposobów można to zrobić?

b) Spróbuj zastosować podobną metodę, co w podpunkcie a), do analogicznego problemu dla prostokąta $3 \times n$.

Zadanie 2

Rozważmy prostokąt i kafelkowanie kostkami domina z poprzedniego zadania. O kostce domina możemy myśleć jako o krawędzi łączącej dwa sąsiednie punkty kratki $2 \times n$. Jeśli weźmiemy dwa kafelkowania i nałożymy je na siebie, to dostaniemy pokrycie prostokąta cyklami o parzystej długości (dwie nałożone na siebie krawędzie dają wtedy cykl długości dwa), tak jak na (nieco niechlujnym) rysunku:

a) Podać przykład, że dwie różne pary kafelkowań mogą dawać to samo pokrycie cyklami.

b) Wymyślić, w jaki sposób można zorientować krawędzie prostokąta, aby zorientowane pokrycie cyklami wyznaczało już jednoznacznie parę zorientowanych kafelkowań. Wykorzystać wynik z podpunktu a) poprzedniego zadania do wyznaczenia liczby wszystkich takich zorientowanych pokryć cyklami. [Wskazówka: wystarczy zorientować pionowe krawędzie]

Zadanie 3

Rozważmy zbiór $\{1, \ldots, n\}$ i wszystkie jego permutacje. Transpozycją nazwiemy permutację, która zamienia miejscami dwa ustalone elementy, a pozostałych nie rusza.

a) Pokazać, że każdą permutację można zapisać jako złożenie pewnej liczby transpozycji.

b) Znakiem permutacji $\sigma$ nazwiemy liczbę równą $+1$, jeśli $\sigma$ daje się rozłożyć na parzystą liczbę transpozycji, oraz $-1$, jeśli daje się rozłożyć na nieparzystę liczbę transpozycji. Pokazać, że liczba ta jest dobrze określona, tj. dana permutacja nie może mieć jednocześnie znaku $+1$ i $-1$.

Zadanie 4

Rozważmy nieskierowany graf $G$ o parzystej liczbie wierzchołków. Doskonałym skojarzeniem nazwiemy taki zbiór krawędzi, że ich końce pokrywają wszystkie wierzchołki grafu i każdy wierzchołek należy do tylko jednej krawędzi. Cykl parzystej długości $C$ nazwiemy dobrym, jeśli po wyrzuceniu wierzchołków należących do tego cyklu pozostała część grafu posiada przynajmniej jedno doskonałe skojarzenie.

Rozważmy teraz dowolną orientacją krawędzi grafu $G$. Powiemy, że cykl parzystej długości $C$ jest nieparzyście zorientowany, jeśli obchodząc go w dowolnym kierunku przechodzimy przez nieparzyście wiele krawędzi zgodnych z wybraną orientacją grafu $G$.

Podać przykład grafu posiadającego co najmniej dwa cykle, który można zorientować tak, aby zachodziła następująca własność: każdy dobry cykl jest nieparzyście zorientowany. Pokazać, że grafu $K_{3,3}$, przedstawionego poniżej, nie da się zorientować w ten sposób.

Zadanie 5

Pokazać, że:

(2)

\begin{align} \prod\limits_{l=1}^{n} \cos \left( \frac{l \pi}{2n+1} \right) = 2^{-n} \end{align}

Zadanie 6

Rozważmy układ dwóch równań o rzeczywistych lub zespolonych współczynnikach $a,b,c,d$:

(3)

\begin{align} ax + by = 0 \\ cx + dy = 0 \end{align}

Oczywiście $x = y = 0$ zawsze jest jego rozwiązaniem. Znaleźć warunek konieczny i dostateczny na współczynniki, aby istniały inne, niezerowe rozwiązania. Czy potrafisz uogólnić ten warunek na przypadek trzech równań? A na $n$ równań?

Zadanie 7

Drzewem rozpinającym w grafie nazwiemy podzbiór jego krawędzi, który jest drzewem (czyli grafem spójnym bez cykli) oraz zawiera wszystkie wierzchołki grafu. Znaleźć liczbę wszystkich drzew rozpinających w drabince o wysokości $n$ (poniżej znajduje się przykładowy rysunek dla $n=8$:

(uwaga - graf traktujemy jako etykietowany, tj. liczy się nie tylko "kształt" drzewa, ale też to, jakie wierzchołki zawiera)

Zadanie 8

Graf $G$ nazwiemy planarnym, jeśli da się go narysować na płaszczyźnie tak, aby krawędzie się nie przecinały. Ścianą takiego grafu nazwiemy dowolny spójny obszar ograniczony krawędziami, w szczególności uwzględniamy zewnętrzną, nieskończoną ścianę (od tej pory utożsamiamy graf z jego rysunkiem na płaszczyźnie). Grafem dualnym do $G$ nazwiemy graf $G^{\ast}$ otrzymany następująco: dla każdej ściany $f$ w $G$ wprowadzamy jeden wierzchołek $f^{\ast}$ w $G^{\ast}$ i dla każdej krawędzi, którą stykają się ściany $f_1$ i $f_2$ w $G$, odpowiadające im wierzchołki $f_{1}^{\ast}$, $f_{2}^{\ast}$ w $G^{\ast}$ łączymy krawędzią.

Pokazać, że dla grafu planarnego zachodzi wzór Eulera:

(4)

\begin{equation} V - E +F = 2 \end{equation}

gdzie $V$ to liczba wierzchołków, $E$ - liczba krawędzi, a $F$ - liczba ścian. Wskazówka: dualność oraz drzewa rozpinające.

(można tego wzoru dowodzić też przez indukcję, ale zachęcam do próby użycia wskazówki)

Zadanie 9

Rozważmy dla $n \geq 3$ następujący układ równań:

(5)

\begin{align} x_1 + x_3 = \lambda x_2 \\ x_2 + x_4 = \lambda x_3 \\ \ldots \\ x_{n-2} + x_n = \lambda x_{n-1} \\ x_{n-1} + x_1 = \lambda x_n \\ x_{n} + x_2 = \lambda x_1 \end{align}

gdzie $\lambda$ jest pewnym parametrem. Znaleźć wszystkie rozwiązania w zależności od $\lambda$. Wskazówka: układ równań ma cykliczną symetrię - jak mogą tu pomóc zespolone pierwiastki z jedynki?

Zadanie 10

Znaleźć liczbę wszystkich drzew na zbiorze wierzchołków $\{1, \ldots, n\}$ (drzewa uznajemy za etykietowane, czyli liczy się nie tylko "kształt" drzewa, ale numery wierzchołków). Uwaga: to zadanie jest być może trudniejsze od pozostałych, więc w razie trudności pojawią się wskazówki.

Kontakt

Mój mail to moc.liamg|1ikswotok.lahcim#moc.liamg|1ikswotok.lahcim - bardzo chętnie odpowiem na wszelkie pytania związane z warsztatami i nie tylko!