LGR Flashcards
Atomicka formule
Zakladni prvek vyrokove logiky
Mnozina At
Je mnozina atomickych formuli
Jazyk vyrokove logiky
Je mnozina vsech formuli nad mnozinou At a je definovana jako
F(at) ::= a | T | F | (~F) | (F1 ^ F2)
kde:
a - atomicke formule
T, F - logicke konstanty
~ - negace, unarni log. spojky
^, U, =>, <=>… - binarni log. spojky
Syntakticky strom formule
Rozbijim formuli podle operatoru a skladam strom na rekurzivni mensi podstromy
Hloubka syntaktickeho stromu
Jestli narazil na at. promennou, T,F => vrat 0
Jestli narazil na negaci podformule => vrat 1+hl(podformule)
Jestli narazil na podformuli => vrat 1+max(hl(leva), hl(prava))
Mnozina podformuli formule F
Mejme formuli Fle(At). Mnozina vsech podmnozin (vzpomen si na Cantorovu vetu) je dana jako P(Fle(At)) a je to mnozina vsech moznych podformuli, ktere jsem schopen sestavit z puvodni formule.
Patri tam i ona sama, pak vsechny atomicke promenne a vsechny jejich podkombinace ktere vidim ve stromu
Definice prirozene dedukce ve vyrokove logice VL
Je to dukazovy system
Semantika vyrokove logiky
Prirazuje vyznam syntaktckym objektum,
napr Booleonovka logika prirazuje {0,1} jako pravda/nepravda
Pravdivostni ohodnoceni formule Fle(At)
Je zobrazeni z Fle(At) do Bool, splnujici podminky
1. T = 1, F = 0
2. a^b = 1 <=> a=1 ^ b=1
3. a U b = 0 <=> a=0 ^ b=0
3. a=>b = 0 <=> a=1 ^ b=0 (z pravdy plyne lez)
4. a<=>b = 1 <=> a=b (ekvivalence jsou stejne)
5. ~a = 1 <=> a=0
Ja toto zobrazeni je jednoznacny - jakmile ohodnotim vstupni atomicke promenne -> pa ihned se cela formule ohodnoti sama jednoznacne
Jak zjistit pravdivostni ohodnoceni zadane formule s ohodoncenymi at. prvky?
Sestavim strom a jdu nahoru od at. prvku a ohodnocuju kazdou operaci zvlast az dojdu k vyslednemu ohodnoceni nahore
Pravidlo vylouceneho tretiho
Bez zadnych predpokladu mohu prohlasit, ze plati A nebo negace A
neco bude plati nebo neplati, nic jinyho nejde, nepotrebuje to zadny predpokald
Logicky ekvivalentni formule f1 -||- f2
Jsou takove f1 a f2 pro ktere plati
f1 |- f2
f2 |- f2 // tedy z jedne plyne druha a naopak
„Je pátek nebo sobota.“
„Není pravda, že není pátek a zároveň není sobota.“
existuje obostranny dukaz
Semanticka ekvivalence dvou formuli
Je to relace ekvivalence
Pro vsechny formule A,B,C plati:
1. a |=| a //reflexivita
2. (a|=|b) => (b|=|a) //symetrie
3. tranzitivita… podobne
Kdyz a|=|b pak a -||- b
Rika mi to neco jako ze tyto formule rikaji v podstate totez - tj pokud plati jedna, tak plati i druha, a pokud neplati jedna, tak enplati ani druha. Jsou pravdivostne ohodnoceny stejne za vsech okolnosti.
Priklad: kazdy clovek ma matku
neexistuje clovek, co nema matku
Formule f je Semanticky dusledek mnoziny formuli S…
Pokud pro kazde ohodnoceni U, v nemz jsou pravdive vsechny formule z S, je pravdiva i f ve stejnem ohodnoceni U.
Znacime S|= f //f je semantickym dusledkem S
Postup dukazu/vyvraceni, ze formule f je semanticky dusledek mnoziny formuli S
Mam mnozinu S{nejake formule… s at. prvky}
Sestavim tabulku vsech at. prvku a vsech formuli z S do sloupcu.
Pak ohodnotim vsechny mozne kombinace at. prvku jako 00,01,10,11 atd do radku
Pro kazdy radek ohodnotim i formule z S.
Najdu takove radky, kde jsou formule z S pravdive VSECHNY. Pokud ve stejnych radcich je pravdiva i moje zadana formule, pak je semantickym dusledkem S. Pokud radek S=1, ale f ve stejnem radku=0, pak neni sem. dusledkem.
Pro formuli s n atomickymi promennymi kolik existuje pravdivostnich ohodnoceni (variant, jak ji ohodnotit)
Pro kazdou z n promennych muzeme pridelit 2 moynosti - 0,1.
Tedy je to 2 ohodnoceni pro 1. prvek * 2 ohodnoceni pro 2. prvek * 2 ohodnoceni pro 3. prvek * … n-krat
tedy je to 2^n ohodnoceni celkem
Tedy je to 2^n radku v tabulce pravdivostniho ohodnoceni
Definice splnitelne formule
Formule je splnitelna, pokud existuje alespon jedno pravdivostni ohodnoceni atomickych prvku tak, ze je formule v tomto ohodnoceni pravdia, tedy staci najit pouze jeden radek abych prohlasil ze je splnitelna.
Definice tautologie
Formule je tautologie p.t.k je splnitelna pro vsechna pravdivostni ohodnoceni jeji atomickych prvku
Definice kontradikce
Formule je kontradikce p.t.k neni splnena v zadnem pr. ohodnoceni jeji atomickych prvku
Definice splnitelna mnoziny formuli S
Mnozina formuli S je splnitelna, pokud existuje alespon jedno takove pravdivostni ohodnoceni, ve kterem jsou splneny vsechny formule z S
Vztah mezi semantickou ekvivalenci a pravdivostnim ohodnocenim dvou formuli
Dve formule jsou semanticky ekvivalentni pokud rikaji totez, tedy pro jakekoliv pr. ohodnoceni maji stejnou pravdivostni hodnu obe.
Takze udelam tabulku kam do sloupcu dam obe formule a pak jejich aatomicke prvky. Pro vsechny kombinace pr. hodnoceni at. prvku spocitam pr. ohodnoceni formuli a ve vsech radcich musi vyjit stejne
Nebo jiny pohled:
Dve formule jsou sem. ekv. p.t.k. implikace mezi nimi je tautologie
Jeste jiny pohled
Dve formule jsou sem. ekv. p.t.k. druha je sem. dusledkem prvni a naopak
Pokud mnozina formuli S je prazdna mnozina, pak formule f je jejim semantickym dusledkem p.t.k.
f je tautologie
Tedy f je pravdiva vdzy, takze i ve vsech pripadech, kdy prazdna mnozina je pravdiva (coz ale je splneno vzdy, protoze predpoklad z prazdne mnoziny je vzdy pravda…, protoze nenajdu protipriklad)
Takze S vdzdy/nikdy je pravdiva a f je vzdy pravdiva => f je dusledkem S.
Semanticky dusledek nesplnitelne mnoziny je…
Jakakoliv formule,
protoze nesplnitelna mnozina NIKDY NEMA PRAVDIVY RADEK, tedy nemam co overovat, takze jakakoliv formule je dusledkem nesplnitelne
Pokud formule je semantickym dusledkem pravdy True, pak je tato formule…
tautologie
Veta o dedukci (asi ne moc podstatna)
Psi je sem. dusledkem mnoziny formuli sjednoceno s formuli fi p.t.k. implikace q->psi je sem. dusledkem mnoziny formuli
S U f |= psi p.t.l S |= (fi =>psi)
Mnozina vsech sem. dusledku mnoziny formuli S
Je mnozina Cos(S) // consequences
Je to mnozina vsech formuli, ktere jsou sem. dusledkem S
Plati:
1. S je podmnozina Con(s)
2. S je podmnozina T, pak Con(s) je podmnozina Con(t)
3. Con(Con(S)) = Con(S)
Vztah semantickeho a logickeho dusledku
S |- fi p.t.l S |= fi
Tedy fi mohu odvodit z S p.t.k. fi je sem. dusledkem mnoziny formuli S
Pokud je otazka polozena jako “dokazte, ze fi plyne z S” => pouziju S|-fi.
Pokud je otazka “ rozhodnete, za fi je dusledkem S…” => Pouziju S|=fi
Uplny/Adekvatni system spojek v logice
Je takova mnozina symbolu/spojek, ze s jejcih pomoci muzeme poskladat jakoukoliv formuli a mohou nahradit jina vyjadreni, treba rozsirenejsich systemu.
Treba {negace, sjednoceni, disjunkce, implikace, ekvivalence}
Ale mohou byt i mensi, treba jenom {negace, disjunkce} je nejmensi, ostatni jsou syntactic sugars jakoby. Ale vsechny formule se daji napsat pouze pomoci {negace, disjunkce}
Negace vzdy musi byt soucasti uplneho systemu spojek, bez ni s eneobejdeme
S |= fi p.t.k [S spolu s (negace fi)] je…
nesplnitelna
Pokud formule je dusledkem, pak negace nemuze byt dusledkem
Dukaz primitivni:
V tabulce kde jsou radky S=1 a fi=1 z predpokladu
Pak negace fi ma 0 a tim padem rozsirena mnozina nema ani jeden radek samych 0
Predikatova logika
Obsahuje predikaty (vlastnosti) a argumenty (vstupy do predikatu)
Byt mladsi nez:
M(pavel, jirka) - M je predikat/vlastnost a ma dva argumenty
Termy a formule predikatove logiky
Termy jsou objekty (neco jako atomicke formule) a nedaji se ohodnotit.
Formule popisuji uz vlastnosti objektu a daji se ohodnotit
Treba term Pavel a mit maminku M(Pavel).
Pavel nejde ohodnotit. Pavel ma maminku jde ohodnotit
Syntakticky strom predikatove logikt
Delam stejne jako vyrokove. Postupne podle priority stepim formule na dalsi podformule az dojdu k termum. Po ceste mam jako binarni operatory tak i predikaty/funkce, ktere berou termy
Volny/vazany vyskyt promenne ve formuli
Promenna je vazana p.t.k v syntaktickem strome od jejich prvniho vyskytu dole jdu nahoru a cestou narazim na obecny/kvantovy kvantifikator s touto promennou.
Pokud na takovy kvantifikator nenarazim, pak je tato promenna volna.
Pak pisi bud:
bound(fi) = promenna1
free(fi) = promenna2
Jazyk L predikatove logiky je zadan mnozinami…
Var - promenne (clovek)
Pred - predikaty (vlatnost, byt studentem, mladsim nez…)
Func - funkce (m(x) - matka cloveka, vraci nam novy objekt - term)
Kons - konstanty (treba jeden vybrany clovek, Pavel)
Specifikace arity vsech funkci
Jak se definuji termy a formule
t ::= promenna | konstanta | vysledek funkce(x,y,z…)
f ::= false | true | t1=t2 | Predikat(termy…) | negace f | spojeni formuli | kvantifikatory
Substituce ve formuli
Nech f je formule a ma volnou promennou x.
Pak definujeme f[t/x] jako substituci. Vznikla z formule f narhazenim volne promenne termem t.
Cemu se vyhnout pri substituci
Aby novy term se nestal vazanym, protoze se zmeni smysl formule.
Nahrazuju POUZE VOLNE promenne a tak aby ZUSTALY VOLNE (tzn vetsinou novy nazev uplne)
Definice volneho termu
Term t je volny pro promennou x ve formuli fi p.t.k. pro jakoukoliv substituci x za t se nezmeni “volnost” na tomto miste substituce NEBO pokud je puvodni x vazane (protoze substituju pouze za volne promenne, tj pokud je puvodni promenna vazana, tak se neda substituovat, takze nemam co overovat pro jeji substituci, takze je term t pro ni volny)
Prirozena dedukce predikatove logiky
Je to dukazovy system
Definice Sentence
Formule je sentence, pokud nema volne promenne, vsechny jsou vazane nejakym kvantifikatorem
Deklarovana promenna
Je to takova promenna, ktera byla nejak zavedena v postupu dukazu nebo odvozovani. Nemuze se z niceho nic random objevit nova promenna
stejny princip jako v kodu - pokud chci pouzivat promennou, musim ji predem zavest nejak
Interpretace jazyka L definice
Interpretace ma 2 casti:
1. Mnozinu, kterou popisuje - universum
2. Prirazeni [||] vsech predikatu, funkci, konstant, ktere vezme ten prvek a priradi mu podmozinu univerzu podle arity prvku.
Priklad interpretace jazyka L
Necht je jazyk L zadan jako:
Pred = {S, M}, ar(S)=1, ar(M)=2,
Func = {f}, ar(f)=2,
Konst = {a}
Toto je pouze KOSTRA jazyka, nic nam nerika absolutne, dokud tomu nedame vyznam - interpretaci. Je to pouze sablona, na kterou muzeme vytvaret ruzne interpretace.
Interpretace I=(U, [||]) ma dve casti:
1. Univerzum - prirozena cisla
2. [|S|] = {2k | k je prirozene} // byt sude
[|M|] = {m,n | m < n} // byt mensi nez
[|f|] = (m,n) -> m+n // funkce soucet
[|a|] = 1 // a neni ale 1, je to pouze symbol, ale neni to primo objekt 1.
Tedy interpretace bere KOSTRU/sablonu/abstrakne zadany jazyk a pridava tomu vyznam podle syntaxe. Podobnych interperataci muze byt mnoho
Kontext promennych ro pro interpretaci I
Kontext promennych je parcialni zobrazeni (bere prvek a posila ho na nejaky prvek, ale nemusim definovat pro vsechny, treba deleni je parcialni zobrazeni, protoze neni definovano pro 0).
Je to jakasi look-up tabulka nebo slovnik, ktery udrzuje informaci o tom, jaka hondota je ulozena pro jakou promennou. Kontext mi uklada hodnoty promennych.
ro: x -> 2, y->4 // prirazeni hodnot promennym
Update kontextu promennych ro interpretace I
Update je obycejna zamena puvodni hodnoty promenne na novou hodnotu - jako kdybych proste priradil novou hodnotu ALE U TOHO SE VYTBORI UPLNE NOVY OBJEKT SLOVNIKU JAKO DEEP COPY a původní kontext ale nezanikne
ro[x:=d] znamena, ze vezmu puvodni kontext ro: x->2, y->4 a vytvorim novy ro:x->d, y->4, puvodni ale stale existuje
Interpretace termu t v kontextu ro a interpretaci I
- Mam zadany jazyk jako prazdnou kostru/sablonu bez vyznamu.
- Mam zadanou interpretaci, ktera dodava vyznam symbolum jazyka.
- Kontext promennych mi stanovuje hodnoty promennych.
Je to jako 1. syntax programovaciho jazyka, 2. semantika prog. jazyka a 3. samotne promenne. Pak jsem vybaven tremi nastroji na zodpovidani ruznych dotazu do meho systemu/kodu.
Nekdo mi zadal tyto tri veci a chci vyhodnotit vystup programu pro nejake formule nebo kod.
Treba jak interpretovat promennou v kontextu ro a interpretaci I jazyka L?
a) [|x|] = x, je to proste hodnota promenne v kontextu
b) [|konst| = konst, kostanty nezavisi na kontextu, nemeni se
c) [|f(t1,…tn)|] = [|f|] ([|t1|], … [|tn|] // interpretace funkce s termy delam postupne po slozkach, nejdriv interpretuju vsechny argumenty a pak na ne poslu interpretaci funkce
Priklad interpretace [|f(a, x)|] pro
jazyk L:
Pred = {S, M}, ar(S)=1, ar(M)=2,
Func = {f}, ar(f)=2,
Konst = {a}
Interpretaci I:
1. Univerzum - prirozena cisla
2. [|S|] = {2k | k je prirozene} // byt sude
[|M|] = {m,n | m < n} // byt mensi nez
[|f|] = (m,n) -> m+n // funkce soucet
[|a|] = 1 // a neni ale 1, je to pouze symbol, ale neni to primo objekt 1.
Deklarovane promenne:
{x,y}
A kontext promennych ro:
x -> 2,
y->3
Nekdo mi zadal abecedu/syntax pouzivanych symbolu, jejich vyznam, pouzivane promenne, jejich hodnoty.
Chce po me, abych v tomto prostredi vyhodnotil vyraz:
[|f(a,x)|]. Tedy jaka bude v tomto prostredi hodnota funkce f aplikovana na konstatnu 1 a x.
Interpretuju po slozkach:
f -> soucet prvku uvnitr.
Hodnota a je ulozena v interpretaci = 1.
Hodnota x je ulozena v kontextu promennych = 2
Tedy je to 1+2=3.
Definice pravdivosti at. formule fi v interpretaci I a kontextu ro
Znazcime I |= fi, tedy fi je pravdiva v interpretaci I a kontextu ro.
- I |= True vzdy // pravda plati za vsech podminek
- | !|= False vzdy // nepravda nikdy neplati
- I |= A, pokud interpretace termu A = 1
- I |= t1=t2 pokud jejich interpretace se rovnaji
- I |= P(t1,…tn), pokud interpretace vsech termu jsou splneny v predikatu
- I |= (negace fi), pokud I !|= fi (plati bud fi nebo negace fi)
- I |= (fi a psi) p.t.k. (I |= fi a I |= psi)
- I !|= (fi nebo psi) p.t.k. (I !|= fi a I !|= psi)
- implikace a ekvivalnece pdoobne…
Tedy se vzdy podivam, jestli pro dany jazyk a interpretaci je prava strana ohodnocena jako 1 (znacky plati jak u vyrokove lopgiky), tj jestli prava strana vyplyva z kontextu leve (sem. dusledek jakoby).
Priklad: I |= S(y)? V nasi predchozi interpretaci.
Tedy je y sude? Y = 4 => ano.
Pravdivost formuli s kvantifikatory
Jak zjistit, zd formule tvaru (ProVsechna x plati fi) je pravida pro interpretaci s kontextem?
I |= PrVs x: fi p.t.k I |= fi (pro jakykoliv update x) // tj musi to platit pro uplne vsechny updaty promennych, postupne tedy kontext promennych menim a bud hledam protipriklad, nebo se snazim dokazat inducki pravdivost
Analogicky pro to, abych dokazal Existenci, tak musim najit alespon jeden update aby to platilo.
Priklad. Je pravda, ze pro vsechna x v mem jazyku a interpretaci plati, ze soucet x,a je mensi nez 5? NEPLATI, PROTOZE MOHU X PRIRADIT HODNOTU 4, PAK X+A = 4+1 !<5. tedy nasel jsem takovy update kontextu promennych, ze neplati ProVs.
Ale plati, ze takove x alespon jedno existuje (treba x=1..3)
Sentence fi je pravdiva v I p.t.k…
Je pravida nezavisle na kontextu promennych, tedy v prazdnem kontextu. Znacime I |= fi. Tedy sentenci je jedno, jaky je kontext, protoze stejne bude updatovan.
Interpretace I je modelem sentence fi p.t.k.
Sentece fi je pravida v I ve vsech updatech, tedy v prazdnem kontextu
Splnitelna sentece/kontradicke/tautologie
Sentence je
1. splnitelna p.t.k ma model (tedy interpretaci, ve ktere je fi splnena)
2. kontradikce p.t.k nema model (nejde splnit za zadnych interpretaci)
3. tautolgie p.t.k kazda I je jejim modelem
Interpretace tady vystupuje jako ve vyrokove logice pravdivostni ohodnoceni atomickych prvku
Formule je splnitla p.t.k existuje pr. ohodnoceni takove, ze je f splnena. Ve vyrokove logice funkci takoveho ohodnoceni hraje Interpretace a kontext promennych.
Abych dokazal splnitelnost, tak staci najit Interpretaci takovou, aby formule platila. Priklad
PrVs x plati: M(x, f(x,a)). Chci toto dokazat, ze je splnitelna -> hledam nejakou interpretaci tak, aby formule platila.
Treba ze M=> byt mensi, f(x.a) = x + 1. Tedy PrVs x plati: x < x +1. SPLNENO => SPLNITELNA
Uz vim ze to neni kontradikce.
Je to ale tautologie? Hledam protipriklad Interpretace. Treba M-> je vetsi nez. Pak formule PrVs x plati: x > x +1 NEPLATI => neni tautologie…
Mnozina sentenci je splnitelna/nesplnitelna
P0okud existuje interpretace I takova, ze kazda sentence z mnoziny je splnena v teto interpretaci, tj I je modelem vsech sentenci
Pokud mnozina nema model, pak je nesplnitelna
Semanticky dusledek v predikatove logice
Rekneme, ze sentence fi je sem. dusledek mnoziny sentenci S p.t.k kazdy model mnoziny S je zaroven i modelem fi.
// analogie s vyrokovou logikou:
formule byla sem. dusledkem mnoziny p.t.k. pro vsechna ohodnoceni mnoziny, kde S=1 i formule fi=1. V predikatove logice misto ohodnoceni mame interpretace, tedy pro kazdou interpretaci S, ve ktere jsou vsechny sentence S splneny, musi byt splnena i nova sentence fi
Dokazuju bud induktivne pres modely, nebo normalni dedukci jako dukaz ze z predpokladu S mohu odvodit fi
Graf definice
Graf G j dvojice (V,E), kde V je neprazdna mnozina vrcholu a E je neprazdna mnozina dvojic {(u,v) | u,v lezi v V} a nazyvaji se hrany
Diskretni/uplny grf
Diskretni je takovy, ze nema hrany, pouze vrcholy
Uplny je takovy, ze ma vsechny mozne hrany co jdou
Bipartitni graf
Je takovy, ktery se da rozdelit na dve strany tak, ze kazda hrana vede z jedne strany do druhe
Uplny bpartitni graf
Ma vsechny mozne hrany co jde udelat, ale jsou pouze mezi partitatmi, ne v nich
Pri N vrcholech, kolik ma uplny graf hran?
Je to kazdy s kazdym ale bez opakovani, tedy je to n(n-1)/2
Epsilon neorientovany graf definice
Stejna defincie jako jednoduchy graf, ale navic se prida do trojice mnozina epsilon, ktera kazde hrane prirazuje vztah incidence - tedy pocatek a konec. Kazde hrane priradi dvojici (u,v) odkud kam vede
Tato definice povoluje smycky a oboustranne cesty
Stupen vrcholu
Pocet hran vychazejicich z tohoto vrcholu
Smycka se zapocitava jako dve hrany
Tvrzeni o Sume stupnu vrcholu
Pocet hran v grafu je (Suma vsech stupnu vrcholu)/2
Takze sectu vsechny hrany, ktere vychazeji ze vsech uzlu a vydelim dvema abych predesel zapocitani cest dvakrat pro tu stejnou hranu
Dusledek:
Kazdy graf ma sudy pocet vrcholu licheho stupne
Regularni graf
Takovy graf, ktery ma vsechny vrcholy stejneho stupne
Treba uply graf, nebo uzavrena kruznice
Skore grafu
Je to n-tice obsahujici stupne vsech vcrholu sestupne (proste usporadam vsechny stupne sestupne a hotovo)
Jak poznat, ze zadana n-tice je skore grafu?
- Skontroluju, ze je sudy pocet lichych stupnu
- Zadam vsechny vrcholy treba do primky
- Zamerim se pouze na prvni vrchol a zakreslim z nej zleva do prava jeho hrany postupne pro dalsi vrcholy (NESAHAM zatim na dalsi vrcholy)
- Odeberu prvni polozku z n-tice a u vsech zbylych odectu 1
- Ted vezmu novy prvni prvek (stary druhy) a udelam s nim totez jak krok 3-4.
- Koncim kdyz je n-tice nulova
Podgraf grafu
Je vybrana podmnozina vrcholu a hran, proste vyhodim nejake uzly a hrany z nich vychazejici
Podgraf je faktorem grafu G
p.t.k. ma vsechny puvodni vrcholy grafu G. Hrany si mohu vybrat nahodne
Graf indukovany mnozinou V`
Pokud E obsahuje vsechny hrany puvodniho E, ktere maji oba krajni vrcholy v V
Pokud v novem podgrafu vyhodime nejaky vrchol, musime z neho vyhodit i vychazejici hrany
Rozdil mezi obecnym grafem a indukovanym mnozinou V`
Obecny graf - vznikl odebranim vrcholu, hran ktere z nich vychazely a NAVIC ODEBRANIM I JINYCH hran, ktere s temito uzly nesouvisely
Indukovany - vznikl odebranim POUZE takovych hran, ktere vychazely z odebranych uzlu A ZADNYCH jinych
Isomofrni grafy g1,g2
Pokud mezi nimi existuje bijekce. Neboli daji se nakreslit tim samym obrazkem.
Skore izomornich grafu je
Stejne. trivialne maji stejny graf.
Neplati to ale obracene!
Grafy o stejnem skore nemusi byt isomorfni
Cesta v grafu definice
Cesta delky n je isomorni graf s mnozinou vrcholu V={0,1,…n} a s mnozinou E={(0,1), (1,2),…(n-1,n)} Tedy je to graf, kde z predchazejiciho uzlu se umim dostat hranou do dalsiho, dohromady mi to vytvai cestu Pn (path delky n)
Kruznice delky n
Je graf isomorfni grafu s mnozinou V={1,…n} a E={(1,2),(2,3),…(n,1)}. Tedy z kazdyho uzlu mohu hranou prejit do dalsiho a n-ty uzel se vraci na zacatek grafu a uzavira mi kruznici.
Znaci se Cn (circle delky n)
Delka cesty
Pocet hran v ceste
Trivialni cesta
Je to cesta v jednovrcholovem grafu bez hran, delky 0
Definiec sledu
Sled delky K je posloupnost vrcholu a hran v0e1, v1e2… takova, ze hrana ei je incidentni s vrcholy v(i-1) a vi.
Tzn ze hrana ei lezi mezi dvema sousednymi vrcholy.
Je to jakoby neomezeny tah grafem, neboli cesta, ktera se muze opakovat i v nekonecnych cyklech. Je to krivka, kterou mohu nepretrzite prejet graf.
Sled je uzavreny, pokud pocatecni vrchol je i koncovy a ma alespon jednu hranu, tedy je to proste cara ktera zacne v nejakem bode, pak se pohybuje libivolne po sousednich hranach a vrati se zpet i s opakovanimi)
Definice tahu
Je to sled bez opakovani hran, tedy v jednom vrcholu mohu byt libovolne moc krat, ale vzdy se tam musim dostat a odejit nepouzitou hranou
Definice cesty pomoci tahu
Cesta je tah bez opakovani vrcholu. Tedy kazdou hranu i vrcholu smim porjit pouze jednou.
Definice kruznice pomoci tahu
Kruznice je uzavreny tah, ve kterem se neopakuji vrcholy
Hierarchie mezi sledem, tahem, cestou
Sled je nejobecnejsi cara, ktera mi vede z vrcholu do sousedniho vrcholu, muze opakovat uzly i hrany.
Tah je sled, ktery zakazuje opakovane hrany, je to konkretnejsi sled
Cesta je nejkonkretenjsi sled, protoze je to tak, ktery zakazuje i opakovani vrcholu
Souvisly graf definice
P.t.k mezi kazdymi dvam vrcholy existuje cesta
Komponenta souvislosti
Je to maximalni souvisly podgraf.
Treba mam graf rozbity na dve pulky a neni souvisly mezi nimi. Tzn komponenta souvislosti je kazda z tech pulek sama o sobe, protoze v ramci sebe souvisla je
Pozadavky na grafove algoritmy
- Terminace - vzdy skonci
- Parcialni korektnost - poskytne ocekavany vysledek
Variant - neco co se menni prubezne
Invariant - nemenna vlastnost
Eulerovsky tah
Je to takovy tah, ktery obsahuje vsechny hrany a vsechny vrcholy
Eulerovsky graf
Je to takovy graf, pro ktery existuje eulerovsky tah.
Neboli je to takovy graf, ktery umim nakreslit jednim tahem, tzn projit pospojovat vsechny vrcholy vsemi hranami, ale nesmim jit dvakrat po te stejne hrane
Ma-li graf vsechny vrcholy sudeho stupne, pak tah, ktery uz nejde prodlouziy je…
uzavreny tah
Existuje otevreny eulerovsky tah
p.t.k. graf je souvisly a ma prave dva vrcholy licheho stupne (neco jako zacatek a konec)
Kdyz max G 2k vrcholu lichecho stupne, pak abych nakreslil jeho graf potrebuju
k tahu
Priklady regularnich grafu radu k=0,1,2,
Graf je k-regularni, kdy stupen vsech jeho vrcholu je k
1. k=0 je to sjednoceni diskretnich grafu (muzu jich dat libivolne mnoho)
2. k=1 sjednoceni clanku, tj grafu o dvou vrcholech a jedne hrane
3. k=2 sjednoceni kruznic, tj uzavrenych grafu nekonecne mnoho ktere jsou jenom kruznice a dva vrcholy jsou spojeny jednou hranou
Jak souvisle propojit n vrcholu s nejmensim poctem hran?
Potrebuju n-1 hran. Je to proste primka o n vrcholech a n-1 hranach
Definice stromu
Je to souvisly graf bez kruznic
Veta o dvou listech
Kazdy strom strom s alespon 2 vrcholy ma alespon 2 listy. (vrcholy s stupnem=1)
Veta o trhani listu
Kazdy strom o n vrcholech, ma n-1 hran
Mam primitivni strom o dvou vrcholech. Hrana mezi nimi je jenom jedna. Tady vznika zaver, ze mam n-1 hran. Kdyz zacnu pridavat dalsi uzly, tak se k nim prida i dalsi hrana ve stejnem poctu. Tedy pomer n a n-1 se zachovava
Pokud G je strom, tak pridanim/odebranim jedne hrany
Uzavreme nejakou kruznici/nebude G souvisly
Oba pripady narusi definici stromu
Tedy strom uz ma tolik hran, kolik musi a nemuzu zadnou pridat ani odebrat.
Definice kostry
Nech G je obecny graf. K nemu vytvorim faktor K (ma vsechny vrcholy stejne jako G). Pokud je K strom, pak je to kostra.
Kostra je pokryti vsech uzlu puvodniho grafu tak, ze je souvisle a bez kruznic.
Obecny graf G ma kostru p.t.k…
Aby existovala kostra, musi existovat strom. Strom mohu vytvorit pouze ze souvisleho grafu (to ze nema cykly vyresim tim, ze nadbytecne hrany odstranim).
Tudiz puvodni graf musi byt souvisly
Definice ohodnoceneho grafu
Je to graf G spolu se zobrazenim E->R (prirazeni cen kazde hrane).
Minimalni kostra ohodnoceneho grafu G
Je takova kostra, ktera ze vsech koster ma nejnizsi cenu
Kazdy ohodnoceny souvisly graf ma…
Kostru a ted i minimalni kostru
Kruskaluv algoritmus nalezeni nejmensi kostry
Mam zadany graf a ohodnocene hrany,
1. Vypisu si vsechny hrany od nejlevnejsi po nejdrazsi
2. Vyberu nejlevnejsi a zakreslim do grafu.
3. Vyskrtnu ze seznamu prave pouzitou hranu
4. Jdu na dalsi nejlevnejsi a zakresluju je pokud neuzavrou nejakou kruznici. Algrotmus konci kdyz jsem pokryl vsechny uzly
Tedy postup je: vem nejlevnejsi hranu pokud neudela cyklus, zakresli, jdi na dalsi nejlevnejsi hranu loop
Jarniku-Boruvkuv algoritmus nalezeni nejmensi kostry
TODO
Jake skore ma strom o n vrcholech?
Pro graf plati:
Suma skore vsech vrcholu = 2 pocet hran
Pro strom o n vrcholech plati: ma (n-1) hran
Tedy skore stormu o n vrcholech je: 2*(n-1)
Ma musi mit alespon 2 listy, tedy jeho skore musi nutne vypadat jako:
(v1, v2, v3, … , 1, 1), tedy pozice predposledni a posledni jsou listy se stupnem 1
Kolik existuje ruznych a kolik izomorfnich stromu s n vrcholy?
n^(n-2) ruznych stromu. Ale pocet neizomorfnich urcim jen z odvozeni pres skore…
Jak vytvorit Pruferuv kod stromu
Mam zakresleny strom a jeho uzly jsou ocislovany.
kod dostanu takto:
1. Najdu LIST s nejmensim cislem.
2. Odtrhnu ho.
3. Do kodu zapisu cislo ODKUD jsem to trhal.
4. Najdu dalsi LIST s nejmensim cislem.
5. Opakuju krok 1-4.
Posledni trhani nezapisuju. Kod konci kdyz mi zbyl jen jeden list
Delka kodu je o dva mensi nez je pocet vrcholu. [1,…n-2]
Jak dekodovat Pruferuv kod stormu
Mam zadanou posloupnost [x1,x2,x3…xn]
- Tato posloupnost je o 2 mensi nez je pocet vrcholu
- Urcim pocet vrcholu jako jeji delka + 2
- Rozepisu je vzestupne VSECHNY.
- Ty vrcholy, ktere chybely v zadani kodu - jsou to listy, ktere se utrhly jako prvni hned.
- Najdu mezi nimi ten nejmensi a napojim ho na prvni cislo kodu.
- Najdu druhy nejmensi a napojim ho na druhe cislo kodu.
- Pridavam takto listy na odpovidajici pozici v kodu.
- Postupne jdu vpravo podle kodu a updatuju listy, ktere jsou mensi nez dana pozice v kodu.
Orientovany graf
Je relace E podmnozina VxV, tedy hranam prirazujeme dvojice vrcholu jako pocatek a konec hrany
in(v), out(v)
Je pocet vstupnich hran do vrcholu, pocet vystupnich hran do vrcholu
Lema poctu vstupnich/vystupnich hran
Kazda hrana v grafu je zaroven pro nekoho vystupni, pro nekoho vstupni ale furt je to ta sama hrana z E
tedy
Suma in(v) = Suma out(v) = |E|
Definice acyklickeho grafu a co plati pro jeho dva zajimave uzly
Je to takovy graf, ktery nema zadny cyklus.
Pro tento graf plati, ze existuje poc. vrchol s in(v)=0 a koncovy vrchol s out(v)=0. Je to zdroj a vylevka.
Topologicke usporadani grafu
Je to hezke usporadani grafu zleva do prava (vetsinou), ktere vzniklo tak, ze pokud jsou dva prvky v relaci v1,v2 pak i v top. usporadani jsou napsany v1 pred v2. Tedy pokud vede cesta z v1 do v2, pak v1 bude stat driv nez v2. Toto ale plati pouze pro acyklicke grafy. Jinak tam vznikne smycka.
Topologicke usporadani ma hrany pouze jednim smerem, nemuzeme se vracet.
Jak rozpoznat ze je orientovany graf acyklicky?
Pokud ma topologicke ocislovani vrcholu //tzn dana relace uz plati zleva do prava a je splnena uz hned jak to ctu
Obarveni vrcholu grafu G
Je zobrazeni V->B, ktere vrcholum prirazuje barvy tak, ze pokud jsou sousede, tak maji ruzne barvy
K-barevny graf
Je graf, ktery se da obarvit K barvami
Barevnost grafu
Je nejnizsi K takove, ktere obarvi cely graf
// nejsetrnejsi barveni
Znaci se velke Chi(G)
Uplny graf o n vrcholech ma barevnost…
N, protoze vsichni jsou si sousede a tim padem potrebujem tolik barev kolik je uzlu
Klika grafu G
Klika grafu G je podmnozina uzlu K takova, ze kazda dvojice uzlu z kliky je propojena cestou.
Je to nejvetsi podgraf grafu G ktery je uplny. Tedy celkovy graf G nemusi byt uplny, ale nejaky mensi podgraf muze byt uplny. Nejvetsi takovy podgraf je klika
Klikavost grafu
znaci se w(G) je nejpocetnejsi klika grafu G. Tedy pocet vrcholu v nejvetsim uplnem podgrafu grafu G
Co obecne plati pro vztah barevnosti a klikavosti
klikavost <= barevnosti
Obecne tedy potrebujem vice barev na obarveni grafu, nez ma uplnou podmonozinu
Protoze kdyz si predstavime uplny graf, pak je jeho klikavost=n, barevnost=n.
Kdyz k tomuto grafu pridavame vrcholy, tak muze narustat barevnost, ale nemusi narustat klikavost.
Nezavisla mnozina grafu G
je mnozina vrcholu M takova, ze zadne dva vrcholy z M nejsou spojeny (opak klikavosti jakoby, je to mnozina vrcholu, mezi kterymi neni prima vazba)
Nezavistlost grafu G
Je nejvetsi nezavisla mnozina grafu G, znaci se alfa(G)
Priklad - jak zjistim, ktere procesy nesmi probehnout soucasne a kolik etap to bude trvat aby probehly za sebou
Mam graf kde body jsou procesy, hrany je zakaz soucasneho deje.
Pak obarvim tento graf barvami 1,2,3,… Vznikne mi mnozina barev a v kazde barve mnozina procesu - toto jsou nezavisle procesy, ktere mohou bezet soucasne. Kolik je barev - tolik bude etap chronologicky.
Tvrzeni spojitosti nezavislosti a klikavosti grafu G
Pro LIBOVOLNY graf G s n vrcholy plati:
1. alfa(g) * chi(g) >= n
2. alfa(g) + chi(g) <= n + 1
Graf je jednobarevny p.t.k.
je diskretni, tj nema hrany
Graf je dvoubrevny p.t.k.
ekvivalntni podminky vsechny tri
- je bipartitni
- neobsahuje kruznici liche delky
Algoritmus na barveni grafu dvema barvami
Obarvim prvni uzel 1. barvou, vsechny sousedy 2. Pak z kazdeho souseda obarvim jeho sousedy 1. barvou atd do sirky
Jak odhadnout barevnost grafu v nejhorsim pripade podle stupne grafu
Pokud je max(d(v)) = 50, maximalni pocet hran vychazejicich z vrcholu je 50, tak tam mame minimalne 51 vrcholu. V nejhorsim pripade je to uplny graf o 51 vrcholech tedy nejhorsi pripade potrebujeme 51 barev.
Tedy obecne je to n barev, neboli max(d(v)) + 1
Dosazitelnost vrcholu v orientovanem grafu G
Bod y je dosazitelny z bodu x, pokud existuje ORIENTOVANA JEDNOSMERNA cesta z x do y. Je to relace.
Oboustranna dosazitelnost
Pokud mezi dvema body existuje OBOUSTRANNA cesta
Orientovany graf je silne souvisly definice
Pro kazde dva vrcholy existuje OBOUSMERNA cesta
pro neorientovany graf je souvislost existence cesty
Souvisly orientovany graf G je SILNE souvisly p.t.k. kazda jeho hrana lezi…
v nejakem cyklu, tj cyklus nam zaruci cestu tam i nazpet aby platila obousmerna dosazitelnost dvou bodu
Silne souvisla komponenta definice
je to mnozina bodu grafu G pro kterou plati:
je to nejvetsi podmnozina pro kterou plati, ze podgraf indukovany B je silne souvisly
Neboli je to nejvetsi mnozina bodu takova, ze jsou navzajem obousmerne dosazitelne, ale nejde se z nich dostat uz ven, jakmile jsem se dostal do teto mnoziny, uz neexistuje cesta opacne orientovana, tj existuje jenom cesta dovnitr, ale ne obracene, protoze to by byl cyklus a tim by se mi dve komponenty podle defincie slily dohromady
Kondenzace grafu G
Je to prosty graf bez smycek, jehoz vrcholy jsou komponenty silne souvislosti G a pro dve ruzne komponenty SS vede orientovana hrana (JEDNOSMERNE) pouze pokud v jedne existue x a ve druhe existuje y tak, ze vede hrana z x do y
Tedy je to jakesi zhusteni vsech bodu v ramci komponent silne souvislosti, tvori to tridy ekvivalnece a vsechny vrcholy v jeden KSS mi rikaji totez a splynou do jednoho vrcholu.
Je kondenzace or. grafu acyklicky graf?
Je, protoze kdyby to nebyl acyklicky graf, tak to znamena, ze mezi dvemi KSS stale existuje smycka, jenomze to nesedi do definice, tzn jsme je meli spojit do jedne vetsi KSS.
Les o k stromech o celkem n vrcholech ma kolik hran minimalne?
n-k
Protoze v souvislem neor. grafu je n-1 hran. Kdyz odebereme jednu hranu, rozpadne se nam na dve komponenty a hran bude n-1. Kdyz odebereme k hran, vznikne nam k komponent a celkem n-k hran
Kolik je maximalni pocet hran pro graf o n vrcholech a dvou komponentach souvislosti?
Nejoptimalnejsi bude graf rozdelit na jeden vrchol a pak zbytek. Toto budou moje dve komponenty souvislosti. Pak prvni komponenta je diskretni = 0 hran, druhou udelam uplnou, tedy je tam (n-1) vrcholu kazdy s kazdym, tedy (n-1)(n-2)/2
Celkem tedy:
0 + (n-1)(n-2)/2
Jadro grafu
Je to jakasi uzavrena/izolovana mnozina vrcholu, do ktere se musim umet dostat ze vsech vrcholu vne, ale jakmile jsem uvnitr, uz se tam nemuzu pohybovat.
Tedy je to mnozina takovych bodu, ktere mezi sebou nejsou propojeny, ale vede do teto mnoziny cesta z kazdeho vnejsiho bodu
Postup nalezeni jadra grafu
- Udelej topologicke usporadani
- Posledni prvek dej do jadra
- Vsechny prvky, ktere jsou naveseny pred tim, tj existuje plynula cesta z tohoto prvku do posledniho - dej mimo
- Prvky ktere nikam nevedou/neexistuje cesta do posledniho - dej taky do jadra (jsou to slepe ulicky a nesmi mezi nimi byt cesta)
Postup nalezeni komponent souvislosti
Delam to pomoci DFS
1. Zacnu v nejakem vrcholu a otevriam jeho cas
2. Jdu do jeho moznych sousedu a tam taky oteviram cas
3. Kdyz uz nemam kam jit (bud sousede nejsou, nebo uz jsem v nich byl), tak zaviram cas a vracim se nazpet o predchozi uzel a tam pokracuju rekurzi.
4. Na uplnem konci se vratim do prvniho vrcholu a uzavru jeho cas.
Vsechny navstivene vrcholy za tento jeden beh pridam do jedne komponenty/i silne souvislosti.
Pokud jsem nepokryl vsechny vrcholy, spustim ten samy algoritmus z nejakej doposud neotevreneho uzlu -> on mi najde dalsi komponentu souvislosti atd…
Kolikrat spustim DFS -> tolik komponent souvislosti
Vrchol je koren p.t.k.
Se z nej mohu dostat do vsech ostatnich uzlu alespon jednosmernou cestou
Strom je korenovy p.t.k.
ma koren
Hladovy algoritmus barveni
Obarvim prvni uzel prvni barvou, dalsi uzly barvim bud novou barvou, nebo prvni “uvolnenou” barvou z mnoziny uchovanych pouzitych barev
Jak najit takovy graf, na ktery potrebujeme alespon 3 barvy, ale aby neobsahoval trojuhelnik
Jelikoz graf nebude dvoubarevny, tak nebude bipartitni, tj je to kruznice s lichym poctem vrcholu
Plati totiz tvrzeni ze:
g je dvoubarevny p.t.k je bipartitni p.t.k nema cyklus liche delky
Dominantni mnozina vrcholu G
je to mnozina takovych bodu, ze jsou na ne napojeny i zbytek vrcholu z G
//tedy rikam ze tyto dominantni vrcholy mi ovladaji/jsou spojeny s/vidi na ostatni vrcholy
Dominance G
Je to nejmensi dominantni mnozina vrcholu G, tedy nejmensi pocet prvku, pres ktery “vidim” i na ostatni prvky. Jinak receno ze kdyz vezmu dominantni prvek, tak je na nem napojenej retizek dalsich vrcholu. Kdybych ho odebral z grafu, mohou zustat jeste vrcholy, pro ne tedy musim taky najit dominantni prvek, pokud mi nic nezustane
znaci se beta(g)
Jaky je obecne vztah mezi nezavislosti a dominanci g?
alfa(g) >= beta(g), protoze dominantni prvek muze byt klidne i jenom jeden, a zbytek je na nem zavesen do hvezdy.
Naopak mnozina nezavislych prvku je takova, ze se navzajem absolutne nevidi, tj abychom jim dominovali, muzeme potrebovat v nejhorsim pripade az stejny pocet dominantnich prvku. A pokud mame nejaky dominantni prvek ktery ovlada jiny prvek mimo nezavislou mnozinu, tak pak nezavislou mnozinu muzeme o ten prvek rozsirit a tim se pomer nezmeni
Algoritmus nalezeni Eulerova tahu
TODO
Zavedeni/eliminace kvantifikatoru
TODO
Normalni formy, CNF, DNF
Kazda formule se da prepsat na normalni formu, ktera ma dva typy:
Konjuktivni normalni forma:
formule f je v CNF p.t.k:
f = Konjunkce Disjunkci literalu, tedy ve forme:
f = (a V ~a) A (~b V b) A… tedy je to SJEDNOCENI takovych podformuli, kde kazda podfurmule je DISUJNKCE literalu
Literal je atomicka formule | negace atomicke formule
a | ~a je literal
Disjunkntni normlani forma - DNF je obracene:
je to velka disjunkce mensich podformuli, ktere jsou konjunkcemi
