Számítástudomány

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.

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.

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.

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.

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.

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.

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.

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.

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.

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$

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.

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.

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.