DS Teorija

• 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

• Različni točki u in v sosedi v grafu G(črtica) natnko tedaj, ko nista sosedi v G.
• 

Najmanjše število barv s katerimi se da graf pobarvati.

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

• 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.

Če za poljubni dve točki u v, obstaja u-v sprehod.

Je dolžina najkrajšega u-v sprehoda v grafu.

• Enostaven obhod, ki vsebuje vse povezave največ enkrat ter se zaključi na začetku.
• 
• Graf G je eulerjev, če ima kak eulerjev obhod.

• Je  cikel, ki vsebuje vse točke grafa.
• 
• Hamiltonov pot: Vsebuje vse točke
• Hamilnotnov cikel: vsebuje vse točke in se vrne v začetno

Kadar ohranja število vozlišč, število povezav, stopnje vozlišč, število trikotnikov.

• Graf je poln če sta vsaki njegovi točki sosedi
• 

Kadar nobeni točki nista sosedi.

Kadar ga lahko pobarvam z dvema barvama.

Negiram sklep, ter poskušam najti protiprimer

• Dela samo za implikacijo
• Vzamem prvi del ter poskušam najti drugega.

Logični izraz ki ima v vseh naborih logično vrednost 1

Je izraz, ki ima v vseh naborih logično vrednost 0

Je najkrajša izjavna formula ki jo preberemo neposredno za lastno spremenljivko posameznega kvantifikatorja.

• Drevo je povezan graf brez ciklov.
• 

• Gozd je graf brez ciklov
• 

• 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)

Kadar je refleksivna, simetrična, tranzitivna.

R[a] ={x|xRa}

Ekvivalencni razred elementa a∈A je mnozica vseh tistih elementov mnoziceA, ki so v relaciji z a.

Kvantifikatorji se nahajajo na začektu