Matematické Fórum

Hees · 25. 06. 2009 17:55

Chcem sa spytat ako vypocitam faktor tohoto grafu.Priklad som si vymyslel sam len pre to aby som to pochopil.Lebo su ovela zlozitejsie.

Malo by sa to robit pomocou kombinatoriky.Prvy obrazok je graf dalsie su jeho faktory ako priklad.Moze ich byt velmi vela.

Hees · 25. 06. 2009 23:13

nikto nevie :(

Kondr · 26. 06. 2009 01:11

Jen se nebojte, loupežníkové, počkejte do zimy - potom spadnou!

Jak má ve faktoru vypadat množina vrcholů víme. Množina hran je podmnožinou původní množiny hran. Pokud měl původní graf E hran, je takových podmnožin $2^E$ . Snadno rozmyslíme, že každá z nich opravdu určuje faktor grafu.

Hees · 26. 06. 2009 03:00

No toto vysvetlenie vobec nechapem.

Kondr · 26. 06. 2009 08:16

↑ Hees:Tak to zkusím popsat na tvém příkladě. Máme graf o 5 vrcholech a 8 hranách. Ptáme se, kolika způsoby z něj lze vyrobit faktor. Vrcholy zachováme všechny. Hrany zachováme jen některé. U každé z 8 hran se můžeme nezávisle rozhodnout, jestli ji do grafu dáme nebo ne. Podle pravidla součinu tak máme $2^8=256$ možností.

Matematické Fórum

#1 25. 06. 2009 17:55

Faktorizacia grafu

#2 25. 06. 2009 23:13

Re: Faktorizacia grafu

#3 26. 06. 2009 01:11

Re: Faktorizacia grafu

#4 26. 06. 2009 03:00

Re: Faktorizacia grafu

#5 26. 06. 2009 08:16

Re: Faktorizacia grafu

Zápatí