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