Matematické Fórum

1) permutace s opakováním -- pokud nebudeme brát v potaz omezení na O, tak je 11!/(2!*2!). Pokud jsou obě O vedle sebe, představíme si místo nich symbol třeba W. Anagramů slova  STAVRWPLUS je 10!/2!, výsledek je 11!/(2!*2!)-10!/2!.

2) "MARFOS A PETR házení 4 šesti-stěnou kostkou" -- každý z nich hází čtyřikrát nebo dohromady čtyřikrát? A jak se počítají dvojice?

3) Tipl bych si že to jde, ale na hledání konkrétního grafu jsem teď moc líný.

4) kostra bude obsahovat hranu délky 1 a všechny hrany délky 2 krom jedné (např. bez té svislé vlevo nahoře), váha je 13. Použít jde Kruskalův algoritmus
http://cs.wikipedia.org/wiki/Kruskal%C5%AFv_algoritmus

5) Neobsahuje podgraf izomorfní s K_5 ani s K_3,3, proto je rovinný.  Vrcholy očíslujme: na horní hraně vrchol vlevo označme 1, pak ve smyslu chodu hodinových ručiček. Rovinné nakreslení získáme tak, že hrany (1,4) a (8,5) překreslíme jako oblouky ve vnější oblasti osmiúhelníka. To samé pak provedeme s hranami (1,5) a (4,8).

6) Indukovaná cesta délky 5 je např. 6,7,1,2,3,4 (značení viz př. 5)

7) Izomorfní nejsou -- oba obsahují 4 vrcholy stupně 4, ale ve druhém jsou dva z nich spojené, v prvním ne.

↑ Kondr:
Mel bych jenom malou poznamecku, ktera v tomto pripade nehraje roli, nebot graf je rovinny, coz se snadno dokaze nalezenim jeho nakresleni, ale v jinych prikladech roli hrat muze. Pokud graf neni rovinny, nemusi obsahovat K_5 ani K_3,3 jako podgraf. Staci kdyz obsahuje nejake deleni nekterho z techto dvou grafu (takzvana Kuratowskeho veta, kterou Kondr samozrejme urcite zna).

↑ Kondr:
Ok.Dik moc za vysvetleni.Jeste bych se chtel zeptat nejake chytre hlavy, jak se resi 3 nebo spis, jak se pak z te posloupnosti maluje vysledny graf. Vim, ze se tam nejak postupne pridavaji vrcholy, ale nikdy nevim s jakymi vrcholy mam pridavany vrchol pospojovat,abych zachoval spravne stupne vrcholu.Dikec.

↑ Kondr:
Zkousel jsi to nekdo nakreslit? Po prekresleni na papir mi nejde spojit hranz (4,8) dojde vzdy ke krizeni pres vrchol 1 respektive 5 kdyz tahnu spodem. Muzete mi napovedet kde delam chybu?

↑ marros11:Ano, do vrcholu 8 nemůžeme. Možná jsem to popsal moc složitě -- zkrátka procházíme graf do hloubky a kontrolujeme, že je cesta stále indukovaná, tj. že na ní nejsou dva vrcholy v původním grafu spojené hranou, která na  cestě není.

↑ andrééé:Předek je vrchol, kterým jsme na dané cestě už prošli (v orientovaném stromu je a předkem b, pokud z a vede orientovaná cesta do b. Naše prohledávání do hloubky vytváří orientovaný strom. Orientované cesty v něm odpovídají indukovaným cestám.

↑ marros11:Taky jsem zjistil, že to přetočení dvou hran nestačí. On možná vážě není rovinný :o) Zkusím v něm najít to dělení K_3,3 (Dělení K_5 v něm být nemůže, protože jen 4 jeho vrcholy mají stupeň 4.)