A+ | A- | Ø
 
  • English
 
 
2014. október 31. péntek 23:14
A Bolyai Intézet által oktatott tárgyak

Vissza

A tárgy kódja és neveMBX785E Gráfelmélet
Meghirdető tanszék(csoport)Halmazelmélet és Matematikai Logika Tanszék 
Felelős oktatóDr. Hajnal Péter 
Kredit
Heti óraszám
Típusaelőadás 
Számonkéréskollokvium 
Teljesíthetőség feltételea párhuzamos feltétel teljesítése 
Párhuzamos feltételMBX785G 
ElőfeltételMBNX111E 
Helyettesítő tárgyakMx785e 
Periódusőszi 
Javasolt félév, kötelezőségprogramtervező szakon kötelező: 7. félév 
A foglalkozásokon való részvétel követelményei és a távolmaradás pótlásának lehetőségeNincs követelmény.  
Az igazolás módja a foglalkozásokon és a vizsgán való távollét eseténVizsgáról való hiányzás esetén 5 napon belül jelezni kell, ha orvosi okok miatt történik és erről igazolást kell hozni. Más esetben elégtelen vizsga.  
A félévközi ellenőrzések (beszámolók, zárthelyik) száma, témaköre és időpontja, pótlásuk és javításuk lehetőségeNincs.  
A félév teljesítésének követelményeiLegalább elégséges jegy a vizsgán.  
Az osztályzat kialakításának módjaÍrásbeli dolgozat. 4-5, az egész félév anyagát átölelő kérdéssel. Mintavizsga elérhető lesz a vizsgaidőszak előtt. A vizsgázónak az alapfogalmakkal tisztában kell lenni, ezekben való hiányok elégtelen osztályzathoz vezetnek.  


Tematika

Gráfok és kódolásuk. Összefüggőség, minimális költségű feszítőfa. Vonalak, kínai portás probléma, Hamilton-körök, utazó ügynök probléma. Párosítások, magyar módszer, Edmonds-algoritmus. Színezések, színezési algoritmusok. Független ponthalmazok, klikkek, Turán-tétel, Ramsey-számok. Gráfproblémák redukciói.


Ajánlott irodalom

  1. Hajnal Péter: Gráfelmélet, Polygon jegyzettár, Szeged, 1997.