Prednášky LS 2024/25 - diskrétna matematika

[Martin Sleziak]

Spoiler:

10. prednáška (28.4.):
Hamiltonovské grafy.
Postačujúce podmienky: Pripomenuli sme Bondy-Chvátalovu vetu, z ktorej ako dôsledky dostaneme Diracovu aj Oreho vetu.
Nutná podmienka: Pre párne grafy musia byť obe časti grafu rovnako veľké, aby sme dostali hamiltonovský graf.
Petersenov graf. Ukázali sme, že Petersenov graf nie je hamiltonovský. A tiež to, že po vynechaní jedného vrcholu dostaneme hamiltonovský graf - t.j. Petersenov graf je hypohamiltonovský.

Fibonacciho čísla.
Trochu sme sa rozprávali o Fibonacciho číslach.
Povedali sme si definíciu. Pripomenuli sme Binetovu formulu $$F_n=\frac{\varphi^n-\psi^n}{\varphi-\psi}=\frac{\varphi^n-\psi^n}{\sqrt5}$$ a to, že sa dá odvodiť indukciou. (Pri dôkaze sme si tiež uvedomili, že postupnosti vyhovujúce rekurencii $A_{n+2}=A_{n+1}+A_n$ sú uzavreté vzhľadom na lineárne kombinácie.)
Pozreli sme sa na maticové vyjadrenie Fibonacciho čísel, t.j. na to, že platí $$\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}^n=
\begin{pmatrix}
F_{n+1} & F_n \\
F_n & F_{n-1}
\end{pmatrix}.$$
Rozmysleli sme si, že vďaka podobnosti s diagonálnou maticou $\operatorname{diag}(\varphi,\psi)$ vieme aj z tohto vyjadrenia dostať Binetov vzorec.
Pri výpočte charakteristického polynómu sme spomenuli to, ako jeho koeficienty súvisia so stopou a determinantom: viewtopic.php?t=642
Povedali sme si ako $n$-tú mocninu matice (a teda aj Fibonacciho čísla) vieme počítať o čosi efektívnejšie, než postupnosť vypočítať $A^1, A^2, A^3, \ldots, A^n$; v skutočnosti nám stačí rádovo $\log_2 n$ mocnín matice $A$. Wikipédia: Exponentiation by squaring.
Niečo o Fibonacciho číslach a maticiach je aj tu: viewtopic.php?ft=640

[Martin Sleziak]

11. prednáška (5.5.):
Fibonacciho čísla.
Pozreli sme sa na kombinatorickú interpretáciu Fibonacciho čísel pomocou dláždení.
Limita $\lim\limits_{n\to\infty} \frac{F_{n+1}}{F_n}=\varphi$ a zlatý rez.
Fibonacciho čísla vieme rozšíriť aj na záporné indexy.

Zvyšok hodiny sme venovali počítaniu príkladov okolo Fibonacciho čísel.

[Martin Sleziak]

12. prednáška (12.5.):
Lineárne homogénne rekurencie s konštantnými koeficientami.
Pozreli sme sa na rekurencie tvaru
$$A_n=c_{k-1}A_{n-1}+c_{k-2}A_{n-2}+\dots+c_1A_{n-k+1}+c_0A_{n-k}.$$
Rozmysleli sme si, že riešenia takejto rekurencie tvoria podpriestor priestoru všetkých postupností $\mathbb C^{\mathbb N}$ a že jeho dimenzia je $k$.
Ak nemá charakteristická rovnica, tak bázu dostaneme z geometrických postupností tvaru $\alpha^n$, kde za $\alpha$ môžeme dosadzovať jednotlivé korene. Tento fakt sme aj dokázali na základe podobnosti s diagonálnou maticou.
Ak má charakteristická rovnica $s$-násobný koreň $\alpha$, tak časť bázy zodpovedajúca tomuto koreňu obsahuje postupnosti $\alpha^n, n\alpha^n, n^2\alpha^n, \dots, n^{s-1}\alpha^n$.
Prepísali sme si rekurenciu pomocou štvorcovej matice. To viedlo k tomu, že pre $n$-tý člen vieme dostať vyjadrenie z $n$-tej mocniny vhodnej matice; jej charakteristický polynóm zodpovedá presne charakteristickej rovnice.
Ukázali sme si riešení pomocou mocnín Jordanovho tvaru. (O čosi jednoduchšie to bolo v prípade bez násobných koreňov - keďže stačilo umocňovať diagonálnu maticu.
K mocninám Jordanovho bloku pridám aspoň takúto linku: Why does the n-th power of a Jordan matrix involve the binomial coefficient?