Gráfelmélet
Programtervezõ matematikus, IV.-V. évfolyam,
Közgazdász programozó szak, V. évfolyam
Tematika, 1999.~õsz
- Gráfelméleti alapfogalmak:
egyszerû gráf, gráf, irányított gráf;
részgráf, feszített részgráf;
séta, vonal, út, kör egy G gráfban;
fokszám.
- Gráfok összefüggõsége:
összefüggõség, komponensek;
feszítõfák;
minimális összefüggõ gráfok,
fák ekvivalens definíciói;
fák növekedése, fák éleinek száma.
- Kétszeresen élösszefüggõ gráfok:
elvágó élek;
kétszeresen élösszefüggõ gráfok
ekvivalens definíciói;
kétszeresen élösszefüggõ komponensek;
kétszeresen élösszefüggõ gráfok fülfelbontása.
- Kétszeresen összefüggõ gráfok:
(csak kimondani az elhangzottakat!)
elvágó pontok;
kétszeresen összefüggõ gráfok
ekvivalens definíciói;
kétszeresen összefüggõ komponensek;
kétszeresen összefüggõ gráfok fülfelbontása.
- Magasabb fokú összefüggõség:
k-szorosan összefüggõ és
élösszefüggõ gráfok ekvivalens
definíciói és kapcsolatuk Menger-tételeivel.
Menger tételeinek kimondása és
az édiszjunkt utakra vonatkozó változat
bizonyítása.
- Párosítások:
párosítások fogalma;
páros gráfokra vonatkozó párosítási tételek
(Kõnig tételei, Hall-tétel, Frobenius-tétel);
javító utak;
magyar módszer és helyessége;
Kõnig-tétel bizonyítása;
Tutte-akadály, Tutte-tétel;
Berge-formula kimondása és a nyilvánvaló irány
azonosítása és indoklása.
- Vonalak, körök:
Euler-vonal, zárt Euler-vonal;
Euler-tétel;
Hamilton-kör, Hamilton-út;
akadályok Hamilton-kör létezésére;
Dirac-tétel.
- Független ponthalmazok:
független ponthalmazok, lefogó ponthalmazok,
klikkek és kapcsolatuk;
mohó algoritmus független ponthalmaz keresésére,
Turán-tétel.
- Gráfok színezései:
gráfok kromatikus száma;
kis kromatikus számú gráfok,
2-színezhetõ gráfok jellemzése;
gráfok kromatikus számának
és maximális fokszámának
kapcsolata, Brooks-tétel kimondása
és háromszorosan összefüggõ
gráf esetén a tétel bizonyítása;
gráfok kromatikus számának és a maximális
méretû klikk nagyságának kapcsolata,
példa háromszög nélküli nagy
kromatikus számú gráfra.
- Gráfelméleti problémák:
redukciók az elõadáson elhangzott példák alapján.
- Extremális gráfelmélet:
Turán tételének átfogalmazásai, Turán-gráfok és
a Turán-tétel erósebb változatának kimondása;
C4-et nem tartalmazó gráfok élszáma;
extremális gráfelmélet egy alkalmazása.
- Ramsey-elmélet:
Ramsey-számok, Ramsey-tétele;
Ramsey-tétel általánosításai;
Ramsey-számok alsó becslése;
Ramsey-tételének egy alkalmazása.
- Síkgráfok:
gráfok síkra rajzolása, íkgráfok;
síkra rajzolt gráfok, tartományok, Euler-formula;
topológikus részgráf, minor, Kuratowski-tétel kimondása;
síkgráfok színezése, ötszín tétel.
* * *
\noindent
- Gráfok kódolása:
izolált pont létezésének eldöntése,
ha gráfunk szomszédsági mátrixával
adott;
összefüggõség eldöntése,
ha gráfunk szomszédsági mátrixával
adott, mátrixhatványozás.
- Kruskal-algoritmus:
a minimális feszítõfa keresének általánosítása,
az általanosított kérdésre
vonatkozó mohó algoritmus;
három példa;
a mohó algoritmus helyességére vonatkozó tétel;
a három példa analízise.
- Folyamok:
hálozatok, folyamok, vágások, javító utak;
mimimális vágás maximális folyam tétel;
folyam algoritmusok.
- Párosítások:
Edmonds-algoritmus.
- Vonalak, körök:
kínai postás probléma és megoldása;
utazó ügynök probléma;
approximációs algoritmusok, az utazó
ügynök problemára vonatkozó algortmusok.
- Bonyolultságelmélet:
Turing-gépek, NP és P nyelvosztályok.
- Véletlen számokat használó algoritmusok:
Schwartz-lemma;
teljes párosítás létezésének
tesztelése páros gráfokban véletlen algoritmussal.