Algoritmuselmélet gyakorlat (5)
1. A 6 pontú G gráf csúcsait jelölje x,y,z,u,v,w. A gráf egy mélységi bejárásánál a mélységi, ill. a befejezési számok a következők: x: 1,6; y: 2,4; z: 6,5; u: 3,3; v: 4,1; w: 5,2. Adjuk meg a bejáráshoz tartozó mélységi feszítőfa éleit. Rekonstruálható-e G az előző számok ismeretében? 2. G irányítatlan gráf a következő éllistával (zárójelben a költségek, az élek mindkét végpontjukból fel vannak sorolva): a:b(2),c(3); b:a(2),d(2); c:a(3),d(1); d:b(2),c(1),e(2),f(4); e:d(2),f(1),g(2); f:d(4),e(1),g(2),h(1); g:e(2),f(2),h(3); h:f(1),g(3); Keressünk G-ben (a) Prim algoritmusával minimális költségű feszítőfát! (b) Kruskal algoritmusával minimális költségű feszítőfát! (c) a-ból kiinduló mélységi feszítőfát! (d) a-ból kiinduló szélességi feszítőfát! (e) Határozzuk meg G artikulációs pontjait! 3. Adjuk meg az összes olyan minimális élszámú irányított gráfot (élsúlyokkal együtt), amely(ek)re az alábbi táblázat a Dijkstra-algoritmusban szereplő D[ ] tömb változásait mutathatja. Adja meg a legrövidebb utakat tartalmazó P[ ] tömb állapotait is.
4. Tegyük fel, hogy G egy összefüggő irányítatlan gráf, melynek minden mélységi feszítőfája egy egyszerű irányított út. (a) Igazoljuk, hogy nincs G-nek artikulációs pontja (olyan csúcsa, melyet az összes belőle induló éllel együtt elhagyva G-ből, a kapott gráf már nem lesz összefüggő)! (b) Mutassuk meg, hogy G nem szükségképpen teljes gráf! 5. Adott éllistával egy n pontú, e élű G összefüggő irányítatlan gráf. Adjunk O(e) uniform költségű algoritmust olyan ![]() ![]() ![]() 6. Legyen adott egy ![]() 7. Éllistával adott a súlyozott élű G=(V,E) gráf. Tegyük fel, hogy az élek súlyai az 1,2,3 számok közül valók. Javasoljunk O(n+e) uniform költségű algoritmust az ![]() ![]() 8. A szoftverpiacon n féle grafikus formátum közötti oda-vissza konverzióra használatos programok kaphatók: az i-edik és a j-edik között oda-vissza fordító program ára aij, futási ideje pedig tij (ha létezik). (a) Javasoljunk módszert annak megtervezésére, hogy minden egyes formátumról a saját grafikus terminálunk által megértett formátumra a lehető leggyorsabban konvertáljunk! (Az ár nem számít.) (b) Javasoljunk módszert annak eldöntésére, hogy mely programokat vásároljuk meg, ha azt szeretnénk a lehető legolcsóbban megoldani, hogy a megvett programok segítségével bármelyik formátumról bármelyik más formátumra képesek legyünk konvertálni. (Itt a futási idő nem számít). 9. Az ország n különböző ![]() ![]() |