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.

  1. Dokažte, že pro každý graf G jsou následující tvrzení ekvivalentní: [4b.]
    1. G obsahuje uzavřený sled liché délky
    2. G obsahuje uzavřený tah liché délky
    3. G obsahuje kružnici liché délky
    4. G obsahuje indukovanou kružnici liché délky

Na úterý 8.12 a pátek 11.12.

  1. 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
    1. na (surjektivní).
      Musí být f také na? A g? [1b.]
    2. bijekce.
      Musí být f také bijekce? A g? [1b.]

Na úterý 20.10.

  1. Najděte všechny relace, které jsou zároveň symetrické a slabě antisymetrické. [2b.]
  2. 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á.
    1. X_1 = N, R_1 = {(x,y): x|y} x|y znamena, že x dělí y, tj. y/x je celé číslo [1b]
    2. 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]
    3. X_3 = N x N, R_3 = {((a,b),(c,d)): a=b=c} [2b]
Na pátek 23.10.
  1. Najděte všechny relace, které jsou zároveň symetrické a slabě antisymetrické. [2b.]
  2. Vymyslete relaci, která je tranzitivní a symetrická, ale není reflexní [2b]
  3. Pro následující relaci určete a zdůvodněte, které z vlastností reflexivita, symetrie, slabá antisymetrie a tranzitivita má a které nemá:
    1. X_1 = N x N, R_1 = {((a,b),(c,d)): a+b<=c} [1b]
Na 13.10. a 16.10.:
  1. 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.
  2. 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čí.