Zadania z egzaminu, 3 termin 2010/2011

Treść:



Zadania
  1. Niech będzie relacją pomiędzy punktami prostej określoną następująco:
    wtedy i tylko wtedy, gdy
    Sprawdzić czy relacja jest relacją: a) zwrotną b) symetryczną c) przechodnią d) słabo antysymetryczną e) silnie antysymetryczną f) słabo spójną g) silnie spójną. (Podać interpretację geometryczną tej relacji.)
  2. Narysować diagram Hassego relacji porządku o macierzy .
    Czy ta relacja ma (wskazać je) elementy: najmniejsze, największe, minimalne, maksymalne? Czy jest relacją równoważności? Czy diagram Hassego relacji traktowany jako graf jest: a) drzewem, b) eulerowski, c) spójny?
  3. Znaleźć rozwiązanie ogólne i rozwiązanie spełniające warunki początkowe równania rekurencyjnego .
  4. Znaleźć oraz takie liczby , że
  5. Znaleźć maksymalny przepływ i minimalny prrzekrój w sieci (rysunek na tablicy):
    a) bez łuku zaznaczonego przerywaną linią, b) z łukiem zaznaczonum przerywaną linią.
  6. Wykazać indykcyjnie, że .

Pytania teoretyczne

  1. Zdefiniować kratę.
  2. Sformułować uogólnioną zasadę szufladkową Dirchleta.
  3. Sformułować twierdzenie Czebyszewa.

Rozwiązania: