Archiv příkladů z Diskrétní matematiky
Na této stránce jsou příklady, které jsem nechával na rozmyšlení nadoma. Jejich řešení jsme
si už na cvičení řekli, a tedy za tyto úlohy nelze získat žádné body.
Na úterý 15.12 a pátek 18.12.
-
Dokažte, že pro každý graf G jsou následující tvrzení ekvivalentní: [4b.]
-
G obsahuje uzavřený sled liché délky
-
G obsahuje uzavřený tah liché délky
-
G obsahuje kružnici liché délky
-
G obsahuje indukovanou kružnici liché délky
Na úterý 8.12 a pátek 11.12.
-
Pro které dvojice (a,b) je H_a podgrafem H_b? A kdy je i indukovaným podgrafem? Graf H_d je hypekrychle, tj. vrcholy jsou (0,1)-vektory délky d a hrany vedou mezi dvojicemi vektorů lišícími se v právě jedné souřadnici. [3b.]
Na úterý 3.11. a pátek 6.11.
Na úterý 27.10.
Funkce f složeno g je
- na (surjektivní).
Musí být f také na? A g? [1b.]
- bijekce.
Musí být f také bijekce? A g? [1b.]
Na úterý 20.10.
-
Najděte všechny relace, které jsou zároveň symetrické a slabě antisymetrické. [2b.]
-
Pro každou z následujících relací určete a zdůvodněte, které z vlastností reflexivita,
symetrie, slabá antisymetrie a tranzitivita má a které nemá.
-
X_1 = N, R_1 = {(x,y): x|y} x|y znamena, že x dělí y, tj. y/x je celé číslo [1b]
-
X_2 = {2,3,4 ...}, R_2 = {(x,y): gcd(x,y)>1} gcd(x,y) značí největšího společného dělitele čísel x a y (z anglického greatest common divisor) [1b]
-
X_3 = N x N, R_3 = {((a,b),(c,d)): a=b=c} [2b]
Na pátek 23.10.
-
Najděte všechny relace, které jsou zároveň symetrické a slabě antisymetrické. [2b.]
-
Vymyslete relaci, která je tranzitivní a symetrická, ale není reflexní [2b]
-
Pro následující relaci určete a zdůvodněte, které z vlastností reflexivita,
symetrie, slabá antisymetrie a tranzitivita má a které nemá:
-
X_1 = N x N, R_1 = {((a,b),(c,d)): a+b<=c} [1b]
Na 13.10. a 16.10.:
-
Najděte a dokažte, že existuje 5 závaží, pomocí kterých umíme odvážit všechny hmotnosti 0g, 1g, 2g, .., 70g na rovnoramenných vahách,
přičemž závaží můžeme ukládat na obě misky.
- Mějme 11 pravých a 1 falešnou kouli, která se od pravých liší hmotností (všechny pravé mají stejnou hmotnost) a rovnoramenné váhy.
Zjistěte, kolik minimálně vážení potřebujeme na nalezení falešné koule a zjištění, zda je těžší nebo lehčí.