Gráfelmélet súlyozott tematika

2009, ősz

Az alábbi szabályok nem kőbe vésett szabályok, de jó szem előtt tartani a vizsgánál készülésnél. Az alapok utáni listám nem sorolja be a teljes tematikát, de egy érzést ad milyen mélységű tudásra milyen jegyet lehet remélni.

Alapfogalmak

  • Egyszerű gráf, gráf fogalma
  • Fokszám fogalma
  • Séta
  • Elérhetőség reláció
  • Csúcsok elhagyása gráfokból, feszített részgráf
  • Gráfok komponensei
  • Összefüggő gráf
  • Vonal, Euler-vonal fogalma
  • Élek elhagyása gráfokból, feszítő részgráf
  • Út, kör
  • Fa
  • Hamilton-kör, Hamilton-út
  • Gráfok színezése, kromatikus szám
  • Klikk, omega paraméter
  • Párosítások, nü paraméter
  • Lefogó ponthalmazok, tau paraméter
  • Javító út
  • Kőnig-akadály
  • Tutte-akadály fogalma
  • Független ponthalmaz, alfa paraméter
  • Turán-gráfok

    Alapalgoritmusok

  • Vonal növelései
  • Minimális, az összes pontot tartalmazó, összefüggő részgráf keresése összefüggő gráfokban, feszítőfa
  • Minimális költségű feszítőfa keresése, Kruskal-algoritmus
  • Mohó algoritmus maximális költségű megengedett halmaz keresésére;
  • Út mohó növelése, csavarása
  • Mohó színezési algoritmus
  • Párosítások mohó növelése
  • Párosítások javító utas növelése
  • Mohó algoritmus független ponthalmaz keresésére
  • Módosított mohó algoritmus független ponthalmaz keresésére

    A fentieket tudni kell. Ezekben tapasztalt hiány, elégtelen vizsgát jelent. Sajnos csak ezek tudása viszont nem biztos, hogy elégséges jegyet eredményez. Sokan azt hiszik, hogy ezeket megtanulták, de írásbeli visszaadásuk hiányokat, értelmetlenségeket, elírásokat tartalmaz. A fentiekre akkor építhet valaki egy átmenő vizsgát, ha többet is lát az anyagból (azt esetleg nem feltétlen teljes mélységben) és ideje volt "megemészteni a fogalmakat".

    Alapproblémák (mi az input, mi az output)

  • Euler-vonal keresés
  • Hamilton-kör keresés sűrű gráfokban
  • Kínai postás problémája
  • Utazó ügynök problémája

    Alapösszefüggések

    Ezek indoklása egy-két mondatban elmondhatók. Sokszor egy mélyebb összefüggés úgy mond triviális iránya.

  • Fokszámokra vonatkozó egyszerű állítások (indoklás)
  • Elérhetőség reláció ekvivalenciareláció volta (indoklás)
  • Euler-tétel kimondása
  • Fák ekvivalens definíciói (kimondás)
  • Két-színezhető gráfok jellemzése (kimondás)
  • Mohó színezési algoritmus outputjának mérete és a maximális fokszám viszonya (indoklás)
  • Kromatikus szám és az omega paraméter viszonya (indoklás)
  • nü és tau paraméterek viszonya (indoklás)
  • Javító út létezése mit mond a párosításról (indoklás)
  • Mit akadályoz meg egy Kőnig-akadály (indoklás)
  • Mit mond egy Kőnig-akadály a legnagyobb párosítás méretéről (indoklás)
  • Mit akadályoz meg egy Tutte-akadály (indoklás)
  • Mit mond egy Tutte-akadály a legnagyobb párosítás méretéről (indoklás)
  • Mohó algoritmus (független ponthalmaz keresésére) outputjának mérete és a maximális fokszám viszonya (indoklás)
  • Turán-gráfok és n pontú, k elemű klikk nélküli gráfok élszáma közti viszony (kimondás)
  • Ramsey-számok (definíció)

    A fentiek alapos tudása biztos közepes jegy. Átmenő jegy megszerzéséhez is ajánlott ezeknek az összefüggéseknek a megértése.

    A többi része az anyagnak négyes, ötös érdemjegy megszerzéséhez szolgálhatnak. Például:

  • Kínai postás algoritmusa
  • Magyar módszer analízise
  • Ramsey-tétel bizonyítása
  • Öt-szín-tétel bizonyítása ...