Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
Stránky: 1
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?
Offline
↑ Květina:
Uloha 3.
Nevim jestli to bude presne dukaz, ale snad z toho budes mit alespon motivaci :)
Jestli to chapu dobre tak mas vzdycky 3 formule o 3 promennych a chces dokazat, ze jsou vzdycky splnitelny.
Budu to zapisovat takhle:
Tam kde bude promenna ve formuli NEznegovany tak bude 1, tam kde bude znegovana bude 0. Takze treba formule a nebo b nebo (negace)c bude zapsana jako 110. Ten zapis jsme si definovali pro jazyk L(SAT) trochu jinak, ale na tom zas tak nezalezi...
Takze mas tri formule o trech promennych, formule to muzou byt tyto:
000
001
010
011
100
101
110
111
Teda celkem 8 formuli. Ted vyberem 3 nahodny formule, takze treba:
011
100
101
A ptam se jakoby naopak. Pro jaky ohodnoceni nebudou tyto formule splneny???
Budou to takovy ohodnoceni, kde se nachazi alespon jedna z nich v negaci. Takze tyhle tri formule nebudou splneny pro tyto ohodnoceni:
100
011
010
Pro vsechny ostatni ohodnoceni budou splneny.
Jelikoz mas 8 moznych formuli a 8 moznych ohodnoceni, z tech 8mi ohodnoceni tri nevyhovuji, tak ti zbyva 5 vyhovujicich ohodnoceni... -> je to splnitelny.
Offline
Stránky: 1