Gráfelmélet előadás + gyakorlat (levelező), 2022/2023 ősz

KÖVETELMÉNYEK

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.

ÓRAI FELADATSOROK

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

SEGÉDANYAGOK

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

0. Ismétlés
Jegyzet: Hajnal Péter: KOMBINATORIKAI FOGALOMTÁR
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 (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.
8. Euler-vonal, kínai postás problémája, utazóügynök probléma
Ismétlés: Séta, vonal, út.
Elmélet: Nyílt és zárt Euler-vonal definíciója. Euler-tétel. Kínai postás problémája. Az utazóügynök probléma.
Típusfeladat: Egy konkrét gráfról eldönteni, hogy van-e benne nyílt, illetve zárt Euler-vonal. Egy konkrét kis élsúlyozott gráfra megoldani a kínai postás problémáját.

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

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

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

Főoldal