Fórum studentů MFF UK

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.

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.

Bylo 6 prikladu:

1) Urcete pocet koster tohoto grafu:
[img]http://artax.karlin.mff.cuni.cz/~vasum7am/graf1.png[/img]
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:
[img]http://artax.karlin.mff.cuni.cz/~vasum7am/graf2.png[/img]
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)