Gráfelmélet előadás (levelező), 2019/2020 ősz

KÖVETELMÉNYEK

Az előadás teljesítésének előfeltétele a teljesített gyakorlat (a gyakorlat követelményrendszere itt olvasható).

Az előadás anyaga egy 100 pontos írásbeli vizsgán lesz számon kérve a vizsgaidőszakban (a Neptunban meghirdetett időpontokban), mely a tematikából válogatott elméleti kérdéseket, illetve a fogalmak és tételek megértését tesztelő egyszerű feladatokat tartalmaz majd. A vizsga sikeres teljesítésének alapvető feltétele az alapfogalmak és legegyszerűbb összefüggések pontos ismerete, ezek hiányában a vizsga automatikusan elégtelen.

A félév folyamán pluszpontokat is lehet szerezni (legfeljebb 10-et) az előadás alatt tett érdemi hozzászólással/hibajelzéssel. A pluszpontok hozzáadódnak a vizsgán szerzett pontszámhoz.

Ponthatárok:
  0 – 50:   elégtelen
51 – 60:   elégséges
61 – 70:   közepes
71 – 85:   jó
86 – 100: jeles

SEGÉDANYAGOK

1. MINTAVIZSGA, 2. MINTAVIZSGA
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)

TEMATIKA

A zölddel jelölt részeket nem kérdezem vizsgán, ezekkel pluszpontot lehet szerezni.

1. Fokszámsorozatok realizációja
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 összeszámlálása
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: 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: 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 (Második kombinatorikus bizonyítás Cayley formulájára (Prüfer), 6. Tétel)
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.
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
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.
8. Euler-vonal
Ismétlés: Séta, vonal, út.
Elmélet: Nyílt és zárt Euler-vonal definíciója. Euler-tétel.
Típusfeladat: Egy konkrét gráfról eldönteni, hogy van-e benne nyílt, illetve zárt Euler-vonal.
9. Kínai postás problémája
Elmélet: Kínai postás problémája.
Típusfeladat: Annak eldöntése, hogy egy konkrét terv (a gráf éleire írt számok azt jelzik, hogy hányszor akarunk áthaladni az élen) megvalósítható-e zárt sétával.

GRÁFELMÉLETI FOGALMAK KÉPEKBEN

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).

AJÁNLOTT IRODALOM

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ó)
Reinhard Diestel: Graph Theory (Springer-Verlag, interneten is olvasható)
Friedl Katalin, Recski András, Simonyi Gábor: Gráfelméleti feladatok (Typotex)

HASZNOS LINKEK

A gyakorlat honlapja

Főoldal