V tomto vlákne budem pravidelne dopĺňať, čo sa stihlo prebrať na jednotlivých prednáškach. (Napríklad to môže byť užitočné pre ľudí, ktorí z nejakého dôvodu nemohli prísť na prednášku - aby si mohli pozrieť, čo si treba doštudovať.)
Ak budete mať otázky k niečomu, čo odznelo na prednáškach, otvorte na to nový topic. (Tento topic by som chcel zachovať pre tento jediný účel.)
Prednášky LS 2023/24 - diskrétna matematika
-
Martin Sleziak
- Posts: 5689
- Joined: Mon Jan 02, 2012 5:25 pm
-
Martin Sleziak
- Posts: 5689
- Joined: Mon Jan 02, 2012 5:25 pm
Re: Prednášky LS 2023/24 - diskrétna matematika
1. prednáška (19.2):
Sčítací a násobiaci princíp.
Spomenuli sme niektoré základné kombinatorické princípy; konkrétne sčítací a násobiaci princíp.
Ako príklad použitia násobiaceho princípu sme odvodili počet permutácií, počet variácií a počet $k$-prvkových podmnožín $n$-prvkovej množiny.
Ako príklad použitia sčítacieho princípu som ukázal Pascalovu identitu.
Pri počte prvkov zobrazení z $A$ do $B$ sme na chvíľu odbočili k tomu, čomu sa rovná $0^0$, $0^n$ a $n^0$: viewtopic.php?t=343
Ako príklad princípu bijekcie sme ukázali, že $n$-prvková množina má práve $2^n$ podmnožín. Použili sme pri tom charekteristickú funkciu.
Ako príklad počítania dvoma spôsobmi sme ukázali, ako vyzerá súčet v riadku Pascalovho trojuholníka. (Súčasne sme spomenuli, že pri induktívnom dôkaze sa nám hodí konvencia, že $\binom nk=0$ v prípadoch $k<0$ aj $k>n$.)
Počítanie dvoma spôsobmi chceme použiť aj na zdôvodnenie hokejkovej identity; tu sme sa však zatiaľ k jej dôkazu nedostali; iba sme sa chvíľu hrali s Pascalovým trojuholníkom a po chvíli experimentovania sa nám podarilo uhádnuť, ako vyzerá súčet binomických koeficientov na diagonále.
Keďže na konci niekto spomenul, že tieto veci trochu pripomínajú integrál a deriváciu, tak pridám takúto linku: Analógie integrál/derivácia vs. suma/diferencie.
Dohodli sme sa, že od budúceho týždňa už budú prednášky vo štvrtok a utorok večer bude (raz za dva týždne) cviko. Tento týždeň je cvičenie ešte "po starom".
Sčítací a násobiaci princíp.
Spomenuli sme niektoré základné kombinatorické princípy; konkrétne sčítací a násobiaci princíp.
Ako príklad použitia násobiaceho princípu sme odvodili počet permutácií, počet variácií a počet $k$-prvkových podmnožín $n$-prvkovej množiny.
Ako príklad použitia sčítacieho princípu som ukázal Pascalovu identitu.
Pri počte prvkov zobrazení z $A$ do $B$ sme na chvíľu odbočili k tomu, čomu sa rovná $0^0$, $0^n$ a $n^0$: viewtopic.php?t=343
Ako príklad princípu bijekcie sme ukázali, že $n$-prvková množina má práve $2^n$ podmnožín. Použili sme pri tom charekteristickú funkciu.
Ako príklad počítania dvoma spôsobmi sme ukázali, ako vyzerá súčet v riadku Pascalovho trojuholníka. (Súčasne sme spomenuli, že pri induktívnom dôkaze sa nám hodí konvencia, že $\binom nk=0$ v prípadoch $k<0$ aj $k>n$.)
Počítanie dvoma spôsobmi chceme použiť aj na zdôvodnenie hokejkovej identity; tu sme sa však zatiaľ k jej dôkazu nedostali; iba sme sa chvíľu hrali s Pascalovým trojuholníkom a po chvíli experimentovania sa nám podarilo uhádnuť, ako vyzerá súčet binomických koeficientov na diagonále.
Keďže na konci niekto spomenul, že tieto veci trochu pripomínajú integrál a deriváciu, tak pridám takúto linku: Analógie integrál/derivácia vs. suma/diferencie.
Dohodli sme sa, že od budúceho týždňa už budú prednášky vo štvrtok a utorok večer bude (raz za dva týždne) cviko. Tento týždeň je cvičenie ešte "po starom".
-
Martin Sleziak
- Posts: 5689
- Joined: Mon Jan 02, 2012 5:25 pm
Re: Prednášky LS 2023/24 - diskrétna matematika
2. prednáška (29.2):
Hokejkovú identitu, ktorú sme spomenuli na konci minulej prednášky, sme dokázali na cvičeniach.
Permutácie s opakovaním. Počet permutácie pre $n_1,n_2,\dots,n_k$ rôznych typov prvkov a $n=n_1+n_2+\dots+n_k$ je
$$\binom n{n_1,n_2,\dots,n_k}=\frac{n!}{n_1!n_2!\cdots n_k!}.$$
Tomuto výrazu sa zvykne hovoriť aj multinomický koeficient..
Kombinácie s opakovaním a celočíselné riešenia. Počet kombinácii s opakovaním $k$-tej triedy z $n$ prvkov je rovný $$\binom{n+k-1}{k-1}=\binom{n+k-1}n.$$
Zdôvodnili sme ho pomocou stars and bars. (Povedali sme si, že pomerne priamočiaro by sa dal dokázať aj indukciou - ale každopádne túto metódu je užitočné poznať.)
Ten istý vzťah nám dá počet celočíselných riešení rovnice $x_1+\dots+x_k=n$ takých, že $x_i\ge0$.
Binomické koeficienty. Pripomenuli sme definíciu binomického koeficientu a niektoré základné vlastnosti (symetria, Pascalova identita.)
Binomická veta. Sfomulovali sme binomickú vetu v dvoch podobách:
\begin{gather*}
(1+t)^n=\sum_{k=0}^n \binom nk t^k\\
(x+y)^n=\sum_{k=0}^n \binom nk x^ky^{n-k}
\end{gather*}
Povedali sme si, ako sa dá dokázať - aj keď pri dôkaze indukciou som nerobil všetky detaily. (Spomenul som otázku, či platí binomická veta pre polia, okruhy, či sa dá aplikovať na matice - môžeme sa k tejto otázke niekedy vrátiť.)
Keď sme vhodne dosadili do binomickej vety, tak sme dostali, že pre $n\ge1$ platí
$$\sum_{k=0}^n (-1)^k \binom nk=0,$$
t.j. vlastne súčet binomických koeficientov v riadku Pascalovho trojuholníka so striedavými znamienkami. Ako dôsledok dostávame, že máme rovnako veľa podmnožín s párnym a s nepárnym počtom prvkov.
Potom sme ešte binomickú vetu zderivovali a zintegrovali, dostali sme takto identity: $\sum\limits_{k=0}^n k\binom nk = n2^{n-1}$ a $\sum\limits_{k=0}^n \frac1{k+1}\binom nk = \frac{2^{n+1}-1}{n+1}$.
Sľúbil som, že aspoň k niektorým identitám, ktoré sme dostali ako dôsledky binomickej vety, sa ešte vrátime aj na cvičeniach - pozrieme sa na možnosť iného dôkazu (indukciou, kombinatoricky, pomocou iných identít).
Hokejkovú identitu, ktorú sme spomenuli na konci minulej prednášky, sme dokázali na cvičeniach.
Permutácie s opakovaním. Počet permutácie pre $n_1,n_2,\dots,n_k$ rôznych typov prvkov a $n=n_1+n_2+\dots+n_k$ je
$$\binom n{n_1,n_2,\dots,n_k}=\frac{n!}{n_1!n_2!\cdots n_k!}.$$
Tomuto výrazu sa zvykne hovoriť aj multinomický koeficient..
Kombinácie s opakovaním a celočíselné riešenia. Počet kombinácii s opakovaním $k$-tej triedy z $n$ prvkov je rovný $$\binom{n+k-1}{k-1}=\binom{n+k-1}n.$$
Zdôvodnili sme ho pomocou stars and bars. (Povedali sme si, že pomerne priamočiaro by sa dal dokázať aj indukciou - ale každopádne túto metódu je užitočné poznať.)
Ten istý vzťah nám dá počet celočíselných riešení rovnice $x_1+\dots+x_k=n$ takých, že $x_i\ge0$.
Binomické koeficienty. Pripomenuli sme definíciu binomického koeficientu a niektoré základné vlastnosti (symetria, Pascalova identita.)
Binomická veta. Sfomulovali sme binomickú vetu v dvoch podobách:
\begin{gather*}
(1+t)^n=\sum_{k=0}^n \binom nk t^k\\
(x+y)^n=\sum_{k=0}^n \binom nk x^ky^{n-k}
\end{gather*}
Povedali sme si, ako sa dá dokázať - aj keď pri dôkaze indukciou som nerobil všetky detaily. (Spomenul som otázku, či platí binomická veta pre polia, okruhy, či sa dá aplikovať na matice - môžeme sa k tejto otázke niekedy vrátiť.)
Keď sme vhodne dosadili do binomickej vety, tak sme dostali, že pre $n\ge1$ platí
$$\sum_{k=0}^n (-1)^k \binom nk=0,$$
t.j. vlastne súčet binomických koeficientov v riadku Pascalovho trojuholníka so striedavými znamienkami. Ako dôsledok dostávame, že máme rovnako veľa podmnožín s párnym a s nepárnym počtom prvkov.
Potom sme ešte binomickú vetu zderivovali a zintegrovali, dostali sme takto identity: $\sum\limits_{k=0}^n k\binom nk = n2^{n-1}$ a $\sum\limits_{k=0}^n \frac1{k+1}\binom nk = \frac{2^{n+1}-1}{n+1}$.
Sľúbil som, že aspoň k niektorým identitám, ktoré sme dostali ako dôsledky binomickej vety, sa ešte vrátime aj na cvičeniach - pozrieme sa na možnosť iného dôkazu (indukciou, kombinatoricky, pomocou iných identít).
-
Martin Sleziak
- Posts: 5689
- Joined: Mon Jan 02, 2012 5:25 pm
Re: Prednášky LS 2023/24 - diskrétna matematika
3. prednáška (7.3.):
Binomické koeficienty.
Ukázali sme, že platí $k\binom nk = n \binom{n-1}{k-1}$: viewtopic.php?t=988
Použili sme ju na iné zdôvodnenie rovnosti $\sum\limits_{k=0}^n k\binom nk = n2^{n-1}$: viewtopic.php?t=1003
Dokázali sme Vandemondovu identitu - kombinatoricky cez počítanie komisií aj použitím binomickej vety na základe $(1+t)^{m+n}=(1+t)^m(1+t)^n$.
Princíp zapojenia a vypojenia.
Sformulovali sme princíp zapojenia a vypojenia a ukázali sme si nejaký dôkaz. Spomenul som, že by sa takýto dôkaz dal zapísať aj pomocou charakteristických funkcií - dá sa takýto dôkaz pozrieť v texte na stránke. (A spomenul som, že by sa dôkaz dal spraviť aj indukciou vzhľadom na počet množín.)
Permutácie bez pevného bodu.
Zatiaľ sme zadefinovali čo sú permutácie bez pevného bodu a vypisovaním všetkých možností sme spočítali $D_n$ pre $n=1,2,3,4$.
Dohodli sme sa, že cvičenia posunieme tak, že teraz budú 18. marca a potom 25. marca - keďže 2-týždňový interval od 18. marca by vyšiel na 1. apríl, čo je akurát ten pondelok, ktorý odpadne.
Binomické koeficienty.
Ukázali sme, že platí $k\binom nk = n \binom{n-1}{k-1}$: viewtopic.php?t=988
Použili sme ju na iné zdôvodnenie rovnosti $\sum\limits_{k=0}^n k\binom nk = n2^{n-1}$: viewtopic.php?t=1003
Dokázali sme Vandemondovu identitu - kombinatoricky cez počítanie komisií aj použitím binomickej vety na základe $(1+t)^{m+n}=(1+t)^m(1+t)^n$.
Princíp zapojenia a vypojenia.
Sformulovali sme princíp zapojenia a vypojenia a ukázali sme si nejaký dôkaz. Spomenul som, že by sa takýto dôkaz dal zapísať aj pomocou charakteristických funkcií - dá sa takýto dôkaz pozrieť v texte na stránke. (A spomenul som, že by sa dôkaz dal spraviť aj indukciou vzhľadom na počet množín.)
Permutácie bez pevného bodu.
Zatiaľ sme zadefinovali čo sú permutácie bez pevného bodu a vypisovaním všetkých možností sme spočítali $D_n$ pre $n=1,2,3,4$.
Dohodli sme sa, že cvičenia posunieme tak, že teraz budú 18. marca a potom 25. marca - keďže 2-týždňový interval od 18. marca by vyšiel na 1. apríl, čo je akurát ten pondelok, ktorý odpadne.
-
Martin Sleziak
- Posts: 5689
- Joined: Mon Jan 02, 2012 5:25 pm
Re: Prednášky LS 2023/24 - diskrétna matematika
4. prednáška (14.3.):
Permutácie bez pevného bodu.
Odvodili sme vyjadrenie pre $D_n$, t.j. počet permutácií bez pevného bodu pomocou PIE.
Počet surjektívnych zobrazení.
Vyjadrili sme pomocou PIE $\operatorname{Sur}(n,k)$, počet surjekcií z $n$-prvkovej množiny do $k$-prvkovej množiny.
Trochu sme potom odbočili k tomu, že počet $\operatorname{Sur}(n,k)$ pomerne prirodzeným spôsobom súvisí aj s počtom rozkladov $n$-prvkovej množiny na $k$ neprázdnych podmnožín, čo je vlastne definícia Stirlingovho čísla druhého druhu.
(Vo verzii textu, ktorá je na momentálne na stránke, je o Stirlingových číslach druhého druhu niečo napísané - ale veľmi málo, v podstate iba rekurencia, ktorú sme spomenuli na prednáške a súvis s počtom surjekcií. Každopádne keď sme dnes hovorili o niečom, čo s touto témou úzko súvisí, zdalo sa mi rozumné ich aspoň spomenúť.)
V súvislosti so vzťahom medzi surjekciami a rozkladmi resp. reláciami ekvivalencia pridám aj túto linku: viewtopic.php?t=1730
Permutácie bez pevného bodu.
Odvodili sme vyjadrenie pre $D_n$, t.j. počet permutácií bez pevného bodu pomocou PIE.
Počet surjektívnych zobrazení.
Vyjadrili sme pomocou PIE $\operatorname{Sur}(n,k)$, počet surjekcií z $n$-prvkovej množiny do $k$-prvkovej množiny.
Trochu sme potom odbočili k tomu, že počet $\operatorname{Sur}(n,k)$ pomerne prirodzeným spôsobom súvisí aj s počtom rozkladov $n$-prvkovej množiny na $k$ neprázdnych podmnožín, čo je vlastne definícia Stirlingovho čísla druhého druhu.
(Vo verzii textu, ktorá je na momentálne na stránke, je o Stirlingových číslach druhého druhu niečo napísané - ale veľmi málo, v podstate iba rekurencia, ktorú sme spomenuli na prednáške a súvis s počtom surjekcií. Každopádne keď sme dnes hovorili o niečom, čo s touto témou úzko súvisí, zdalo sa mi rozumné ich aspoň spomenúť.)
V súvislosti so vzťahom medzi surjekciami a rozkladmi resp. reláciami ekvivalencia pridám aj túto linku: viewtopic.php?t=1730
-
Martin Sleziak
- Posts: 5689
- Joined: Mon Jan 02, 2012 5:25 pm
Re: Prednášky LS 2023/24 - diskrétna matematika
5. prednáška (21.3.):
Eulerova funkcia
Ukázali sme si pomocou PIE vyjadrenie Eulerovej funkcie na základe kanonického rozkladu.
Z neho vieme odvodiť aj $\varphi(mn)=\varphi(m)\varphi(n)\frac{d}{\varphi(d)}$ pre $d=\gcd(m,n)$. (Okrem iného dostaneme to, že $\varphi(n)$ je multiplikatívna funkcia.)
Bez dôkazu sme spomenuli Eulerovu vetu a Malú Fermatovu vetu.
Riešenia rovnice $x_1+\dots+x_k=n$ s obmedzeniami. Už sme sa zaoberali počtom celočíselných riešení rovnice $x_1+\dots+x_k=n$, pričom sme mali dolné ohraničenia na jednotlivé premenné. Na cvičeniach sa pozrieme na to, ako sa PIE dá použiť, ak nám pribudnú aj horné ohraničenia. Nejaké takéto príklady sú vyriešené aj v texte na stránke.
Binomická veta s reálnym exponentom.
Povedali sme si, ako by fungovala binomická veta pre reálny exponent. (Tam sme dostali vyjadrenie pre $(1+x)^t$ v tvare nekonečného radu. Je to vlastne skôr téma týkajúca sa matematickej analýzy než diskrétnej matematiky - keďže však súvisí s tým čo sme preberali teraz, zdalo sa mi vhodné ju aspoň spomenúť.)
Spomenul som, že takáto veta platí a že ju dostanete ako špeciálny prípad Taylorovho radu. (Túto tému by ste mali na analýze prebrať niekedy v tomto semestri.)
Pozreli sme sa na to, čo dostaneme, keď exponent je $-1$; vyjadrili sme $\binom{-1}k$ a dopracovali sme sa ku geometrickému radu.
A tiež sme sa ešte pozreli na špeciálny prípad $t=-n$ pre prirodzené číslo $n$; videli sme, že to nejako súvisí s počtom nezáporných celočíselných riešení.
Wikipédia: Binomial series.
Eulerova funkcia
Ukázali sme si pomocou PIE vyjadrenie Eulerovej funkcie na základe kanonického rozkladu.
Z neho vieme odvodiť aj $\varphi(mn)=\varphi(m)\varphi(n)\frac{d}{\varphi(d)}$ pre $d=\gcd(m,n)$. (Okrem iného dostaneme to, že $\varphi(n)$ je multiplikatívna funkcia.)
Bez dôkazu sme spomenuli Eulerovu vetu a Malú Fermatovu vetu.
Riešenia rovnice $x_1+\dots+x_k=n$ s obmedzeniami. Už sme sa zaoberali počtom celočíselných riešení rovnice $x_1+\dots+x_k=n$, pričom sme mali dolné ohraničenia na jednotlivé premenné. Na cvičeniach sa pozrieme na to, ako sa PIE dá použiť, ak nám pribudnú aj horné ohraničenia. Nejaké takéto príklady sú vyriešené aj v texte na stránke.
Binomická veta s reálnym exponentom.
Povedali sme si, ako by fungovala binomická veta pre reálny exponent. (Tam sme dostali vyjadrenie pre $(1+x)^t$ v tvare nekonečného radu. Je to vlastne skôr téma týkajúca sa matematickej analýzy než diskrétnej matematiky - keďže však súvisí s tým čo sme preberali teraz, zdalo sa mi vhodné ju aspoň spomenúť.)
Spomenul som, že takáto veta platí a že ju dostanete ako špeciálny prípad Taylorovho radu. (Túto tému by ste mali na analýze prebrať niekedy v tomto semestri.)
Pozreli sme sa na to, čo dostaneme, keď exponent je $-1$; vyjadrili sme $\binom{-1}k$ a dopracovali sme sa ku geometrickému radu.
A tiež sme sa ešte pozreli na špeciálny prípad $t=-n$ pre prirodzené číslo $n$; videli sme, že to nejako súvisí s počtom nezáporných celočíselných riešení.
Wikipédia: Binomial series.
-
Martin Sleziak
- Posts: 5689
- Joined: Mon Jan 02, 2012 5:25 pm
Re: Prednášky LS 2023/24 - diskrétna matematika
28.3. bolo rektorské voľno.
6. prednáška (4.4.):
Multinomická veta. Sformulovali a zdôvodnili sme multinomickú vetu.
Grafy.
Definícia grafu, niektoré základné pojmy (vrcholy, hrany, stupeň, izomorfizmus grafov, podgraf, indukovaný podgraf kompletný graf).
Stromy.
Definícia cesty a kružnice. Definovali sme strom ako súvislý a acyklický graf.
Ukázali sme, že každý strom s aspoň dvoma vrcholmi má aj vrcholy stupňa 1. Ukázali sme, že pre vrchol stupňa 1 platí: $G$ je strom $\Leftrightarrow$ $G-v$ je strom.
Strom na $n$ vrcholoch má $n-1$ hrán. Ak súvislý graf na $n$ vrcholoch má $n-1$ hrán, tak je to strom.
6. prednáška (4.4.):
Multinomická veta. Sformulovali a zdôvodnili sme multinomickú vetu.
Grafy.
Definícia grafu, niektoré základné pojmy (vrcholy, hrany, stupeň, izomorfizmus grafov, podgraf, indukovaný podgraf kompletný graf).
Stromy.
Definícia cesty a kružnice. Definovali sme strom ako súvislý a acyklický graf.
Ukázali sme, že každý strom s aspoň dvoma vrcholmi má aj vrcholy stupňa 1. Ukázali sme, že pre vrchol stupňa 1 platí: $G$ je strom $\Leftrightarrow$ $G-v$ je strom.
Strom na $n$ vrcholoch má $n-1$ hrán. Ak súvislý graf na $n$ vrcholoch má $n-1$ hrán, tak je to strom.
-
Martin Sleziak
- Posts: 5689
- Joined: Mon Jan 02, 2012 5:25 pm
Re: Prednášky LS 2023/24 - diskrétna matematika
7. prednáška (11.4.):
Stromy.
Ukázali sme si ďalšie ekvivalentné charakterizácie stromov: minimálny súvislý graf, maximálny súvislý graf, existencia práve jednej cesty pre ľubovoľné dva vrcholy.
Planárne grafy.
Zadefinovali sme pojem planárneho (rovinného) grafu. Povedali sme si niečo o tom, čo myslíme pod rovinným nakreslením a ako počítame steny. Spomenuli sme stereografickú projekciu a to, že planárne grafy sú vlastne tie isté grafy, ktoré vieme nakresliť na guľu.
Viacero vecí sme spomínali skôr na intuitívnej úrovni než ako niečo, čo by bol úplne rigorózny dôkaz - špecificky spomeniem, že sme vlastne využívali Jordanovu vetu o krivkách; potrebovali sme vedieť, že uzavretá krivka rozdelí rovinu na dve oblasti.
Dokázali sme Eulerovu formulu: Pre súvislý planárny graf platí $v-h+s=2$.
Ako dôsledok sme dostali nerovnosť $h\le 3v-6$.
Stromy.
Ukázali sme si ďalšie ekvivalentné charakterizácie stromov: minimálny súvislý graf, maximálny súvislý graf, existencia práve jednej cesty pre ľubovoľné dva vrcholy.
Planárne grafy.
Zadefinovali sme pojem planárneho (rovinného) grafu. Povedali sme si niečo o tom, čo myslíme pod rovinným nakreslením a ako počítame steny. Spomenuli sme stereografickú projekciu a to, že planárne grafy sú vlastne tie isté grafy, ktoré vieme nakresliť na guľu.
Viacero vecí sme spomínali skôr na intuitívnej úrovni než ako niečo, čo by bol úplne rigorózny dôkaz - špecificky spomeniem, že sme vlastne využívali Jordanovu vetu o krivkách; potrebovali sme vedieť, že uzavretá krivka rozdelí rovinu na dve oblasti.
Dokázali sme Eulerovu formulu: Pre súvislý planárny graf platí $v-h+s=2$.
Ako dôsledok sme dostali nerovnosť $h\le 3v-6$.
-
Martin Sleziak
- Posts: 5689
- Joined: Mon Jan 02, 2012 5:25 pm
Re: Prednášky LS 2023/24 - diskrétna matematika
18.4. bolo dekanské voľno (ŠVK) - preto som tento týždeň rozprával ešte trochu o planárnych grafoch pondelok a príklady sme počítali potom ku koncu hodiny a ešte sa im budeme venovať vo štvrtok.
8. prednáška (25.4.):
Planárne grafy.
Graf $K_5$ nie je planárny.
Každý rovinný graf má vrchol stupňa nanajvýš $5$.
Ak graf nemá kružnicu dĺžky $3$, tak platí $h\le 2v-4$. Graf $K_{3,3}$ nie je planárny.
Našli sme aké sú možné počty vrcholov, hrán a stien ak máme rovinný graf taký, kde každý vrchol má rovnaký stupeň a každá stena rovnaký počet vrcholov - čo súvisí s platónskymi telesami.
*
Spomenuli sme, že existujú charakterizácie rovinných grafov takého typu, že grafy $K_{3,3}$ a $K_5$ sa nesmú "vyskytnúť" v danom grafe - aj keď sme nehovorili o detailoch. Ide o Kuratowského a Wagnerovu vetu.
Ukázal som ale aspoň to, že Petersenov graf nie je rovinný - do istej miery aj ako ilustráciu vecí, ktoré sa vyskytujú v týchto dvoch vetách. (Súčasne sa podobné úvahy ako sme použili tu dajú využiť aj v niektorých cvičeniach.)
8. prednáška (25.4.):
Planárne grafy.
Graf $K_5$ nie je planárny.
Každý rovinný graf má vrchol stupňa nanajvýš $5$.
Ak graf nemá kružnicu dĺžky $3$, tak platí $h\le 2v-4$. Graf $K_{3,3}$ nie je planárny.
Našli sme aké sú možné počty vrcholov, hrán a stien ak máme rovinný graf taký, kde každý vrchol má rovnaký stupeň a každá stena rovnaký počet vrcholov - čo súvisí s platónskymi telesami.
*
Spomenuli sme, že existujú charakterizácie rovinných grafov takého typu, že grafy $K_{3,3}$ a $K_5$ sa nesmú "vyskytnúť" v danom grafe - aj keď sme nehovorili o detailoch. Ide o Kuratowského a Wagnerovu vetu.
Ukázal som ale aspoň to, že Petersenov graf nie je rovinný - do istej miery aj ako ilustráciu vecí, ktoré sa vyskytujú v týchto dvoch vetách. (Súčasne sa podobné úvahy ako sme použili tu dajú využiť aj v niektorých cvičeniach.)
-
Martin Sleziak
- Posts: 5689
- Joined: Mon Jan 02, 2012 5:25 pm
Re: Prednášky LS 2023/24 - diskrétna matematika
9. prednáška (2.5.):
Farbenie grafov.
Zadefinovali sme $k$-farbiteľný graf a chromatické číslo grafu.
Pozreli sme sa na bipartitné (práne) grafy a ukázali sme si charakterizáciu, ktorá hovorí, že sú to presne tie grafy, ktoré neobsahujú kružnicu nepárnej dĺžky.
Dokázali sme vetu o piatich farbách: Každý rovinný graf sa dá ofarbiť piatimi farbami.
Spomenuli sme vetu o štyroch farbách, t.j. v skutočnosti platí silnejší výsledok - dôkaz je však oveľa náročnejší.
Eulerovské grafy. Charakterizáciu grafov, ktoré majú eulerovský ťah resp. uzavretý eulerovský ťah sme nechali na cvičenia. (Rozmysleli sme si ten smer, ktorý je ľahký.)
Farbenie grafov.
Zadefinovali sme $k$-farbiteľný graf a chromatické číslo grafu.
Pozreli sme sa na bipartitné (práne) grafy a ukázali sme si charakterizáciu, ktorá hovorí, že sú to presne tie grafy, ktoré neobsahujú kružnicu nepárnej dĺžky.
Dokázali sme vetu o piatich farbách: Každý rovinný graf sa dá ofarbiť piatimi farbami.
Spomenuli sme vetu o štyroch farbách, t.j. v skutočnosti platí silnejší výsledok - dôkaz je však oveľa náročnejší.
Eulerovské grafy. Charakterizáciu grafov, ktoré majú eulerovský ťah resp. uzavretý eulerovský ťah sme nechali na cvičenia. (Rozmysleli sme si ten smer, ktorý je ľahký.)