MMN101piG
Gráfelmélet informatikus MSc hallgatók számára
2019 Ősz
A gyakorlat a MMN101piE Gráfelmélet előadáshoz tartozó gyakorlat.
Az ott elhangzó fogalmak, algoritmusok, tételek feladatokon keresztül történő
gyakorlásából áll.
A félév során két zh-n kell beszámolni tudásunkról. Az itt szerzett
pontszámok (0-50+50) alapján lesz az osztályozás. Az órai pozitív aktivitás
és szorgalmi feladatok megoldásával plusz pontok szerezhetők.
A szorgalmi feladatok megoldásait írásban kell beadni a következő gyakorlat
kezdetéig. Ez történhet fizikailag a gyakorlat elején, vagy email-en.
Előre láthatólag a pontok (0-100-as skála) jegyre váltása
a következőképpen történik:
- 1:
< =50 összpont
- 2:
50 < összpont < = 60
- 3:
60 < összpont < = 70
- 4:
70 < összpont < = 85
- 5:
85 < összpont
Gyakorlatok
Szeptember 4.:
- Gráfelméleti alapfogalmak
[
Gyakorlat anyaga: A félév menetének megbeszélése,
5. feladat, 3.(a) feladat.
Beadható szorgalmi feladat: Legyen G egy tetszőleges gráf és p egy páratlan fokú csúcsa.
p-ből kezdjünk el sétálni úgy, hogy már bejárt élen ne haladjunk át újra (azaz egy vonalat
járjunk be). Sétánk szükségszerűen elakad (egy csúcsba jutunk, ahonnan nem tudunk a szabályok
szerint továbblépni). Igazoljuk, hogy
(a) az elakadás egy páratlan fokú csúcsban történik
(b) az elakadás pontja nem lehet p.
]
Szeptember 11.:
- Gráfelméleti alapfogalmak 2: Fák
[
Gyakorlat anyaga: Fokszámsorozatok, fák, feszítőfák.
Beadható szorgalmi feladat:
Nézzük a 3,3,3,3,3,5,6,6,6,6,6 számsorozatot.
Realizálható-e ez
(a) hurokélmentes, párhuzamos élek nélküli (a két feltétel együtt: egyszerű) összefüggő gráffal?
(b)* páros gráffal?
]
Szeptember 18.:
Szeptember 25.:
- A két csoport közös gyakorlata Csaba Béla vezetésével.
Október 2.:
- Folyamok
[H.f.: A feladatsor 2. feladatátnak befejezése. Megoldásunk egy ábra a
kiinduló folyammal, rá vonatkozó javító úttal. Egy következő ábra a
javított folyammal és egy rá vonatkozó javító úttal. Újabb ábra, ...
addig amíg azt állítjuk, hogy az aktuális folyam optimális. Ezt
indokoljuk is meg. A feladat megoldása az előadás anyagának átnézését is igényli.]
Október 9.:
- A két csoport közös gyakorlata Hajnal Péter vezetésével:
Folyamok, tesztelés, konzultáció
Október 16.:
- I. zárthelyi dolgozat tematika
- Fokszámsorozatok, realizációk egyszerű, összefüggő, páros
gráfokkal
- Fák, Prüfer-kódok, dekódolás
- Összefüggőség, komponensek, komponensek száma
- Folyamok (gyakorló feladatok)
- A zh négy feladatból fog állni. A mellékelt
minta zh sok feladata csak segítség a hallgatóknak: pdf file
Október 23.:
Október 30.:
November 6.:
November 13.:
- Párosítások II
[Hf.: Egy sakktábla két átellenes sarokmezője letört. Lefedhetők-e
a maradék mezők 31 dominóval? Egy dominó két szomszédos mezőt fedhet le.]
November 20.:
November 27.:
- II. zárthelyi dolgozat tematika
- Folyamok alkalmazásai
- Párosítások: Páros és általános gráfok
- Lefogások
- A zh négy feladatból fog állni. A mellékelt
minta zh sok feladata csak segítség a hallgatóknak: pdf file
December 4.:
- II. zárthelyi dolgozat megbeszélése, a félévi jegyek kialakítása
Ha az előadással, gyakorlattal kapcsolatban bármilyen
kérdés, megjegyzés, vélemény stb. felmerül, akkor
azokat az hajnal@math.u-szeged.hu
email címen érdeklõdve
várom.