Gyakorlat: A félév során házi feladatokat tűzök ki CooSpace-en, melyek megoldását az ott megadott határidőig kell a rendszerbe feltölteni.
A félév folyamán pluszontokat is lehet szerezni órai munkával, illetve szorgalmi feladatok megoldásával.
Az így kialakult összpontszám határozza meg a gyakorlat érdemjegyét az alábbiak szerint:
0% – 50%: elégtelen
51% – 62%: elégséges
63% – 75%: közepes
76% – 87%: jó
88% – 100%: jeles
Előadás: (Az előadás teljesítésének előfeltétele a teljesített gyakorlat.) A hallgatóknak a tananyaghoz kapcsolódó számítógépes projektmunkát kell készíteniük a vizsgaidőszak végéig, melynek témáját az oktató a hallgatóval egyeztetve jelöli ki a szorgalmi időszakban. A projektmunka kiváltható írásbeli vizsgával a vizsgaidőszakban a félév anyagából. A gyakorlatnál látott ponthatárokat alkalmazom az előadásnál is.
1. Fokszámsorozatok realizációja
2. Fák összeszámlálása
3. Folyamok
4. Többszörös összefüggőség
5. Párosítások (páros gráfokban)
6. Színezések
2009/2010 tanév elektronikus jegyzete (Hajnal Péter honlapján)
2010/2011 tanév elektronikus jegyzete (Hajnal Péter honlapján)
Euler-tétel és bizonyítása
Dirac-tétel és bizonyítása
Síkgráfok
Ford—Fulkerson-algoritmus (példa)
Párosítási algoritmusok
Fák ekvivalens definíciói (ismétlés)
0. Ismétlés
Jegyzet: Hajnal Péter: KOMBINATORIKAI FOGALOMTÁR
1. Fokszámsorozatok realizációja (prezentáció)
Ismétlés: Gráf, egyszerű gráf, fokszám, fokszámsorozat definíciója.
Elmélet: Számsorozatok realizációja tetszőleges gráffal, hurokélmentes gráffal (csak kimondani), illetve egyszerű gráffal. Havel—Hakimi-tétel és -algoritmus.
Erdős-Gallai-tétel kimondása.
Típusfeladatok: Havel—Hakimi-algoritmus alkalmazása konkrét sorozatra.
Jegyzet: Hajnal Péter: Fokszámsorozatok (1-3. oldal)
2. Feszítőfák
Ismétlés: Összefüggőség, fák. Részgráf, feszítő és feszített részgráfok. Feszítőfa.
Elmélet: Minimális költségű feszítőfa, Kruskal-algoritmus. Cayley-tétel a teljes gráf feszítőfáinak számára. Címkézett fák. Prüfer-kód (a kódolás és az inverze).
Típusfeladatok: Minimális költségű feszítőfa megtalálása Kruskal-algoritmussal. Egy címkézett fa Prüfer-kódjának meghatározása. Egy adott Prüfer-kódú fa rekonstrukciója.
Jegyzet: Hajnal Péter: Cayley és Kirchhoff formulája (lásd 'Második kombinatorikus bizonyítás Cayley formulájára (Prüfer)')
3. Folyamok
Elmélet: Hálózat, (megengedett) folyam, folyamérték definíciója. Vágás és kapacitása. Maximális folyam - minimális vágás tétel. Javító utak,
javítóút-kezdemények. Folyam javítása javító út mentén. Javító út létezésének és a folyam maximalitásának kapcsolata.
Ford—Fulkerson-algoritmus. Egész élkapacitású hálózatok esetén létezik egész értékű optimális folyam.
Típusfeladatok: Javító út keresés egy adott folyamra nézve; maximális értékű folyam konstruálása Ford—Fulkerson-algoritmussal.
4. Többszörös összefüggőség
Elmélet: k-szoros élösszefüggőség és összefüggőség definíciója, és ezek kapcsolata. Menger tételei.
5. Párosítások
Ismétlés: Páros gráfok definíciója.
Elmélet: Párosítás, teljes párosítás, és a ν(G) paraméter definíciója. Párosítások páros gráfokban: Kőnig-akadály, Kőnig—Hall-tétel, Kőnig—Frobenius-tétel.
Teljes párosítás létezése reguláris páros gráfokban. Javító utak. Magyar módszer (+ egy szemléltető példa).
Tutte-akadály (+ mit akadályoz meg, és miért), Tutte-tétel kimondása.
Kiegészítés (nem vizsgaanyag): Edmonds-algoritmus.
Típusfeladatok: Kőnig-akadály / javítóút-keresés páros gráfban magyar módszerrel, konkrét gráf ν(G) paraméterének meghatározása, Tutte-akadály keresése.
Jegyzetek: Párosítások. Párosítási algoritmusok.
6. Élszínezések
Elmélet: Jó élszínezés, élkromatikus szám definíciója. Vizing-tétel; Shannon-tétel; páros gráfok élkromatikus száma (ezek bizonyítás nélkül).
Típusfeladat: Egy konkrét gráf élkromatikus számának meghatározása.
7. Csúcsszínezések, síkgráfok
Elmélet: Jó (csúcs)színezés, kromatikus szám definíciója. Klikkek. Az ω(G) paraméter és kapcsolata a kromatikus számmal.
Mohó színezési algoritmus. Kromatikus szám felső becslése a maximális fokszám segítségével. Brooks-tétel (bizonyítás nélkül).
Páros gráfok és jellemzésük (a nehezebb irány bizonyítása nélkül).
Síkgráfok definíciója. Négyszín-tétel kimondása. A két alappélda nem síkgráfokra. Kuratowski-tétel (bizonyítás nélkül).
Típusfeladat: Egy konkrét gráf kromatikus számának meghatározása.
Jegyzetek: Csúcsszínezések. Síkgráfok.
Euler-vonal: #1 (zárt),
#2 (zárt),
#3 (nyílt),
#4 (nyílt).
Hamilton-út: #1, #2.
Hamilton-kör: #1, #2, #3.
Komponensek: #1 (gráf 4 komponenssel),
#2 (gráf 3 komponenssel),
#3 (gráf 3 komponenssel).
Fa: #1, #2, #3.
Feszítőfa: #1, #2.
Gyökeres fa lerajzolása: #1, #2 (gyökér: 'a').
Síkgráf duálisa: #1, #2, #3, #4.
A duális gráf az eredeti gráf lerajzolásától is függ: #1.
Jó (csúcs)színezés: #1, #2.
Térképszínezési probléma / négyszíntétel szemléltetése: #1, #2.
Párosítás: #1 (nem teljes), #2 (teljes),
#3 (páros gráf egy párosítása), #4 (páros gráf egy A-t lefedő párosítása),
#5 (páros gráf egy teljes párosítása).
Kőnig-akadály: #1, #2.
A képek többségét más oldalakról linkeltem (az URL-ből kiolvasható/megkereshető a forrás).
Csaba Béla, Hajnal Péter, Nagy V. Gábor: Graph theory for MSc students in computer science (ingyenesen letölthető jegyzet, 2019).
Hajnal Péter: Gráfelmélet, II. kiadás (Polygon Jegyzettár)
Lovász László: Kombinatorikai problémák és feladatok (Typotex, interneten is olvasható)
