DS Teorija

  1. Dokaz pravilnosti sklepa
    • 1. Dam predpostavke
    • poskušam izpeljati zaključek s pravili sklepanja
    • S pogojnim sklepom, tam kjer imam implikacijo, vzamem prvi člen, ter poskušam najti drugega
    • Protislovje: Tam kjer imam implikacijo, negiram implikacijo ter to dam kot predpostavko, ter poskušam najti en protiprimer
  2. Kaj je komplement grafa
    • Različni točki u in v sosedi v grafu G(črtica) natnko tedaj, ko nista sosedi v G.
    • Image Upload 1
  3. Kromatično število grafa
    Najmanjše število barv s katerimi se da graf pobarvati.
  4. Kdaj je graf regularen
    Takrat ko imajo vse njegove točke isto stopnjo.

    • Točka stopnje 0: Izolirana točka
    • Točka stopnje 1: List grafa
    • Točka stopnje 3: Kubični graf

    Točka poljubne stopnje: d-regularen
  5. Kaj je sprehod v grafu, pravila, dolžina sprehoda.
    • Je zaporedje, pri čemer sta vsaki zaporedni točki sosedi.
    • Sprehod ima začetek in konec, to sta krajišči sprehoda.

    • Sprehod v začetku u in koncu v pravimo tudi u-v sprehod.
    • Sprehod sme isto povezavo uporabiti večkrat, prav tako, ravno tako lahko posamezno povezavo uporabi v različnih smereh.

    Dolžino sprehoda S označimo z |S|, ter je enaka številu uporabljenih povezav, upoštevamo tudi število ponovitev.
  6. Kdaj je graf povezan?
    Če za poljubni dve točki u v, obstaja u-v sprehod.
  7. Razdalja med točkama u-v v grafu
    Je dolžina najkrajšega u-v sprehoda v grafu.
  8. Eulerjev obhod
    • Enostaven obhod, ki vsebuje vse povezave največ enkrat ter se zaključi na začetku.
    • Image Upload 2
    • Graf G je eulerjev, če ima kak eulerjev obhod.
  9. Hamiltonov cikel
    • Je  cikel, ki vsebuje vse točke grafa.
    • Image Upload 3
    • Hamiltonov pot: Vsebuje vse točke
    • Hamilnotnov cikel: vsebuje vse točke in se vrne v začetno
  10. Kdaj sta grafa izomorfna
    Kadar ohranja število vozlišč, število povezav, stopnje vozlišč, število trikotnikov.
  11. Kdaj je graf poln
    • Graf je poln če sta vsaki njegovi točki sosedi
    • Image Upload 4
  12. Kdaj je graf prazen
    Kadar nobeni točki nista sosedi.
  13. Kdaj je graf dvodelen?
    Kadar ga lahko pobarvam z dvema barvama.
  14. Sklep s protislovjem
    Negiram sklep, ter poskušam najti protiprimer
  15. Pogojni sklep
    • Dela samo za implikacijo
    • Vzamem prvi del ter poskušam najti drugega.
  16. Tavtologija
    Logični izraz ki ima v vseh naborih logično vrednost 1
  17. Protislovje
    Je izraz, ki ima v vseh naborih logično vrednost 0
  18. Kaj je doseg kvantifikatorja?
    Je najkrajša izjavna formula ki jo preberemo neposredno za lastno spremenljivko posameznega kvantifikatorja.
  19. Drevo
    • Drevo je povezan graf brez ciklov.
    • Image Upload 5
  20. Gozd
    • Gozd je graf brez ciklov
    • Image Upload 6
  21. Prerezna točka
    Image Upload 7
  22. Izračun GCD nalog
    • Izračunam največji skupni deljitelj
    • (predzadna vrstica)+ t*(zadna)

    • Primer
    • -34*828 + 14*2016 + t*(56*828-23*2016)
    • 828*(-34+56t) + 2016*(14 - 23t)
  23. Kdaj je relacija R ekvivalenčna
    Kadar je refleksivna, simetrična, tranzitivna.
  24. Kaj je ekvivalenčni razred relacije
    R[a] ={x|xRa}

    Ekvivalencni razred elementa a∈A je mnozica vseh tistih elementov mnoziceA, ki so v relaciji z a.
  25. Grafično zaporedje
  26. Prenesena normalna oblika
    Kvantifikatorji se nahajajo na začektu
Author
wolf
ID
328507
Card Set
DS Teorija
Description
dsa
Updated