Matematické Fórum

Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.

Nástěnka
22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.

Nejste přihlášen(a). Přihlásit

#1 03. 02. 2011 16:53 — Editoval mysteriouss (03. 02. 2011 16:56)

mysteriouss
Příspěvky: 47
Reputace:   -1 
 

acyklicky graf

Máme acyklický graf G s 21 vrcholy a 14 hranami. Určete počet komponent grafu G a své tvrzení zdůvodněte.

Mohl by mi prosím někdo objasnit jak se to děla? Hledal jsem v přednáškách pana kováře a nic, google taky mlčí, ví o co to je acyklický graf, ale jak se počítají komponenty odmítá prozradit.

Co jsem se dočetl tak acyklický graf je strom. Tak mě napadlo ze počet komponent je roven |V|+|E| tj. celkem že má komponent 21+14=35.

Offline

  • (téma jako vyřešené označil(a) mysteriouss)

#2 03. 02. 2011 18:59

mysteriouss
Příspěvky: 47
Reputace:   -1 
 

Re: acyklicky graf

teď mě napadlo, mela být odpověď 0? jelikož acyklický graf = strom a pokud víme, že pro strom platí |V| = |E| + 1 a po dosazení 21 se nerovná 15, tudíž acyklický graf neudělám.

Offline

 

#3 03. 02. 2011 19:04

Oxyd
Příspěvky: 614
Škola: MFF UK, teoretická informatika
Pozice: Student
Reputace:   31 
 

Re: acyklicky graf

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.)


Mýlím se častěji, než bych chtěl. Pokud vám v mém příspěvku něco nehraje, neváhejte se zeptat.
Jsem stále mlád a je mi příjemnější tykání. :)

Offline

 

#4 03. 02. 2011 19:19

mysteriouss
Příspěvky: 47
Reputace:   -1 
 

Re: acyklicky graf

takže výsledek bude 7 pro několik různých grafů jestli to chápu dobře, pokud spojím pomocí 14 hran 15 vrcholů tak budu mít 1 komponent + 6 zbylých vrcholů je budu mít 7 komponent .. nebo pokud např. spojím 7 hranama 8 vrcholů mám jeden komponent + 7 hranama 8 vrcholů mám další komponent a zbude 5 vrcholů tak mám opět 7 komponent ... a je jen na mě jaký graf si vyrobím.

Ještě byc hse chtěl zeptat jaký je pro to vzorec nikde jsem ho nenašel tedy alespoň google o žádném neví. Pochybuji totiž že kdybych na písemce nakreslil nějaký ten graf tak že dostanu plný počet bodů jelikož by se po mě chtěl důkaz, že to tak bude vždy.

Offline

 

#5 03. 02. 2011 19:41

Oxyd
Příspěvky: 614
Škola: MFF UK, teoretická informatika
Pozice: Student
Reputace:   31 
 

Re: acyklicky graf

↑ 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.)


Mýlím se častěji, než bych chtěl. Pokud vám v mém příspěvku něco nehraje, neváhejte se zeptat.
Jsem stále mlád a je mi příjemnější tykání. :)

Offline

 

#6 03. 02. 2011 19:44 — Editoval mysteriouss (03. 02. 2011 19:57)

mysteriouss
Příspěvky: 47
Reputace:   -1 
 

Re: acyklicky graf

myslím že napovědět už můžeš kolik chceš ... tento příklad jsem měl dnes na zkoušce na které jsem neuspěl tak bych se rád přiučil co jsem dnes viděl poprvé v životě :)

Offline

 

#7 03. 02. 2011 19:59

Oxyd
Příspěvky: 614
Škola: MFF UK, teoretická informatika
Pozice: Student
Reputace:   31 
 

Re: acyklicky graf

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

Když G je acyklický, pak musí platit $|V| - c = |E|$, kde $c$ 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í $|V| - 1 = |E|$.

Nechť je c > 1. Zvolím si dvě libovolné komponenty a spojím je hranou, označím ji $e$ -- tím získám graf $G' = (V, E')$, kde $E' = E \cup \{ e \}$. 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í $|V| - c' = |E'|$, kde $c'$ je počet komponent grafu G'. Ale protože c' = c - 1 a |E'| = |E| + 1, tak $|V| + c' = |E'| \Leftrightarrow |V| - (c - 1) = |E| + 1 \Leftrightarrow |V| + c = |E|$. A je dokázáno.

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


Mýlím se častěji, než bych chtěl. Pokud vám v mém příspěvku něco nehraje, neváhejte se zeptat.
Jsem stále mlád a je mi příjemnější tykání. :)

Offline

 

#8 03. 02. 2011 20:05 — Editoval mysteriouss (03. 02. 2011 20:13)

mysteriouss
Příspěvky: 47
Reputace:   -1 
 

Re: acyklicky graf

mockrat děkuji vědět ten vzorec |V|-c = |E| mohlo byt u zkoušky vše jinak :D
c = |V|-|E| ... k mojí smůle jsem vymyslel vzorec ale vymyslel jsem ho se špatným znaménkem dal jsem  21+14 a ono to ma byt 21-14 :)
ještě jednom moc díky za ochotu a vysvětlení.

jen $|V| + c' = |E'| \Leftrightarrow |V| - (c - 1) = |E| + 1 \Leftrightarrow |V| + c = |E|$
nemělo být $|V| - c' = |E'| \Leftrightarrow |V| - (c - 1) = |E| + 1 \Leftrightarrow |V| - c = |E|$ ??

Offline

 

#9 04. 02. 2011 09:39

petrkovar
Veterán
Místo: Ostrava/Krmelín
Příspěvky: 1004
Pozice: VŠB - TU Ostrava
Reputace:   23 
Web
 

Re: acyklicky graf

↑ 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 $k$ hledaný počet komponent a $n_1, n_2, \dots, n_k$ počet vrcholů v každé komponentě.
Podle věty z přednášek víme, že každá komponenta s $n_i$ vrcholy má právě $n_i-1$ hran a celkem všech hran je 14. To znamená, že $14=\sum_{i=1}^{k}(n_i-1) = \sum_{i=1}^{k}(n_i)-k = 21-k$, protože všech vrcholů je dohromady 21.
Porovnáním levé a pravé strany dostaneme $14=21-k$. Snadno vyjádříme hledaný počet komponent $k=21-14$.


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!

Offline

 

#10 04. 02. 2011 10:39

Oxyd
Příspěvky: 614
Škola: MFF UK, teoretická informatika
Pozice: Student
Reputace:   31 
 

Re: acyklicky graf

↑ mysteriouss:

Ano, má tam být minus.

↑ petrkovar:

A není můj důkaz indukcí jednodušší? Počítání podobného součtu byla také první věc, co mě napadla, ale když jsem si uvědomil, oč v grafu běží, přišlo mi snažší použít indukci.

Nestuduju na VŠB a nemám ponětí, jakým stylem vedete přednášky, ale jsem zvědavý člověk a uvítám kritiku svého řešení. :)


Mýlím se častěji, než bych chtěl. Pokud vám v mém příspěvku něco nehraje, neváhejte se zeptat.
Jsem stále mlád a je mi příjemnější tykání. :)

Offline

 

#11 04. 02. 2011 13:01

mysteriouss
Příspěvky: 47
Reputace:   -1 
 

Re: acyklicky graf

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.

Offline

 

#12 04. 02. 2011 14:38

petrkovar
Veterán
Místo: Ostrava/Krmelín
Příspěvky: 1004
Pozice: VŠB - TU Ostrava
Reputace:   23 
Web
 

Re: acyklicky graf

↑ mysteriouss:Použit v písemce vztah, který nebyl na přednášce ani ve skriptech je "diskutabilní", protože ze studentova textu "Platí vzorec $|V| - c = |E|$' nepoznám, zda student cituje nějakou knížku, kterou četl, a nebo si jen myslí, že vzorec platí. Jak by se mělo lišit bodové hodnocení, když někdo napíše "Platí vzorec $|V| + |E| = c$', nebo 'Komponent je 7'? Kam se podělo zdůvodnění?

Offline

 

#13 04. 02. 2011 14:52

petrkovar
Veterán
Místo: Ostrava/Krmelín
Příspěvky: 1004
Pozice: VŠB - TU Ostrava
Reputace:   23 
Web
 

Re: acyklicky graf

↑ Oxyd:Mně se uvedený důkaz moc nelíbí. Dvě hlavní výhrady.
1) Aby platil vztah $|V| - c = |E|$, musí být graf $G=(V,E)$ acyklický. Nikde se v indukčním kroku nezdůvodňilo, že graf $G' = (V,E')$ je také acyklický.
2) Uvedený důkaz čtu spíš jako "má-li acyklický(!)graf $|V|$ vrcholů a $c$ komponent, tak má $|E|$ 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ů.

Offline

 

#14 04. 02. 2011 15:48 — Editoval mysteriouss (04. 02. 2011 15:48)

mysteriouss
Příspěvky: 47
Reputace:   -1 
 

Re: acyklicky graf

↑ petrkovar:
Neměl jsem namysli hodnocení, kde napíši výsledek bez odůvodnění jelikož v zadání je "tvrzení zdůvodněte", kdyby to tam nebylo plný počet bych očekával jelikož by po mě zdůvodnění požadováno nebylo, ale když bych např. napsal odůvodnění výše uvedenou indukcí tak očekávám, že se nebudou ubírat body jen proto, že to na přednášce nebylo.

Častokrát mi například kamarád z ČVUT vysvětloval nějaký příklad, a vysvětlil mi to postupem, se kterým jsem se na VŠB nesetkal. Stačilo by tedy jako odůvodnění napsat "Zdroj: ČVUT" nebo něco podobného aby to splňovalo kritérium, že jsem si to nevycucal z prstu?

Ohledně toho, že není nikde zdůvodněno, že $G' = (V,E')$ je taky acyklický, předpokládám, že to je vidět z $|V| - c' = |E'| \Leftrightarrow |V| - (c - 1) = |E| + 1 \Leftrightarrow |V| - c = |E|$ kde $|V| - c = |E|$ platí pro $G = (V,E)$ a $|V| - c' = |E'|$ pro $G' = (V,E')$. Jelikož jsme indukcí dokázali, že  $|V| - c = |E| \Leftrightarrow |V| - c' = |E'|$ tak předpokládám, že $G = (V,E) \Leftrightarrow G' = (V,E')$.

Offline

 

#15 04. 02. 2011 16:10

petrkovar
Veterán
Místo: Ostrava/Krmelín
Příspěvky: 1004
Pozice: VŠB - TU Ostrava
Reputace:   23 
Web
 

Re: acyklicky graf

↑ 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 $G'$ nemohl být cyklus nevidím ani slovo.

Offline

 

#16 04. 02. 2011 16:15

mysteriouss
Příspěvky: 47
Reputace:   -1 
 

Re: acyklicky graf

↑ petrkovar:
Já zase nevidím žádnou odpověď na předchozí odstavce.
Profesor má vždycky pravdu, nikdy se nemýlí a postup který nikdy neviděl je diskutabilní protože ho nezná. LOCK

Offline

 

#17 05. 02. 2011 06:53 — Editoval Dana1 (05. 02. 2011 09:44)

Dana1
Host
 

Re: acyklicky graf

↑ 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.

 

#18 05. 02. 2011 09:44

petrkovar
Veterán
Místo: Ostrava/Krmelín
Příspěvky: 1004
Pozice: VŠB - TU Ostrava
Reputace:   23 
Web
 

Re: acyklicky graf

Já odpověd na bodové hodnocení indukce vidím. ↑ Tady: u bodu 2). Proto jsem ji nepsal znovu. Celá další diskuze z mé strany byla o tom, jak řešení podat co nejpřehledněji. Student ↑ mysteriouss: (který není tak anonymní, myslím, že jeho jméno znám) pak nejspíš moji kritiku týkající se řešení bral osobně a místo aby se přiučil detail, na který v hodinách nebyl čas, tak (s krví bušící ve spáncích po posledním neúspěšném termínu) napsal co napsal. To do jisté míry vysvětluje, ale nijak neospravdelňuje neadekvátní reakci.

Zpět věci: "Zdroj: ČVUT" nestačí. Jak by případný zájemce pramen dohledall? Takovou větou bychom mohli zdůvodnit všechno.

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson