Számítástudomány
A kurzus 13 szekcióból áll: Gráfelméleti alapok, Kuratowski gráfok, síkbarajzolhatóság, Gráfalgoritmusok, Kromatikus szám, klikk, perfekt gráfok, Gráfparaméterek, párosítások, Hálózati folyamok, Menger tételei, többszörös összefüggőség, Páros gráfok, párosítások, Irányított gráfok, gráfalgoritmusok irányított gráfokban, Oszthatóság, Euklideszi algoritmus & Diofantoszi egyenletek, Kongruenciák, RSA kódolás, Boole-algebra alapjai
Gráfelméleti alapok
- -
A gráf csúcsokból és azokat összekötő élekből áll.
- -
Egy gráf összefüggő, ha bármelyik csúcsából el lehet jutni bármelyik másik csúcsába élek mentén.
- -
A gráf egy csúcsának fokszáma a gráf e csúcsában összefutó élek száma.
- -
Egy gráfban körnek nevezünk egy olyan utat, amely csupa különböző csúcsokon és éleken haladva visszavezet a kiinduló csúcsába.
- -
Ha egy gráfban nincs kör, de maga a gráf összefüggő, akkor fának nevezzük.
- -
Azokat a gráfokat, ahol minden csúcs mindegyikkel össze van kötve, teljes gráfnak hívjuk.
- -
Egy gráf egyszerű, ha nincs benne sem többszörös él, sem hurokél.
- -
Két szám akkor kongruensek mod m, ha m osztja a két szám különbségét.
- -
Kongruenciák szorzása és osztása egy egész számmal.
- -
Egy gráf Euler-köre olyan zárt élsorozat, amely a gráf összes élét pontosan egyszer tartalmazza.
Kuratowski gráfok, síkbarajzolhatóság
- -
A $G$ gráf egy $( V(G), E(G) )$ rendezett pár, ahol $V(G)$ egy nem üres halmaz, $E(G)$ pedig a $V(G)$-ből képezhető párok egy halmaza.
- -
Azokat az élsorozatokat, amelyek a gráf semelyik pontján nem haladnak át többször, útnak nevezzük.
- -
Ha egy élsorozat ugyanabból a csúcsból indul, mint ahova érkezik, akkor körsétának nevezzük.
- -
Minden gráfban a csúcsok fokszámainak összege az élek számának a kétszerese.
- -
Ha egy gráfban nincs kör, de maga a gráf összefüggő, akkor fának nevezzük.
- -
A nem összefüggő körmentes gráfok neve erdő.
- -
Egy gráf síkbarajzolható, ha lerajzolható úgy, hogy élei csak a csúcspontokban találkozzanak.
- -
A Kuratowski-tétel szerint egy gráf pontosan akkor nem síkbarajzolható, ha tartalmaz $K_{3,3}$-mal vagy $K_5$-tel topológiailag izomorf részgráfot.
- -
Az Euler-féle poliéder-tétel azt mondja, hogy egy konvex poliéder csúcsainak számának és lapjainak számának összege megegyezik az élek száma plusz kettővel.
- -
A síkbarajzolhatóság feltétele, ha egy egyszerű gráfban minden kör legalább k hosszú.
- -
Ha egy gráf síkbarajzolható, akkor az élek számának kisebbnek vagy egyenlőnek kell lennie a csúcsok számának 3-szorosa minusz 6-nál.
Gráfalgoritmusok
- -
Egy gráf feszítőfája a gráf minden csúcsát tartalmazó fa részgráf.
- -
A minimális feszítőfa egy gráfban a legkisebb élsúlyú feszítőfa.
- -
A Kruskal algoritmus segítségével minimális feszítőfát lehet megtalálni.
- -
Gráfok egy adott pontjából való feltérképezésére alkalmas módszer a szélességi keresés (BFS = Breadth-first search).
- -
A DFS algoritmus lényege, hogy elindulunk egy úton, és megyünk, amíg csak tudunk.
- -
A BFS és DFS algoritmusok végrehajtása során a gráfnak egy-egy feszítőfáját kapjuk. Ezeket nevezzük BFS és DFS fának.
Kromatikus szám, klikk, perfekt gráfok
- -
A legkevesebb színt, amivel egy gráf csúcsait kiszinezhetjük úgy, hogy a szomszédos csúcsok ne legyenek egyforma színűek, a gráf kromatikus számának nevezzük.
- -
Egy $G$ egyszerű gráfban klikknek nevezzük azokat a részgráfokat, amelyek teljes gráfok.
- -
Egy gráf klikkszáma a gráfban található maximális klikk elemszáma.
- -
A $G$ gráfban a $G'$ részgráf feszített részgráf, ha bármely két csúcs a $G'$ gráfban pontosan akkor szomszédos, ha $G$-ben is szomszédos.
- -
Ha egy gráf minden feszített részgráfája igaz, hogy azok kromatikus száma egyenlő a klikkszámával, akkor a gráf perfekt.
- -
Egy gráf kromatikus száma a gráf klikkszáma és a gráf maximális fokszáma plusz egy közé esik.
- -
A mohó színezés egy algoritmus a gráfok színezésére.
- -
A Brooks-tétel egy felső becslés a kromatikus számra.
- -
Egy $G$ gráfban azt a legkisebb számot, amire a gráfnak már van jó élszínezése, a $G$ gráf élkromatikus számának nevezzük.
- -
A Vizing-tétel a gráfok élkromatikus számára ad alsó és felső becslést.
- -
Az intervallumgráf egy olyan gráf, melynek csúcsai megfeleltethetőek a valós számok egy-egy intervallumának, és két csúcs között akkor vezet él, ha a nekik megfeleltethető két intervallum metszete nem üres.
- -
Egy gráfot páros gráfnak nevezünk, ha csúcsainak halmaza felbontható két diszjunkt részhalmazra, úgy hogy a két halmazon belül nem vezetnek élek, csak köztük.
- -
A Mycielski-gráfok olyan gráfok, amelyek klikkszáma 2, a kromatikus számuk pedig bármilyen nagy lehet.
Gráfparaméterek, párosítások
- -
A független ponthalmaz precíz definíciójára mindjárt kettő is van.
- -
Egy $G$ gráfban a $T \subset V(G)$ ponthalmaz lefogó ponthalmaz, ha $G$ minden élének legalább az egyik végpontja $T$-ben van.
- -
Ha vesszük egy gráfban a maximális számú független pontokat és a minimális számú lefogó pontokat, akkor épp megkapjuk a gráf összes pontját.
- -
Egy $G$ gráf éleinek $M$ részhalmaza független élhalmaz, ha $M$ semelyik két elemének nincs közös végpontja.
- -
Egy $G$ gráf éleinek $R$ részhalmaza lefogó élhalmaz, ha a gráf minden csúcsa valamelyik $R$-beli él végpontja.
- -
Ha vesszük egy gráfban a minimális számú lefogó éleket, és a maximális számú független éleket, akkor a gráf minden pontjához pontosan egy él fog tartozni.
- -
A lefogó élhalmaz mindig nagyobb vagy egyenlő, mint a független ponthalmaz. A lefogó ponthalmaz mindig nagyobb vagy egyenlő, mint a független élhalmaz.
- -
Egy $G$ gráf akkor és csak akkor páros, ha minden $G$-ben szereplő kör páros hosszúságú.
- -
Egy $G$ gráfban az $E(G)$ élhalmaznak egy $M$ részhalmazát párosításnak nevezzük, ha $M$ semelyik két elemének nincs közös végpontja.
- -
Egy élsorozat akkor lesz egy párosítás javító útja, ha a következő 3 feltétel teljesül rá.
- -
Azokat a párosításokat nevezzük teljes párosításoknak, ami a gráf összes csúcsát lefedi.
- -
Egy gráfban akkor és csakis akkor létezik teljes párosítás, ha bárhogyan hagyunk el a gráfból néhány pontot, a megmaradt gráfban a páratlan komponensek száma nem több az elhagyott pontok számánál.
Hálózati folyamok
- -
Legyen $X$ egy részhalmaza a gráfnak, ami tartalmazza $S$-t. Ekkor az $X$ és a többi csúcs alkotta részgráf (amik nincsenek benne az $X$-ben) közötti éleket vágásnak nevezzük.
- -
Egy vágás kapacitása a vágásban szereplő élek kapacitásainak összege.
- -
A Ford-Fulkerson algoritmus egy olyan algoritmus, amit a maximális folyam megkeresésére használunk.
- -
Irányított gráfban egy él kapacitása az a nem negatív valós szám, amit hozzá rendelünk az élhez.
- -
A $(G, S, T, c)$ egy hálózat.
- -
A hálózatban folyamnak nevezünk egy olyan függvényt, amely az élekhez rendel hozzá pozitív valós számokat és amire teljesül, hogy az egy csúcsba befolyó mennyiség megegyezik a csúcsból kifolyóval.
- -
A folyam értékén az S-ből kifolyó és S-be befolyó mennyiségek különbségét értjük.
- -
A Ford-Fulkerson tétel azt mondja ki, hogy egy hálózatban a maximális folyam mindig megegyezik a minimális vágással.
Menger tételei, többszörös összefüggőség
- -
Egy $G$ gráf $k$-szorosan élösszefüggő, ha bárhogyan hagyunk el belőle $k$-nál kevesebb élt, a maradék gráf összefüggő marad.
- -
Egy $G$ gráf $k$-szorosan pontösszefüggő, ha legalább $k+1$ pontja van és bárhogyan hagyunk el belőle $k$-nál kevesebb pontot, a maradék gráf összefüggő marad.
- -
Menger tételei egy G irányított gráfban lévő élidegen és pontidegen utak maximális számáról szólnak.
Páros gráfok, párosítások
- -
Hall tétele arról szól, hogy egy $G(A,B,E)$ páros gráfban mikor létezik $A$-t fedő párosítás.
- -
Frobenius tétele arról szól, hogy mikor létezik egy gráfban teljes párosítás.
Irányított gráfok, gráfalgoritmusok irányított gráfokban
- -
A DFS algoritmusnak az a lényege, hogy kiindulunk egy csúcsból, és megyünk ameddig tudunk.
- -
A DFS algoritmus eredményeként kapjuk a DFS-fát.
- -
A BFS-algoritmus lényege, hogy kiindulunk egy csúcsból, aztán megkeressük a közvetlen szomszédjait. Innen folytatódik az algoritmus, és az új csúcsoknak keressük meg a szomszédjait.
- -
A BFS algoritmus eredményeként kapjuk a BFS-fát.
- -
A Dijkstra algoritmus lényege, hogy kiválasztunk egy pontot, és ebből a pontból kiindulva csúcsról csúcsra haladva felderítjük az egész gráfot.
Oszthatóság
- -
Két számok legnagyobb közös osztója az a szám, amelyik mindkét számot osztja és ezek közül a legnagyobb.
- -
Két szám relatív prímek, ha a legnagyobb közös osztójuk 1.
- -
Néhány izgalmas oszthatósági szabály.
- -
A nullától és az egységszorzóktól különböző összes $n$ egész szám felbontható prímek szorzatára a sorrendtől és az egységszeresektől eltekintve egyértelműen.
- -
Egy $p$ szám akkor prím, ha $p$ oszt egy szorzatot, akkor csak az egyik szorzótényezőnek lehet osztója.
- -
Egy $q$ szám felbonthatatlan, ha nem létezik olyan egységtől különböző $a$ és $b$ szám, hogy $q=ab$
Euklideszi algoritmus & Diofantoszi egyenletek
- -
Az euklideszi algoritmus egy formányos módszer két szám legnagyobb közös osztójának kiszámolására.
- -
A Diofantoszi egyenletek olyan egész együtthatós kétismeretlenes egyenletek, amelyek megoldásait az egész számok halmazán keressük.
Kongruenciák, RSA kódolás
- -
Ha $a$ és $b$ ugyanazt a maradékot adja $m$-mel osztva, akkor azt mondjuk, hogy $a$ és $b$ kongruensek modulo $m$.
- -
A kongruencia reflexív, szimmetrikus és tranzitív.
- -
Két szám akkor kongruensek mod m, ha m osztja a két szám különbségét.
- -
Kongruenciák szorzása és osztása egy egész számmal.
- -
Egy adott $m$ modulus esetén az $a$-val kongruens elemek halmazát az $a$ által reprezentált maradékosztálynak nevezzük.
- -
Egy mod $m$ modulus esetén az $m$-hez relatív prím elemekből álló maradékosztályokat redukált maradékosztálynak nevezzük.
- -
Az euler féle $ \varphi$ függvény azt adja meg, hogy hány $m$-nél nem nagyobb, $m$-hez relatív prím pozitív szám létezik.
- -
A kis Fermat-tétel általánosítása.
- -
A kis Fermat-tétel szerint ha veszünk egy $a$ egész számot és azt $p$-edik hatványra emeljük, ahol $p$ prímszám, akkor ez a hatvány $p$-vel osztva $a$ maradékot ad.
- -
A lineáris kongruenciák olyan kongruenciák, amikben x is szerepel.
- -
Lineáris kongruenciák megoldásának lépései.
- -
Az RSA lényege, hogy a titkosítás kulcsa nyilvános, vagyis azt bárki ismerheti. Csak a dekódolás kulcsa az, ami titkos.
Boole-algebra alapjai
- -
Az univerzális kvantor egy jelölése a "minden" kifejezésnek.
- -
Az egzisztenciális kvantor egy jelölése a "létezik" vagy "van olyan" kifejezésnek.
- -
Egy $A$ kijelentés negációja az a kijelentés, amely akkor igaz, ha $A$ hamis és akkor hamis, ha $A$ igaz.
- -
Az állítás (vagy kijelentés) olyan kijelentő mondat, amelyről egyértelműen eldönthetjük, hogy az igaz vagy hamis.
- -
Két kijelentés konjunkciója pontosan akkor igaz, ha mindkét kijelentés igaz, különben hamis.
- -
Két kijelentés diszjunkciója pontosan akkor igaz, ha legalább az egyik kijelentés igaz, különben hamis.
- -
Az implikáció akkor hamis, ha $A$ igaz és $B$ hamis, minden más esetben igaz.
- -
Az ekvivalencia akkor igaz, ha $A$ és $B$ logikai értéke azonos, különben hamis.
- -
De Morgan azonosságok a konjunkció, diszjunkció, implikáció és ekvivalencia tagadásaira.
- -
A diszjunktív normálforma, röviden DNF egy olyan alakja egy logikai formuláknak, ahol a művelet a változóinak vagy negáltjainak konjunkcióinak diszjunkciója.