[DÉEM]
Hali!
Hosszú lesz. :)
Kedden nagyzh. Előtte hétfőn 6-tól nagykonzit tartunk, igyekszem a Neumann-t lefoglalni. 2 óránk lesz, kicsit szűkös, ezért most kaptok itt egy kis írásbeli összefoglalót a zh lehetséges feladatairól tippekkel. A konzi menete az lesz, hogy azokba megyünk elsősorban bele, amik ezt elolvasva sem világosak, majd végigfutunk egy korábbi nagyzh-n.

Elmélet:

1. Hamilton kör létezésének elégséges feltétele bizonyítással. Dirac, és Ore tétel. Ore tétel bizonyítása:
https://hu.wikipedia.org/wiki/Ore-t%C3%A9tel
Dirac bizonyítása: ha minden csúcs fokszáma min n/2, akkor bármely kettő összege min n -> Ore tételre visszavezettük, azt bizonyítjuk.

2. Euler poliéder tétel, és bizonyítása. Az alábbi linken a klasszikus bizonyítás amit vettünk.
https://hu.wikipedia.org/…/Euler-f%C3%A9le_poli%C3%A9dert%C…

3. Ötszín tétel. Bérces-dia, 75. oldal
http://users.itk.ppke.hu/~b_novak/DM/szinezes_2016.pdf

4. Mikor egyenlő két halmaz számossága: ha bijektív(kölcsönösen egyértelű) leképezést tudunk köztük létrehozni.

5. Racionáls számok megszámlálhatóak - biz. Alábbi lap második felében.
http://www.bethlen.hu/…/math…/forras/Halmazok_szamossaga.htm

6.:]0 1[ közti valós számok nem megszámlálhatóak.
https://hu.wikipedia.org/…/%C3%81tl%C3%B3s_elj%C3%A1r%C3%A1s

7.Egy megadott halmaz számosságának eldöntése. Előisereteid/tapasztalataid alapján sejtesz valamit -> ha megszámlálhatónak sejted, próbálod sorbarendezni, ha megszámlálhatatlannak (ez jellemzően valami geometriai alakzat pontjainak száma lesz), valami vetítéssel oldod meg, ilyet mindenképp csinálunk.

8. Ford-Fulkerson tétel kimond, bizonyít.
Bérces néni Folyamok diája.

Gyakorlat:
1. létezhet e gráf megadott fokszámokkal.
Buktatók:
-Fokszámok összege páratlan: nem lehet.
-van 0 és n-1 is köztük: nem lehet, HA egyszerű gráf a kérdés, mivel az egyik semmivel nincs összekötve, egy másik meg mindennel.
-Ha nem kell egszerű legyen, akkor lehet: 0, 1, 2, 3. A 3 össze van kötve az 1-gyel, a 2-vel meg duplán.
Más trükk nem szokott lenni, ha úgy találod, hogy lehet, azért inkább rajzold fel, sokszor a feladat is kéri.

2. Euler kör, út, Hamilton kör, út rajzolása. Vizsgáld meg előbb a feltételeket, ne próbálkozz hiába. Cerua, radír legyen nálad :D

3. Feszítőfák keresése.
Nem súlyozott gráfon:
-Szélességi, mélységi: http://project.mit.bme.hu/mi_almanach/books/aima/ch03s04
Súlyozott gráfban minimális keresése:
-Prim: https://hu.wikipedia.org/wiki/Prim-algoritmus
-Kruskal: https://hu.wikipedia.org/wiki/Kruskal-algoritmus

4. Gráfok mátrixreprezentációi: http://rs1.sze.hu/~hajbat/matrixok.pdf

5. Preorder, inorder. postorder bejárások: https://en.wikipedia.org/wiki/Tree_traversal
Vedd észre, hogy mindhárom bejárásnál a szaggatott vonallal ugyanazon az úton járunk végig, és minden csúcsot háromszor érintünk: Föntről lefelé-balra, balrál át jobbra, és jobbről vissza föl. A különbség csak annyi, hogy Preordernél akkor írjuk le a csúcsot, mikor lefelé megyünk, inordernél balról jobbra haladtunkban, postordernél meg fölfelé.

6. Gráfok színezése. Muszáj próbálgatni, de vannak támpontok: Biztos nem kell több szín, mint amennyi csúcsa van a gráfnak, és biztos nem elég kevesebb, mint a legnagyobb teljes részgráf mérete. Jó esetben ez eléggé leszűkíti, a max teljes részgráffal érdemes kezdeni, azoknak adni különböző színt.

7. Dijkstra algoritmus. http://specmat.wiki/images/3/3b/Dijkstra_hujterb.pdf

8. Síkbarajzolhatóság, homeomorfia. Euler tétel következményeit meg kell vizsgálni rá, ha sérti, nem síkbarajzolható. Keresni kell benne K5, vagy K3,3 vagy azzal homeomorf részgráfot. Ha van, nem síkgráf. Végül síkba kell rajzolni, ha mindegyik teszten átment.
https://users.itk.ppke.hu/~b…/…/sikba_rajzolhato_grafok1.pdf
http://users.itk.ppke.hu/~szako1/sikgraf.pdf