10. prednáška (2.5.):
Hamiltonovské grafy.
Definícia hamiltonovskej cesty a hamiltonovskej kružnice.
Nutné podmienky: $c(G\setminus S)\le|S|$. Pre párne grafy musia byť obe časti grafu rovnako veľké, aby sme dostali hamiltonovský graf.
Postačujúce podmienky: Ukázali sme Bondy-Chvátalovu vetu, z ktorj ako dôsledky dostaneme Diracovu aj Oreho vetu.
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ý.
Prednášky LS 2023/24 - diskrétna matematika
-
Martin Sleziak
- Posts: 5687
- Joined: Mon Jan 02, 2012 5:25 pm
-
Martin Sleziak
- Posts: 5687
- Joined: Mon Jan 02, 2012 5:25 pm
Re: Prednášky LS 2023/24 - diskrétna matematika
11. prednáška (9.5.):
Fibonacciho čísla.
Trochu sme sa rozprávali o Fibonacciho číslach.
Povedali sme si definíciu a to, že ich vieme ľahko rozšíriť aj na záporné indexy. 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
Fibonacciho čísla.
Trochu sme sa rozprávali o Fibonacciho číslach.
Povedali sme si definíciu a to, že ich vieme ľahko rozšíriť aj na záporné indexy. 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
-
Martin Sleziak
- Posts: 5687
- Joined: Mon Jan 02, 2012 5:25 pm
Re: Prednášky LS 2023/24 - diskrétna matematika
12. prednáška (16.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$. Tu sme nerobili detailný dôkaz - ale aspoň sme stručne spomenuli jeden možný pohľad, že tieto veci súvisia s tým ako vyzerajú mocniny Jordanovho tvaru.
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?
Fibonacciho čísla.
Pozreli sme sa na kombinatorickú interpretáciu Fibonacciho čísel pomocou dláždení.
Pomocou nej sme potom ukázali, že platí $F_{n+1}=\sum\limits_{k=0}^\infty \binom{n-k}k$.
Dôkaz, ktorý sme urobili, je v texte na stránke - ale pridám aj nejaké linky:
* How to show that this binomial sum satisfies the Fibonacci relation?
* Fibonacci Numbers Proof: $ f_n = \binom n0 + \binom{n-1}1 +\dots+ \binom{n-k}k$
* Relation between Pascal's triangle and Fibonacci series.
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$. Tu sme nerobili detailný dôkaz - ale aspoň sme stručne spomenuli jeden možný pohľad, že tieto veci súvisia s tým ako vyzerajú mocniny Jordanovho tvaru.
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?
Fibonacciho čísla.
Pozreli sme sa na kombinatorickú interpretáciu Fibonacciho čísel pomocou dláždení.
Pomocou nej sme potom ukázali, že platí $F_{n+1}=\sum\limits_{k=0}^\infty \binom{n-k}k$.
Dôkaz, ktorý sme urobili, je v texte na stránke - ale pridám aj nejaké linky:
* How to show that this binomial sum satisfies the Fibonacci relation?
* Fibonacci Numbers Proof: $ f_n = \binom n0 + \binom{n-1}1 +\dots+ \binom{n-k}k$
* Relation between Pascal's triangle and Fibonacci series.