Lemon speci

Gyakorlatok anyagai

gyakorlat

• Lemon attekintes
• Graf felepitese, alapmuveletei

gyakorlat

• Grafok megjelenitese postscriptben
• Ketszinezes bejarassal

gyakorlat

• Komponensekre bontas bejarassal

gyakorlat

• Graf implementacio n -> 3n + 1 | n / 2 problemara

gyakorlat

• Hanyszorosan osszefuggo egy graf, lassu implementacio folyamokkal

gyakorlat

• Labirintusban legrovidebb utak keresese specialis mezokkel

gyakorlat

• Legrovidebb utak csucs koltsegekkel

gyakorlat

• Kep kiszinezese maximum hat szinnel

gyakorlat

• Minimalis feszitofa megkeresese kotelezo elek eseten

gyakorlat

• Utazo ugynok problemakra heurisztikak

gyakorlat

• Hamilton kor keszitese racs es hiperkocka grafban

Fontos linkek

• Lemon honlap

Gyakorlo feladatok

 
1. Adott egy (iranyitott vagy iranyitatlan) graf, a csucsain nemnegativ szamok. Egy ut "pont-hosszan" az ut pontjaira irt szamok osszeget ertjuk. Feladat: keressuk meg ket adott pont kozott a pont-legrovidebb utat!
 
2. Adott egy (iranyitott vagy iranyitatlan) graf, az elein nemnegativ szamok. Egy ut "szelessegen" az ut eleire irt szamok minimumat ertjuk. Feladat: keressuk meg ket adott pont kozott a legszelesebb utat!
 
3. Adott egy (iranyitott vagy iranyitatlan) graf, a csucsain nemnegativ szamok. Egy ut "pont-szelessegen" az ut pontjaira irt szamok minimumat ertjuk. Feladat: keressuk meg ket adott pont kozott a pont-legszelesebb utat!
 
4. Adott egy iranyitatlan graf es s pont. Keressuk meg a grafnak egy olyan feszitofajat, ami a leheto legkevesebb s-bol indulo elet tartalmaz.
 
5. Adott egy tetszoleges iranyitatlan graf. Feladat: iranyitsuk meg a graf eleit ugy, hogy a kapott iranyitott grafban minden pon befoka es a kifoka legfeljebb eggyel terjen el! (Megj: Ha a graf veletlenul Euler (osszefuggo+minden pont foka paros), akkor egy Euler-seta menten megiranyitva az eleket egy jo iranyitast kapunk, hiszen ekkor befok=kifok lesz minden csucsra.)
 
6. Allapitsuk meg egy (iranyitatlan) grafrol minel gyorsabban, hogy hanyszorosan osszefuggo! Mas szoval: keressunk egy (iranyitatlan) grafban egy minimalis elszamu vagast.

Elerhetoseg