Matematické Fórum

Každý strom je acyklický, ale ne naopak! Uvaž třeba graf na pěti vrcholech s žádnou hranou -- ten určitě cyklus neobsahuje, ale není to strom. Kdybychom počítali počet komponent stromu, bylo by to triviální: strom je totiž z definice souvislý, neboli má právě jednu komponentu.

Ale myslím si, že na to jdeš ze správné strany. Každá komponenta acyklického grafu je totiž strom. Zajímá tě tedy, kolik stromů se dá vyrobit, když máš k dispozici 21 vrcholů a 14 hran. (Dodám, že graf tvořený právě jediným vrcholem je také strom.)

↑ mysteriouss:

O žádném vzorci z hlavy nevím. Důkaz, že počet komponent bude vždy stejný, je asi hlavní složkou tohohle úkolu. Po zběžném promyšlení si myslím, že ten důkaz by neměl být nijak těžký. (Nechci napovídat příliš -- pan Kovář se tu určitě brzo dostaví osobně a poskytne případnou další nápovědu dle svých představ, jak byste ten úkol měli řešit.)

Nakonec to vypadá, že vzorec existuje a je poměrně jednoduchý.

Když G je acyklický, pak musí platit , kde je počet komponent.

Proč? Indukcí podle c. Když je c = 1, znamená to, že graf je souvislý a protože je i acyklický, tak je to strom, a pro strom platí .

Nechť je c > 1. Zvolím si dvě libovolné komponenty a spojím je hranou, označím ji -- tím získám graf , kde . Tím jsem do grafu jednu hranu přidal a snížil jsem celkový počet komponent o 1. Podle indukčního předpokladu platí , kde je počet komponent grafu G'. Ale protože c' = c - 1 a |E'| = |E| + 1, tak . A je dokázáno.

A že z toho vzorce se na výsledek přijde snadno je asi jasné.

↑ mysteriouss:Existuje několik jednoduchých řešení a použití vzorce, který jsme na přednášce neměli, je diskutabilní.
Pokud vzorec během písemky dokážeme, tak zvolme takovou metodu, aby důkaz byl co nejpřehlenější.

Jedno možné řešení (i s podrobným komentářem):
Acyklický graf je podle definice les a každá jeho komponenta je strom. Označme hledaný počet komponent a počet vrcholů v každé komponentě.
Podle věty z přednášek víme, že každá komponenta s vrcholy má právě hran a celkem všech hran je 14. To znamená, že , protože všech vrcholů je dohromady 21.
Porovnáním levé a pravé strany dostaneme . Snadno vyjádříme hledaný počet komponent .

Existují i jiná krátká zdůvodnění. Jedno z nich (postavené na podobné myšlence jako Jarníkův nabo Borůvkův algoritmus) by mohlo třeba začínat:
Mějme 21 izolovaných vrcholů. Takový graf je les a má 21 komponent. Přdáním hrany do komponenty (která je stromem) vznikne cyklus (má takovou větu) a aby přidáním 14 hran nevznikl cyklus, musí každá přidaná hrana vždy spojovat vrcholy z RŮZNÝCH komponent. Předáním jedné hrany se počet komponent sníží o ....{důkaz dokončíte sami}

Nejčastější chybou na písemce byla záměna obecného za konkrétní. Tj. student nakreslil nějaký les (= acyklický graf), který měl požadovaný počet vrcholů i hran, spočítal počet komponent svého příkladu a bez jakéhokoliv komentáře tvrdil, že to je řešení vždy. Je sice pravda, že každý acyklický graf s daným počtem vrcholů a hran má stejný počet komponent, ale porč to platí? Smyslem příkladu bylo zdůvodnit, že tomu tak opravdu je a ne jen nakreslit příklad.

I bakalář na VŠ musí poznat, že je rozdíl, mezi obecným tvrzením a příkladem, který sice tvrzení splňuje, ale nijak je nedokazuje.
Současně je naivní si myslet, že vysokoškolsky vzdělaný člověk vyřeší všechny úkoly dosazením do nějakého vzorce. Musíme uvažovat!

Také se mi zdá jednoduší řešení tou indukcí.

K tomu jak píšete, že použití vzorce, který na přednášce nebyl je diskutabilní, můžete mi objasnit z jakého důvodu? Jen proto, že na přednášce nebyl? Zdá se mi jako hloupost diskutovat o správném řešení jen proto, že bylo vyřešeno jiným (samozřejmě správným) způsobem než by jste chtěl vy.

↑ Oxyd:Mně se uvedený důkaz moc nelíbí. Dvě hlavní výhrady.
1) Aby platil vztah , musí být graf acyklický. Nikde se v indukčním kroku nezdůvodňilo, že graf je také acyklický.
2) Uvedený důkaz čtu spíš jako "má-li acyklický(!)graf vrcholů a komponent, tak má hran. Všimněte si, že jde o jinou implikaci a proto se NEJEDNÁ o ekvivalentní tvrzení! (Na písemce bych samozřejmě takový puntičkář nebyl a uvedený důkaz by byl za plný počet bodů.)
Přijde mi přehlednější vést indukci přes počet hran a počet komponent grafu dopočítat. S tím souvisí i druhý navrhovaný postup v jednom z předchozích příspěvků.

↑ mysteriouss:V posledním odstavci vidím pouze diskuzi týkající se počtu prvků nějakých množin. O tom, že by v grafu nemohl být cyklus nevidím ani slovo.

↑ mysteriouss:

Napádaš človeka, ktorý sa k Tebe agresívne nesprával. Fórum je určené na pomoc ľuďom, ktorí ju potrebujú a nie na agresívne prejavy. Alebo žeby (anonymný) študent mal vždy pravdu a nikdy sa nemýlil?

Citujem

Když není možné, abychom se scházeli osobně (není to ani třeba), můžeme se scházet v duševním styku pomocí písemných projevů; vždyť i slunce každodenně probíhá od jedněch národů k druhým po celém okrsku světa a poskytuje stejně všem přiležitost, aby jednali o užitečných věcech...
Nuže, užijme, my lidé, přiležitosti, jež se nám skytaji, a nelze-li co projednat osobně, sdělujme si to přece navzájem tím způsobem, že místo řeči bude nám sloužit pero. A přitom nic nebude bránit, abychom nejednali  i osobně v menších kroužcích a nerozmlouvali spolu ... a pak také sami přikládajíce ruku k dílu.