Matfyz Wiki

Zk. 1.6.2009 - Kratochvil

Marex at 2009-06-01 22:00:39

Bylo 6 prikladu:

  1. Urcete pocet koster tohoto grafu:
    http://artax.karlin.mff.cuni.cz/~vasum7am/graf1.png

  2. Urcete vytvorujici funkci pro posloupnost (2, 1, 3, 2, 4, 3, 5, 4, ...)

  3. Rozhodnete, pro ktera prirozena cisla m, n obsahuje uplny bipartitni graf K<sub>m,n</sub> Hamiltonovskou kruznici

  4. Najdete nejvetsi parovani v nasledujicim grafu a zduvodnete, proc je nalezene parovani nejvetsi:
    http://artax.karlin.mff.cuni.cz/~vasum7am/graf2.png

  5. Dokazte, ze kazdy vrcholove 2-souvisly graf o n vrcholech ma alespon n koster. Popiste vsechny vrcholove 2-souvisle grafy o n vrcholech, ktere maji prave n koster.

  6. Necht n >= 3 je prirozene cislo. Necht A<sub>1</sub>, A<sub>2</sub>, ..., A<sub>n</sub> je system n ruznych mnozin velikosti n-2. Dokazte, ze tento system ma system ruznych reprezentantu.

Bodovani:
Priklady 1-4 za 6 bodu.
Priklady 5-6 za 8 bodu.
Celkovy mozny zisk je 40 bodu.

Hodnoceni:
40-34: 1
31-28: 2
26-19: 3
15-14: ustni
(mezery v bodovani znamenaji, ze takovy pocet bodu nikdo nemel)

(Je to prepis z fotky, kreslit neumim, melo by to byt spravne, patches are welcome)

Sranda at 2009-06-12 00:02:56

Nekdo ma reseni 6. prikladu.

Hallova podminka rika, ze
pro kazde L z {1...n}, |L| <= |U Ai|

ale

  • |U Ai| = n-2

  • kdyz bereme L = {1,2,3,..n} => |L| = n => n>n-2 => A1,A2,...,An nema SRR.

Je to spravne nebo jsem mimo.

Anonymous at 2009-06-12 00:59:25

Myslim si ze |Ai|=n-2 a sjednoceni Ai muze byt vice nez n.
indukci podle L plati az do n-1

pro |L|=n
SPOREM: |U Ai|<=n-1 , z toho plyne, ze system ma maximalne n-1 ruznych prvku. Kazdy mnozina obsahuje n-2 prvku.
odtud vime ze (n-2) z (n-1) = n-1. (pocet ruzne mnoziny) SPOR. Ale system ma n ruzne mnoziny.