Megoldások az ötödik gyakorlathoz 1. A teljes feladatsorban szerepel a megoldás a Gráfalgoritmusok 14. feladatnál. 2. A jegyzetben leírt módon járjunk el. 3. A teljes feladatsorban szerepel a megoldás a Gráfalgoritmusok 2. feladatnál. 4. Ha G-nek lenne artikulációs pontja, akkor lenne legalább két olyan részgráf G-ben, melyek között csak az artikulációs ponton vezet út. Ebből az artikulációs pontból indított mélységi bejárás először bejárja az egyik gráfot, majd visszatér az artikulációs pontba és elindul a másik gráf felé, de akkor ez már nem irányított út. 5.A teljes feladatsorban szerepel a megoldás a Gráfalgoritmusok 23. feladatnál. 6. A teljes feladatsorban szerepel a megoldás a Gráfalgoritmusok 5. feladatnál. 7. A teljes feladatsorban szerepel a megoldás a Gráfalgoritmusok 19. feladatnál. 8. (a) A problémát fogalmazzuk át gráfok nyelvére: a gráf pontjai a formátumok, két pont között vezet él, ha van konvertáló program, az él súlya a futási idő. Keresni kell legrövidebb utat a mi formátumunkat jelölő pontból minden más pontba, az ezen utakra eső szoftvereket kell megvenni. Ezt pl. Dijkstra algoritmusa megteszi nekünk, a módosított változat, ahol az utakat is követjük. Ez O(n2). (b) A gráf hasonló, mint az előbb, csak most az élek súlya az ár. Minimális feszítőfát kell keresni, erre is van több módszer, pl. Prim, Kruskal. 9. Egy páros gráfot konstruálunk: az egyik ponthalmaz az Xi városokból áll, a másik az Yj-kből. Élet húzunk Xi és Yj közé, ha el lehet jutni Yj-ből Xi-be 2 óra alatt. Ebben a páros gráfban kell maximális párosítást találni. Ez O((n+m)e), ahol e az élek száma a páros gráfban. 10. A teljes feladatsorban szerepel a megoldás a Gráfalgoritmusok 40. feladatnál.