Matematické Fórum

Ahojky,
dostali-li jsme za ukol vyresit tyto ulohy, ale nevim si vubec rady.
Urcite tomu nekdo rozumi vic nez ja. Ja ani nevim, co mam poradne delat.
Diky Květinka

Úloha 1. Mejme bipartitní graf na 2n vrcholech takový, že každá partita má velikost n.
a) Dokažte, že pokud minimální stupen G je alespon n/2, pak G obsahuje perfektní párování.
b) Stacilo by, kdyby min. stupen G byl alespon n/2 − 1?

Úloha 2. Dokažte, že pro m mocninu dvou lze Km rozložit na m−1 hranove disjunktních perfektních párování.

Úloha 3. Dokažte, že 3, 3−SAT formule je vždy splnitelná.

Úloha 4. Dokažte, že prímky libovolné konecné projektivní roviny (KPR) mají systém ruzných reprezentantu (SRR).

Úloha 5. Popište všechny systémy, které splnují axiomy (A1) a (A2) konecných projektivních rovin, ale nesplnují (A0).

Úloha 6. Naleznete maximální množinu navzájem ortogonálních latinských ctvercu rádu 4 a dokažte, že je maximální.

Úloha 7.
Pro m <= n definujeme latinský obdélník velikosti m × n jako obdélníkovou tabulku m × n
vyplnena císly [n] = {1, 2, . . . , n}, v jejímž každém rádku a každém sloupci se žádné dve císla neopakují.
Kolik existuje latinských obdélníku rádu 2 × n?