Řešené příklady

Kartezský součin a potenční množina

Ukážeme si, jak se k dané množině vytvoří potenční množina (množina všech podmnožin dané množiny) a pak si předvedeme, jak vypadá kartézský součin potenční množiny s jinou množinou.

Stáhnout ZDM01_Kartezsky_soucin_mnozin_a_potencni_mnozina.pdf a přehrát v přehrávači livescribe.com.

Suma Konstanty

Výraz v sumě může být funkce, která není závislá na indexu sumy, tedy se vůči indexu „chová“ konstantně. Ukážeme, jak stanovit výsledek takové sumy.

Stáhnout ZDM01_Suma_konstanty.pdf a přehrát v přehrávači livescribe.com.

Prázdná suma

Prázdná suma vznikne tak, že její index patří do prázdné množiny. Stanovíme výsledek prázdné sumy.

Stáhnout ZDM01_Prazdna_suma.pdf a přehrát v přehrávači livescribe.com.

Produkt konstanty

Výraz v produktu může být funkce, která není závislá na indexu produktu, tedy se vůči indexu „chová“ konstantně. Ukážeme, jak stanovit výsledek takového produktu.

Stáhnout ZDM01_Produkt_konstanty.pdf a přehrát v přehrávači livescribe.com.

Prázdný produkt

Prázdný produkt vznikne tak, že jeho index patří do prázdné množiny. Stanovíme výsledek prázdného produktu.

Stáhnout ZDM01_Prazdny_produkt.pdf a přehrát v přehrávači livescribe.com.

Kombinace bez opakování 1

Mějme 10 cvičenců a ptáme se, kolik existuje možností, jak je sestavit do pyramidy typu 4+3+2+1, pokud nerozlišujeme pořadí cvičenců v jednotlivých vrstvách.

Stáhnout ZDM02_KombinaceBezOpakovani_pyramida.pdf a přehrát v přehrávači livescribe.com.

Kombinace bez opakování 2

Předvedeme si, jak složitější úlohu rozdělit do jednotlivých případů tak, že konečný výsledek je součet výsledků z jednotlivých případů.

Stáhnout ZDM02_KombinaceBezOpakovani_rozkladPrikladuNaDisjunktniPripady.pdf a přehrát v přehrávači livescribe.com.

Permutace bez opakování 1

Ukážeme si, jak zjistit počet permutací bez opakování, jestliže žádáme, aby nějaké dva prvky stejného typu byly vedle sebe, přičemž v množině jsou právě dva takové prvky.

Stáhnout ZDM02_PermutaceBezOpakovani_dvaPrvkyVedleSebe_jednodussi.pdf a přehrát v přehrávači livescribe.com.

Permutace bez opakování 2

Ukážeme si, jak zjistit počet permutací bez opakování, jestliže žádáme, aby nějaké dva prvky stejného typu byly vedle sebe, přičemž v množině je více takových prvků.

Stáhnout ZDM02_PermutaceBezOpakovani_dvaPrvkyVedleSebe_sloziteji.pdf a přehrát v přehrávači livescribe.com.

Permutace bez opakování 3

Máme zjistit počet permutací, které splňují podmínku, jež je zapsána ve tvaru „Platí A právě tehdy, když platí B“, kde A, B jsou nějaké výroky

Stáhnout ZDM02_PermutaceBezOpakovani_sPodminkouVeTvaruEkvivalence.pdf a přehrát v přehrávači livescribe.com.

Permutace bez opakování 4

Máme zjistit počet permutací, které splňují podmínku, jež je zapsána ve tvaru „Jestliže platí A, pak platí B“, kde A ,B jsou nějaké výroky.

Stáhnout ZDM02_PermutaceBezOpakovani_sPodminkouVeTvaruImplikace.pdf a přehrát v přehrávači livescribe.com.

Kombinace s opakováním 1

Barvíme stejné figurky několika barvami tak, aby každá figurka byla jednobarevná, přičemž všechny figurky musí být obarveny. Ptáme se, kolik máme možností, jak figurky obarvit.

Stáhnout ZDM02_Kombinace_s_opakovanim_barveni_VSECH_stejnych_figurek.pdf a přehrát v přehrávači livescribe.com.

Kombinace s opakováním 2

Barvíme stejné figurky několika barvami tak, aby každá figurka byla jednobarevná, přičemž některé figurku mohou zůstat neobarveny. Ptáme se kolik máme možností, jak figurky obarvit

Stáhnout ZDM02_Kombinace_s_opakovanim_barveni_NEKTERYCH_stejnych_figurek.pdf a přehrát v přehrávači livescribe.com.

Kombinace s opakováním 3

Ptáme se, kolik existuje součtů s konkrétním počtem sčítanců a konkrétním celočíselným výsledkem, pokud je každý sčítanec větší než a, kde a je nezáporné celé číslo.

Stáhnout ZDM02_Kombinace_s_opakovanim_pocet_souctu_se_scitanci_vetsimi_nez_nula_konkretni.pdf a přehrát v přehrávači livescribe.com.

Kombinace s opakováním 4

Ptáme se, kolik existuje součtů s libovolným počtem sčítanců a libovolným přípustným celočíselným výsledkem, pokud je každý sčítanec větší než a, kde a je nezáporné celé číslo.

Stáhnout ZDM02_Kombinace_s_opakovanim_pocet_souctu_se_scitanci_vetsimi_nez_nula_obecny.pdf a přehrát v přehrávači livescribe.com.

Permutace s opakováním 1

Ukážeme si, jak zjistit počet permutací s opakováním, jestliže žádáme, aby nějaké dva stejné prvky byly vedle sebe, přičemž v množině jsou právě dva stejné prvky.

Stáhnout ZDM02_PermutaceSopakovanim_dvaStejnePrvkyVedle_jednodussi.pdf a přehrát v přehrávači livescribe.com.

Permutace s opakováním 2

Ukážeme si, jak zjistit počet permutací s opakováním, jestliže žádáme, aby nějaké dva stejné prvky byly vedle sebe, přičemž v množině je více takových stejných prvků.

Stáhnout ZDM02_Permutace_s_opakovanim_dva_stejne_prvky_vedle_sebe_slozitejsi.pdf a přehrát v přehrávači livescribe.com.

Variace s opakováním 1

Máme zjistit, kolik čísel dělitelných například 7 je v nějaké množině po sobě jdoucích přirozených čísel

Stáhnout ZDM02_Variace_s_opakovanim_pripravny_ukol.pdf a přehrát v přehrávači livescribe.com.

Variace s opakováním 2

Máme určit počet pěticiferných čísel, která jsou dělitelná 5.

Stáhnout ZDM02_Variace_s_opakovanim_pocet_vicecifernych_cisel_s_nejakou_delitelnosti.pdf a přehrát v přehrávači livescribe.com.

Náhodné jevy se stejnou pravděpodobností 1

Ukážeme, že dva náhodné jevy A a B mají stejnou pravděpodobnost. Přičemž jev A je „Prvních k karet v náhodně zamíchaném balíčku má jistou vlastnost“ a jev B je „Náhodně vybraných k karet v náhodně zamíchaném balíčku má jistou vlastnost“.

Stáhnout ZDM03_Balicek_karet_a_nahodne_jevy_se_stejnou_pravdepodobnosti1.pdf a přehrát v přehrávači livescribe.com.

Náhodné jevy se stejnou pravděpodobností 2

Ukážeme, že dva náhodné jevy A a B mají stejnou pravděpodobnost. Přičemž jev A je „Prvních k karet v náhodně zamíchaném balíčku má jistou vlastnost“ a jev B je „Náhodně vybraných k karet v náhodně zamíchaném balíčku má jistou vlastnost“.

Stáhnout ZDM03_Balicek_karet_a_nahodne_jevy_se_stejnou_pravdepodobnosti2.pdf a přehrát v přehrávači livescribe.com.

Náhodné jevy se stejnou pravděpodobností 3

Ukážeme, že dva náhodné jevy A a B mají stejnou pravděpodobnost. Přičemž jev A je „Prvních k karet v náhodně zamíchaném balíčku má jistou vlastnost“ a jev B je „Náhodně vybraných k karet v náhodně zamíchaném balíčku má jistou vlastnost“.

Stáhnout ZDM03_Balicek_karet_a_nahodne_jevy_se_stejnou_pravdepodobnosti3.pdf a přehrát v přehrávači livescribe.com.

Pravděpodobnost při hodu kostkou

Na konkrétním příkladu ukážeme častou chybu při výpočtu pravděpodobnosti. Může se totiž stát, že si vytvoříme pravděpodobnostní prostor tak, že pravděpodobnost NENÍ UNIFORMNÍ a přehlédneme to.

Stáhnout ZDM03_Pravdepodobnost_chybny_a_spravny_vypocet.pdf a přehrát v přehrávači livescribe.com.

Pravděpodobnost karetní postupka 1

Máme vypočítat pravděpodobnost, s jakou všechny vybrané karty z balíčku tvoří jednobarevnou postupku.

Stáhnout ZDM03_Pravdepodobnost_karetni_postupka_v_jedne_barve_jednodussi.pdf a přehrát v přehrávači livescribe.com.

Pravděpodobnost karetní postupka 2

Máme vypočítat pravděpodobnost, s jakou některé vybrané karty z balíčku tvoří jednobarevnou postupku.

Stáhnout ZDM03_Pravdepodobnost_karetni_postupka_v_jedne_barve_slozitejsi.pdf a přehrát v přehrávači livescribe.com.

Závislé a nezávislé jevy

Házíme dvakrát spravedlivou šestistěnnou kostkou a máme zjistit, zda dva nadefinované náhodné jevy jsou nebo nejsou nezávislé.

Stáhnout ZDM03_Zavislost_a_nezavislost_nahodnych_jevu_kostky.pdf a přehrát v přehrávači livescribe.com.

Relace ekvivalence na množině komplexních čísel

Na množině komplexních čísel je definována relace, o níž zjistíme, že je ekvivalence (reflexivní, symetrická, tranzitivní). Ukážeme si různé třídy této ekvivalence.

Stáhnout ZDM05_Relace_ekvivalence_na_mnozine_komplexnich_cisel.pdf a přehrát v přehrávači livescribe.com.

Permutace, cyklický zápis

Permutaci lze také chápat, jako bijekci (zobrazení, které je prosté a NA množinu) nějaké konečné množiny na sebe. Nejpřirozenější vyjádření permutace v tomto případě je zápis dvojřádkovou maticí, kde v prvním řádku jsou vzory a ve druhém obrazy této bijekce. My si ukážeme i jiný zápis permutace, a to pomocí disjunktních cyklů.

Stáhnout ZDM05_permutace_cyklicky_zapis.pdf a přehrát v přehrávači livescribe.com.

Permutace, inverzní permutace

Ke každé permutaci existuje permutace inverzní (Složíme-li permutaci s její inverzí, tak dostaneme vždy permutaci identickou). My se naučíme hledat tuto inverzní permutaci.

Stáhnout ZDM05_permutace_inverzni_permutace.pdf a přehrát v přehrávači livescribe.com.

Permutace, řád permutace

Každá permutace má svůj řád (je to nejmenší k takové, že když k krát složíme permutaci samu se sebou, tak dostaneme permutaci identickou). My zjistíme, jak se tento řád hledá.

Stáhnout ZDM05_permutace_rad_permutace.pdf a přehrát v přehrávači livescribe.com.

Permutace, skládání permutací

Složením dvou permutací vznikne opět permutace. Naučíme se permutace skládat, tedy najít permutaci, která je výsledkem onoho složení.

Stáhnout ZDM05_permutace_skladani_permutaci.pdf a přehrát v přehrávači livescribe.com.

Permutace, vysoká mocnina řádu permutace

Umocnit permutaci na vysoké číslo je velice pracné, pokud nevyužijeme řád permutace. Zde tedy využijeme řádu permutace ke zjištění poměrně vysoké mocniny zadané permutace.

Stáhnout ZDM05_permutace_vysoka_mocnina_uziti_radu_permutace.pdf a přehrát v přehrávači livescribe.com.

Částečné uspořádání, množinová inkluze na systému množin

O relaci „býti podmnožinou“ na nějakém systému množin zjistíme, že je částečné uspořádání. Zakreslíme Hasseův diagram částečně uspořádaného systému množin a určíme také jeho minimální, maximální, nejmenší a největší prvky.

Stáhnout ZDM05_castecne_usporadani_mnozinova_inkluze_na_systemu_mnozin.pdf a přehrát v přehrávači livescribe.com.

Diagram relace a matice relace

Máme zadánu relaci R výčtem prvků (taxativně). Určíme její diagram D(R) a matici M(R).

Stáhnout ZDM05_relace_diagram_a_matice_relace.pdf a přehrát v přehrávači livescribe.com.

Diagram relace a matice relace, vlastnosti

Máme zadánu relaci R pomocí diagramu D(R) a matice M(R). Je třeba zjistit její vlastnosti.

Stáhnout ZDM05_relace_z_diagramu_a_matice_urcit_vlastnosti.pdf a přehrát v přehrávači livescribe.com.

Relace ekvivalence, kongruence modulo 3

Na množině vybraných přirozených čísel je definována relace, o níž zjistíme, že je ekvivalence (reflexivní, symetrická, tranzitivní). Ukážeme si různé třídy této ekvivalence.

Stáhnout ZDM05_Relace_ekvivalence_kongruence_modulo_3.pdf a přehrát v přehrávači livescribe.com.

Relace, počet relací s danými vlastnostmi

Máme zjistit, kolik různých reflexivních a antisymetrických relací existuje na libovolné n prvkové množině.

Stáhnout ZDM05_relace_pocet_relaci_s_danymi_vlastnostmi.pdf a přehrát v přehrávači livescribe.com.

Inkluze a exkluze, dělitelnost

Mějme nějakou množinu po sobě jdoucích přirozených čísel. Chceme zjistit, kolik je v ní čísel, která nejsou dělitelná ani 5, ani 7, ani 11.

Stáhnout ZDM06_Princip_inkluze_a_exkluze_viceciferna_cisla_s_delitelnosti.pdf a přehrát v přehrávači livescribe.com.

Inkluze a exkluze, počet surjekcí 2

Máme slovní příklad, jehož řešení vede ke zjištění počtu surjekcí množiny M na množinu N (surjekce je takové zobrazení, že každý prvek z N je obrazem nějakého prvku z M). Pomocí speciálního tvaru principu inkluze a exkluze zjistíme počet zobrazení, která NEJSOU surjekce, a to už je jen krůček ke zjištění počtu surjekcí.

Stáhnout ZDM06_Princip_inkluze_exkluze_pocet_surjekci_2.pdf a přehrát v přehrávači livescribe.com.

Inkluze a exkluze, počet surjekcí 3

Máme slovní příklad, jehož řešení vede ke zjištění počtu surjekcí množiny M na množinu N (surjekce je takové zobrazení, kde každý prvek z N je obrazem nějakého prvku z M). Pomocí speciálního tvaru principu inkluze a exkluze zjistíme počet zobrazení, která NEJSOU surjekce, a to už je jen krůček ke zjištění počtu surjekcí.

Stáhnout ZDM06_Princip_inkluze_exkluze_pocet_surjekci_3.pdf a přehrát v přehrávači livescribe.com.

Inkluze a exkluze, počet surjekcí, výpočet s chybou

Máme slovní příklad, jehož řešení vede ke zjištění počtu surjekcí množiny M na množinu N (surjekce je takové zobrazení, že každý prvek z N je obrazem nějakého prvku z M). V první fázi si ukážeme řešení tohoto příkladu, které sice vypadá rozumně, ale je úplně špatně.

Stáhnout ZDM06_Princip_inkluze_a_exkluze_pocet_surjekci1_(chybny_vypocet).pdf a přehrát v přehrávači livescribe.com.

Graf a podgraf

Sada příkladů, na kterých se ukáže a pojem podgrafu. Ukážeme, že existence podgrafů dlouhých cest si vynutí existenci podgrafů kratších cest, naproti tomu existence podgrafů dlouhých cyklů nezaručí existenci podgrafů kratších cyklů.

Stáhnout UTG01_grafy_a_podgrafy.pdf a přehrát v přehrávači livescribe.com.

Izomorfismus grafu, nalezení izomorfismu

Dva grafy jsou isomorfní, jestliže mají stejnou strukturu. Z nakreslení grafu obvykle není snadné rozpoznat, zda grafy jsou nebo nejsou isomorfní. Ukážeme jeden z postupů, které lze pro nalezení isomorfismu použít

Stáhnout UTG01_izomorfni_grafy_nalezeni_izomorfismu.pdf a přehrát v přehrávači livescribe.com.

Izomorfismus grafu, neizomorfní grafy

Dva grafy jsou isomorfní, jestliže mají stejnou strukturu. Z nakreslení grafu obvykle není snadné rozpoznat, zda grafy jsou nebo nejsou isomorfní. Ukážeme, že porovnání okolí významných vrcholů může pomoci rozpoznat, zda dva grafy nejsou isomorfní.

Stáhnout UTG01_neizomorfni_grafy_stupne_sousedu.pdf a přehrát v přehrávači livescribe.com.

Izomorfismus grafu, neizomorfní podgrafy

Dva grafy jsou isomorfní, jestliže mají stejnou strukturu. Z nakreslení grafu obvykle není snadné rozpoznat, zda grafy jsou nebo nejsou isomorfní. Isomorfní grafy musí mít stejnou množinu podgrafů. Ukážeme, jak porovnáním unikátních podgrafů můžeme isomorfismus vyloučit

Stáhnout UTG01_neizomorfni_grafy_neizomorfni_indukovane_podgrafy.pdf a přehrát v přehrávači livescribe.com.

Izomorfismus grafu,využití doplňků grafů

Každému grafu je jednoznačně přiřazena stupňová posloupnost. Ukážeme, že naopak stejnou stupňovou posloupnost mohou mít různé grafy. Také ukážeme, jak v diskuzi využít doplněk grafu.

Stáhnout UTG01_neizomorfni_grafy_vyuziti_doplnku_grafu.pdf a přehrát v přehrávači livescribe.com.

Věta Havel-Hakimi, negrafová posloupnost

Na příkladu ukážeme, jak s využitím Věty Havla-Hakimiho zdůvodnit, že daná posloupnost není stupňovou posloupností žádného grafu.

Stáhnout UTG01_veta_Havel_Hakimi_dana_posloupnost_neni_grafova.pdf a přehrát v přehrávači livescribe.com.

Věta Havel-Hakimi, rekonstrukce grafu

Ukážeme, jak využít Větu Havla-Hakimiho ke konstrukci grafu s danou stupňovou posloupností.

Stáhnout UTG01_veta_Havel_Hakimi_rekonstrukce_grafu.pdf a přehrát v přehrávači livescribe.com.

Věta Havel-Hakimi, nerekonstruovatelny graf

Ukážeme, že NE KAŽDÝ graf lze získat postupem, kterým se konstruuje graf dle Věty Havla-Hakimiho. Postup zaručí nalezení je NĚKTERÉHO grafu s danou stupňovou posloupností.

Stáhnout UTG01_veta_Havel_Hakimi_nerekonstruovatelny_graf.pdf a přehrát v přehrávači livescribe.com.

Souvislý graf a minimální počet hran

Ukážeme, jak využít základní tvrzení o stromech: stromy jsou nejmenší grafy vzhledem k počtu hran.

Stáhnout UTG02_Souvisly_graf_s_min_hran.pdf a přehrát v přehrávači livescribe.com.

Komponenty a minimální počet hran

Stromy jsou nejmenší grafy vzhledem k počtu hran. Ukážeme, že tento poznatek můžeme využít i pro nesouvislé grafy a najít nemenší počet hran grafu s předepsaným počtem komponent.

Stáhnout UTG02_Graf_3komponenty_s_min_hran.pdf a přehrát v přehrávači livescribe.com.

Počet komponent, graf s danými parametry

S využitím principu sudosti a s využitím známých vlastností kompletní grafů ukážeme, zda existují grafy s předepsaným počtem vrcholů a hran, které jsou souvislé, nebo které mají předepsaný počet komponent.

Stáhnout UTG02_3_Pocet_komponent_graf_s_danymi_parametry.pdf a přehrát v přehrávači livescribe.com.

Počet komponent, graf s danými parametry 2

S využitím principu sudosti a s využitím známých vlastností kompletních grafů ukážeme, zda existují grafy s předepsaným počtem vrcholů a hran, které mají předepsaný počet komponent.

Stáhnout UTG02_pocet_komponent_grafu_s_danymi_parametry2.pdf a přehrát v přehrávači livescribe.com.

>Počet komponent, graf s daným maximálním stupněm

Ukážeme, zda existují grafy s předepsaným počtem vrcholů a hran a s předepsanou stupňovou posloupností, které jsou souvislé, nebo které mají dvě komponenty.

Stáhnout UTG02_4_Pocet_komponent_graf_s_danymi_parametry_max_stupen.pdf a přehrát v přehrávači livescribe.com.

Počet komponent, graf s danými parametry, neexistuje

S využitím základních vlastností grafů ověříme, zda existuje graf s předepsaným počtem vrchol, hran a s předepsanou stupňovou posloupností

Stáhnout UTG02_5_Pocet_komponent_graf_s_danymi_parametry_neexistuje.pdf a přehrát v přehrávači livescribe.com.

Vyšší stupně souvislosti

Na příkladu ukážeme základní myšlenky, které se využívají při určení vrcholového a hranového stupně souvislosti daného grafu

Stáhnout UTG02_6_Vyssi_stupne_souvislosti.pdf a přehrát v přehrávači livescribe.com.

Vyšší stupně souvislosti 2

Na příkladu ukážeme základní myšlenky, které se využívají při určení vrcholového a hranového stupně souvislosti daného grafu.

Stáhnout UTG02_vyssi_stupne_souvislosti03.pdf a přehrát v přehrávači livescribe.com.

Eulerovské grafy 1

Eulerovský graf lze nakreslit jedním uzavřeným tahem. Ukážeme na příkladu, že nutnou a postačující podmínkou, aby graf byl eulerovský, je souvislost grafu spolu se sudostí všech stupňů.

Stáhnout UTG03_Eulerovske_grafy1.pdf a přehrát v přehrávači livescribe.com.

Eulerovské grafy 2

Eulerovský graf lze nakreslit jedním uzavřeným tahem. Na příkladu ukážeme, že stačí ověřit souvislost a sudost všech stupňů. Uvedeme příklad uzavřeného eulerovského tahu.

Stáhnout UTG03_Eulerovske_grafy2.pdf a přehrát v přehrávači livescribe.com.

Eulerovské grafy 3

Eulerovský graf lze nakreslit jedním uzavřeným tahem. Ukážeme, že aby graf byl eulerovský, tak nestačí, aby všechny vrcholy byly sudého stupně. Druhou nutnou podmínkou je souvislost grafu.

Stáhnout UTG03_Eulerovske_grafy3.pdf a přehrát v přehrávači livescribe.com.

Hamiltonovské grafy

V hamiltonovském grafu existuje cyklus, který obsahuje každý vrchol daného grafu. Na příkladech ukážeme, jednu nutnou a jednu postačující podmínku existence hamiltonovského cyklu v daném grafu.

Stáhnout UTG03_hamiltonovske_grafy.pdf a přehrát v přehrávači livescribe.com.

Sestavení metriky grafu

Metrika grafu je funkce která každé dvojici vrcholů přiřadí jejich vzdálenost. Na příkladech ukážeme konstrukci metriky pro konkrétní graf i obecný přístup k sestavení metriky cest.

Stáhnout UTG04_Vzdalenost_a_metrika_grafu.pdf a přehrát v přehrávači livescribe.com.

Základní vlastnosti stromů 1

Acyklický graf neobsahuje cykly, avšak nemusí být souvislý. Víme-li, kolik má acyklický graf vrcholů a kolik má hran, umíme určit počet komponent.

Stáhnout UTG05_zakladni_vlastnosti_stromu.pdf a přehrát v přehrávači livescribe.com.

Zakladní vlastnosti stromů 2

Každý strom s n vrcholy má právě n-1 hran. Toto tvrzení lze využít při sestavování koster grafu. Je jasné, kolik hran musí být odebráno, aby vznikl acyklický souvislý podgraf (strom).

Stáhnout UTG05_zakladni_vlastnosti_stromu02.pdf a přehrát v přehrávači livescribe.com.

Centrum stromu

Centrum stromu je určeno jednoznačně a lze jej najít rekurzivním postupem. Na dvou příkladech ukážeme nalezení centra.

Stáhnout UTG05_Stromy_vyhledani_centra_stromu.pdf a přehrát v přehrávači livescribe.com.

Kód a minimální kód stromu

Kód uspořádaného kořenového stromu je jednoznačně určen a naopak každý kód jednoznačně určuje uspořádaný kořenový strom. Každý kořenový strom (ne nutně uspořádaný kořenový strom) má jednoznačně určený minimální kód, který lze využít při rozhodování o isomorfismu stromů. Příklad ukazuje rozdíl mezi minimálním kódem kořenového stromu a kódem uspořádaného kořenového stromu.

Stáhnout UTG05_KorenoveStromy_rozdilMeziKodemAminimalnimKodemKorenovehoStromu.pdf a přehrát v přehrávači livescribe.com.

Rekostrukce stromu podle jeho kódu

Kód uspořádaného kořenového stromu je jednoznačně určen a naopak každý kód jednoznačně určuje uspořádaný kořenový strom. Tento příklad ukazuje, jak dle kódu zrekonstruovat uspořádaný kořenový strom.

Stáhnout UTG05_KorenoveStromy_rekonstrukceKorenovehoStromuPodleJehoKodu.pdf a přehrát v přehrávači livescribe.com.

Izomorfismus stromu

Každý kořenový strom (ne nutně uspořádaný kořenový strom) má jednoznačně určený minimální kód, který lze využít při rozhodování o isomorfismu stromů. Na příkladu ukážeme, jak lze kódy stromů využít k rozpoznání isomorfismu dvou stromů.

Stáhnout UTG05_KorenoveStromy_isomorfismusStromu.pdf a přehrát v přehrávači livescribe.com.

Minimální kostra - Borůvkův algoritmus

Minimální kostra souvislého grafu, je takový faktor, který je souvislý, je stromem a má nejmenší součet ohodnocení hran. Na příkladu ukážeme postup hledání minimální kostry souvislého grafu užitím Borůvkova algoritmu.

Stáhnout UTG05_minimalni_kostra_sBoruvkuv.pdf a přehrát v přehrávači livescribe.com.

Minimální kostra - Greedy algoritmus

Minimální kostra souvislého grafu, je takový faktor, který je souvislý, je stromem a má nejmenší součet ohodnocení hran. Na příkladu ukážeme postup hledání minimální kostry souvislého grafu užitím hladového (Kruskalova) algoritmu.

Stáhnout UTG05_minimalni_kostra_greedy_o.pdf a přehrát v přehrávači livescribe.com.

Minimální kostra - Jarníkuv algoritmus

Minimální kostra souvislého grafu, je takový faktor, který je souvislý, je stromem a má nejmenší součet ohodnocení hran. Na příkladu ukážeme postup hledání minimální kostry souvislého grafu užitím Jarníkova (Primova) algoritmu.

Stáhnout UTG05_minimalni_kostra_Jarnik_o.pdf a přehrát v přehrávači livescribe.com.

Chromatické číslo - horní odhad

Chromatické číslo grafu G (též barevnost grafu G) je nejmenší nutný počet barev pro dobré vrcholové obarvení grafu G. Obarvením grafu dostaneme obvykle jen horní odhad chromatického čísla, pro určení chromatického čísla potřebujeme zpravidla další argumenty.

Stáhnout UTG06_barveni_grafu_horni_odhad.pdf a přehrát v přehrávači livescribe.com.

Chromatické číslo - dolní odhad

Chromatické číslo grafu G (též barevnost grafu G) je nejmenší nutný počet barev pro dobré vrcholové obarvení grafu G. Dolní odhad počtu barev obvykle vyplývá z existence podgrafů ,které si vynutí velký počet barev. Avšak, pro určení chromatického čísla potřebujeme zpravidla další argumenty.

Stáhnout UTG06_chromaticke_cislo_dolni_odhad.pdf a přehrát v přehrávači livescribe.com.

Chromatické číslo - Časté chyby 1

Chromatické číslo grafu G (též barevnost grafu G) je nejmenší nutný počet barev pro dobré vrcholové obarvení grafu G. Častou chybou studentů je, že nalezené barvení považují za důkaz nutného počtu barev. Na jednoduchém příkladu ukážeme, že tomu tak není a jak postupovat pečlivěji.

Stáhnout UTG06_chromaticke_cislo_caste_chyby.pdf a přehrát v přehrávači livescribe.com.

Chromatické číslo - Časté chyby 2

Chromatické číslo grafu G (též barevnost grafu G) je nejmenší nutný počet barev pro dobré vrcholové obarvení grafu G. Při určení barevnosti můžeme využít Brooksovu větu, bohužel obvyklou chybou je chybné porozumění tvrzení této věty. Na příkladu ukážeme, čeho se vyvarovat a jak správně tvrzení věty využít.

Stáhnout UTG06_chromaticke_cislo_caste_chyby02.pdf a přehrát v přehrávači livescribe.com.

Užití Eulerova vzorce

Eulerův vzorec je velmi silné tvrzení, které ukazuje, že mezi počtem, hran, vrcholů a oblastí rovinného grafu je souvislost. Tuto vazbu ukážeme na příkladu, kdy ze známých parametrů určíme počet vrcholů grafu aniž bychom graf konstruovali.

Stáhnout UTG06_uziti_Eulerova_vzorce_pravid_20sten.pdf a přehrát v přehrávači livescribe.com.

Užití Eulerova vzorce, pravidelný šestistěn

Z Eulerova vzorce lze odvodit horní mez pro počet hran rovinného grafu. Tuto mez využijeme při řešení příkladu konstrukce rovinného grafu s předepsanými parametry.

Stáhnout UTG06_vyuziti_dusledku_Eulerova_vzorce_pravidelny_sestisten.pdf a přehrát v přehrávači livescribe.com.

Důsledky Eulerova vzorce

Častou chybou je špatné pochopení důsledků Eulerova vzorce. Jestliže nutná podmínka rovinnosti je splněna, neznamená to, že graf je rovinný. Naopak splnění postačující podmínky znamená rovinnost. Na příkladu ukážeme ověření podmínek.

Stáhnout UTG06_Dusledky_Eulerova_vzorce_rovinny_graf.pdf a přehrát v přehrávači livescribe.com.

Rozdělení(subdivize grafu)

Rozdělení grafy je důležitý pojem, který hraje zásadní roli při učení rovinnosti daného grafu. Na příkladu ukážeme, co je a co není rozdělení grafu.

Stáhnout UTG06_rozdeleni(subdivize)_grafu.pdf a přehrát v přehrávači livescribe.com.

Rezerva nenasycené cesty

Rezerva nenasycené cesty je minimum rezerv jednotlivých hran. Zatímco rezerva hrany orientované ve směru nenasycené cesty je dána rozdílem kapacity a toku, tak rezerva hrany orientované proti směru nenasycené cesty je dána hodnotou toku hranou

Stáhnout UTG07_toky_v_sitich_rezerva_nenasycene_cesty.pdf a přehrát v přehrávači livescribe.com.

Největší tok, nejmenší řez

Stáhnout UTG07_toky_nejvetsi_tok_nejmensi_rez.pdf a přehrát v přehrávači livescribe.com.