Gráfelmélet

A végső tematika az utolsó előadás végén pontosítva lesz.

• Gráfok kódolására szolgáló módszerek
• Séták, utak gráfokban
• Sétával és úttal való összeköthetőség ekvivalenciája
• Úttal való összeköthetőség ekvivalenciareláció volta
• Gráfok komponensei
• Összefüggő gráfok
• A szomszédsági mátrix hatványai gráfelméleti értelmezése
• Mátrix hatványozása
• Egy összefüggő gráf minimális összefüggő részgráfjának megkeresése
• Fák
• Fák definíciójával ekvivalens tulajdonságok
• Gráfok ághajtással történő növekezdése
• Fák növekedése
• Fák csúcsainak és éleinek száma közti kapcsolat
• Legsúlyosabb megengedett halmaz keresésének problémája
• Legsúlyosabb megengedett halmaz keresésének problémája és a legolcsóbb feszítőfa problémájának kapcsolata
• Három példa a legsúlyosabb megengedett halmaz keresésének problémájára
• Mohó algoritmus a legsúlyosabb megengedett halmaz keresésének problémájára
• A három példa diszkussziója
• A mohó algoritmus helyességére vonatkozó tétel (matroid fogalma, Edmonds-tétel)
• Vonal, kör fogalma
• Euler-vonal, zárt Euler-vonal
• Euler-vonalak mohó (triviális) növelése
• Euler-vonalak beszúrásos növelése
• Vonal növelés mohó és beszúrásos módon
• Euler-tétele
• Kínai postás problémája
• Kínai postás problémáját megoldó algoritmus
• A kínai postás problémáját megoldó algoritmus helyessége
• Hamilton-kör, Hamilton-út
• Hamilton-utak mohó növelése, Hamilton utak csavart növelése
• Hamilton-út keresése sűrű gráfokban
• Hamilton-utak triviális bezárása, Hamilton-utak csavart bezárása
• Hamilton-kör keresése sűrű gráfokban
• Dirac-tétel
• Utazó ügynök probléma
• Közelítő algoritmusok és a közelítés jóságánal mérése
• Hatékony 2-es faktorú közelítőalgoritmus
• A hatékony 2-es faktorú közelítő algoritmus helyességének igazolása
• Hatékony 3/2-es faktorú közelítőalgoritmus
• A hatékony 3/2-es faktorú közelítő algoritmus helyességének igazolása
• Színezés, jó színezés, színezési probléma, khí paraméter
• 2-színezhető gráfok karakterizációja
• Mohó színezési algoritmus
• Kromatikus szám becslése a maximális fokszám segítségével
• Nem reguláris összefüggő gráfok mohó színezése
• Brooks-tétel háromszorosan összefüggő gráf esetén
• Síkgráfok 6-színezése
• Intervallum gráfok, intervallum gráfok színezése
• Triviális átszínezés, Kempe-átszínezés
• Síkgráfok 5-színezése
• Klikkek, klikk probléma, omega paraméter
• Az omega és khí paraméter viszonya
• Háromszög nélküli nagy kromatikus számú gráfok konstrukciója
• Párosítás, párosítási probléma, nű paraméter
• Mohó párosítás növelő algoritmus
• Javító út
• Javító út létezése mellett párosítás javítása
• Berge-tétel
• Javító út keresésen alapuló maximális párosítást megtaláló algoritmus
• Kőnig-akadály
• Mit akadályoz meg egy Kőnig-akadály?
• Kőnig---Hall-tétel
• Teljes párosítások létezésére vonatkozó szükséges és elegendő feltétel, Kőnig---Frobenius-tétel
• A nű paraméterre vonatkozó Kőnig-akadályokon alapuló becslése
• A nű paraméterre vonatkozó minimax formula felírása
• Lefogó ponthalmaz, lefogási probléma, tau paraméter
• A nű és tau paraméter viszonya
• Kőnig-tétele
• Mohó javító út kezdemény növelő algoritmus
• Javító út keresése páros gráfokban, Kőnig-Egerváry-algoritmus (Magyar módszer)
• Az algoritmus helyessége
• Tutte-akadály
• Mit akadályoz meg egy Tutte-akadály?
• Tutte-tétel kimondása
• Tutte-tétel könnyű irányának azonosítása és indoklása
• nű paraméterre vonatkozó Tutte-akadályokon alapuló becslés
• Berge-formula felírása
• Mohó javító kezdemény növelő algoritmus az összes párosítatlan csúcsból indítva
• A kereső erdő különböző komponensébe eső külső pontok közti él esetén javító út kezdemények összeolvasztása javító úttá
• Külső pontok közti él hiánya esetén nincs javító út
• A kereső erdő azonos komponensébe eső külső pontok közti él esetén a javító út kezdemények csavarása
• Zsugorítás és zsugorítás hatása a kereső erdőre és párosításra. (LÁSD MINTAVIZSGA 4-ES KÉRDÉS!)
• Független ponthalmazok, független ponthalmazok problémája, alfa paraméter
• Klikkek, klikk probléma, omega paraméter
• Lefogó ponthalmazok, lefogó ponthalmazok problémája, tau paraméter
• A fenti három probléma kapcsolata
• Mohó algoritmus független halmaz keresésére
• A mohó algoritmus analízise
• Módosított mohó algoritmus
• A módosított mohó algoritmus analízise
• Ekvivalencia gráfok
• Erősített analízis a módosított mohó algoritmusra
• Turán-gráfok, Turán-tétel
• Extremális gráfelmélet
• C₄-et nem tartalmazó gráfok élszáma
• R(k,l) Ramsey-számok
• Ramsey-tétel
• Ramsey-tétel több színre történő általánosításának kimondása
• Ramsey-tétel k-as részhalmazokra történő általánosításának kimondása
• Ramsey-tétel egy alkalmazása