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(n²).
(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 X_i városokból áll, a másik az Y_j-kből. Élet húzunk X_i és Y_j közé, ha el lehet jutni Y_j-ből X_i-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.