od lukax » 22. 1. 2009 21:57
K4 píše:Nevíte prosím někdo, jak se počítá počet koster nějakého grafu, který je tvořen dvěma "podgrafy" spojenými nejen jedním vrcholem ale třeba i několika hranami..? Počet koster grafů spojených jedním bodem se spočítá jako součin počtu koster obou grafů... Např. čtverec spojený jedním vrcholem s trojúhelníkem se spočítá jako 4*3 = 12 koster...
Jak je to ale například právě s grafem, vzniklým z K4 dělením hran..?
Obecně se asi nic moc vymyslet nedá.
U té K
4 si šlo všimnout toho, že jde spočítat pošet koster K
4 bez dělení (n
n-2=4
2=16) a pak pro každou z nich domyslet, jak kostru „dokreslit“, aby fungovala i na děleném grafu. Víme, že každá kostra grafu nad čtyřmi vrcholy má tři hrany, takže každá z 16 nalezených koster tři hrany má a tři ne. Tam, kde jsou, musíme vést obě hrany dělení, tam, kde nejsou, máme vždy dvě možnosti, jestli vést hranu k vydělenému vrcholu — to je při třech nejsoucích hranách 2
3=8 možností.
Správný výsledek tedy byl 16×8=128. :-)
[quote="K4"]Nevíte prosím někdo, jak se počítá počet koster nějakého grafu, který je tvořen dvěma "podgrafy" spojenými nejen jedním vrcholem ale třeba i několika hranami..? Počet koster grafů spojených jedním bodem se spočítá jako součin počtu koster obou grafů... Např. čtverec spojený jedním vrcholem s trojúhelníkem se spočítá jako 4*3 = 12 koster...
Jak je to ale například právě s grafem, vzniklým z K4 dělením hran..?[/quote]
Obecně se asi nic moc vymyslet nedá.
U té K[sub]4[/sub] si šlo všimnout toho, že jde spočítat pošet koster K[sub]4[/sub] bez dělení (n[sup]n-2[/sup]=4[sup]2[/sup]=16) a pak pro každou z nich domyslet, jak kostru „dokreslit“, aby fungovala i na děleném grafu. Víme, že každá kostra grafu nad čtyřmi vrcholy má tři hrany, takže každá z 16 nalezených koster tři hrany má a tři ne. Tam, kde jsou, musíme vést obě hrany dělení, tam, kde nejsou, máme vždy dvě možnosti, jestli vést hranu k vydělenému vrcholu — to je při třech nejsoucích hranách 2[sup]3[/sup]=8 možností.
Správný výsledek tedy byl 16×8=128. :-)