Fórum studentů MFF UK

1) Pocitani dvojic (R,M) dvema zpusoby, v Kapitolach z DM od Matouska a Nesetrila

2) tohle by bylo nadlouho, muj vysledek (????):
zvolim nejvetsi m takove, ze m<=(n nad 2)
V pripade rovnosti je vysledek n-m+1, jinak n-m

3) Delal jsem to Jarnikovym algoritmem (ale jde to i primo), vyslo mne (n-1)(n+4)/2.

4) Ja jsem to pochopil tak, ze staci dva konkretni stromy s ruznym skore.
Ja jsem zkusil neco, co vypada jako H (prvni graf pred |, druhy za, nekreslim svisle hrany, tecky jsou vypln)
O....O |O O-O
O-O-O,|O-O
O....O,|O O
Oba grafy maji skore (1,1,1,1,2,3,3), ale nejsou isomorfni, protoze
vzdalenost dvou vrcholu s degree=3 je v prvnim grafu 2 a v druhem 1.

A můžeš připsat zhruba řešení? Zajímala by mě hlavně ta 4. Stačí tam jenom uvést příklad, nebo tam chce ještě ěnco připsat. Díky.

Zadani pisemne prace z DMA005, Martin Loebl:

Na pisemnou praci byly 2 hodiny, vyskytovaly se tri typy zadani - A,B,C.

Toto je B tak, jak si ho pamatuju:

1) Dokazte Spernerovu vetu o nezavislem systemu podmnozin usporadanych inkluzi.
2) Graf ma n vrcholu, n-k hran, jaky je max. mozny pocet komponent
3) Mame uplny graf na n vrcholech V = {1,2,...,n}, w({i,j})=i+j, najdete vahu minimalni kostry.
4) Najdete dva neisomorfni stromy se stejnym skore.