17.2.2010 Pangrác

Úvod do kombinatoriky a teorie grafů. Důraz je kladen na aktivní zvládnuti základních pojmů a metod (relace, zobrazení, graf; přesná formulace matematických tvrzení, řešení příkladů a dokazovaní jednoduchých tvrzení).
Dr.Eddy
Matfyz(ák|ačka) level I
Příspěvky: 6
Registrován: 8. 2. 2010 17:03
Typ studia: Informatika Bc.

17.2.2010 Pangrác

Příspěvek od Dr.Eddy »

1. Definujte izomorfismus mezi grafy, izomorfni zobrazeni. Ukazte priklad dvou neizomorfnich stromu na 4 vrcholech, pokud takove existuji.
2. Jaky je maximalni pocet hran v grafu o n vrcholech bez trojuhelniku? Vysledek dokazte. (Ne rovinny, ale kterykoli i bez rovinneho nakresleni)
3. Mejme osm karet ozacenych 1,2,...8 a ctyri obalky oznacene A,B,C,D. Kolik je celkem moznosti pro pripad:
---a) vybereme 4 karty a ty dame do obalek, 4 karty nam zbydou.
---b) v kazde obalce muze byt libovolny pocet karet ale tak, aby nam zadna nezbyla.
---c) v kazde obalce jsou prave dve karty.

Nevzpomnel jsem si na tu vetu a jeji dukaz (2.), tak jsem ho pozadal, jestli by mi nedal nahradni, tak mi dal vypsat 3 nebo 4 ekvivalentni tvrzeni o stromech a dokazat je. I tak jsem dostal 2 :)

Jinak spravna reseni pro 3. jsou:
a) 8 nad 4
b) 4^8
c) (8 nad 2) * (6 nad 2) * (4 nad 2)
Odpovědět

Zpět na „DMI002 Diskrétní matematika“