KMA/DMA   Diskrétní matematika

Otázky ke zkoušce

FAV-1, 1999/2000

  • Binární relace - základní pojmy
  • Ekvivalence, zbytkové třídy modulo p
  • Grupa, těleso, těleso zbytkových tříd
  • Částečně uspořádané množiny
  • Supremum, infimum, svaz
  • Boleova algebra
  • Atomy Booleovy algebry, reprezentace Booleových algeber
  • Direktní součin Booleových algeber
  • Booleovské funkce, Booleovské polynomy, úplná konj. a disj. normální forma
  • Grafy: definice, homomorfismus a izomorfismus grafů
  • Neorientované grafy: stupeň uzlu, cesty, souvislost grafu
  • Neorientované grafy: kružnice, stromy
  • Kostra neorientovaného grafu, hodnost a cyklomatické číslo
  • Orientované grafy: slabé a silné vlastnosti, silná souvislost, kvazikomponenty, kondenzace
  • Acyklické grafy
  • Uzlo-hranová incidenční matice orientovaného grafu a její vlastnosti
  • Algebraický výpočet koster grafu, počet koster úplného grafu
  • Uzlo-hranová incidenční matice neorientovaného grafu a její vlastnosti
  • Matice kružnic neorientovaného grafu, lin. prostor kružnic grafu
  • Matice hranových řezů, lineární prostor hranových řezů grafu
  • Lineární vektorové prostory neorientovaného grafu a jejich vzájemný vztah
  • Matice sousednosti grafu a její mocniny
  • Ohodnocené grafy, w-metrika grafu, distanční matice
  • Minimální cesta, Dijkstrův algoritmus
  • Síť, tok v síti, existence toku v síti
  • Věta o maximálním toku a minimálním řezu
  • Metody nalezení maximálního toku
    • Zkouška: Písemná část - 2 vyučovací hodiny, 20 bodů

    bodový zisk známka
    0 - 9 4
    10 - 12 3
    13 - 16 2
    17 - 20 1

    Ústní část - 2 otázky
    Přihlášky ke zkoušce: elektronicky

    Plzeň, 14. 5. 1999
    Prof. RNDr. Zdeněk Ryjáček, CSc.