Informatika1-2012/Gyakorlat6

A MathWikiből
(Változatok közti eltérés)
32. sor: 32. sor:
 
* Segítség: <code> L.count(1) </code> megadja, hogy az "1" elem hányszor szerepel egy listában. Ez nagyon áttételes ötlet, nem innen kell elindulni.
 
* Segítség: <code> L.count(1) </code> megadja, hogy az "1" elem hányszor szerepel egy listában. Ez nagyon áttételes ötlet, nem innen kell elindulni.
 
* Sokféle megoldás van! Lehet szabadon gondolkodni, ötletelni.
 
* Sokféle megoldás van! Lehet szabadon gondolkodni, ötletelni.
 +
 +
====Floyd-Warshall algoritmus====
 +
 +
====Dijkstra algoritmus====
 +
 +
====Rekurzív algoritmusok====
 +
 +
* Elméleti, órán elhangzott anyag ismétlése

A lap 2012. október 8., 19:00-kori változata

Tartalomjegyzék

Gráfok

Bevezetés

  • Csúcsok, és közöttük futó élek
  • Irányított vs. irányítatlan gráfok
  • Súlyozott vs. súlyozatlan gráfok
  • Szomszédsági mátrix, "Laplace" mátrix
  • Út, legrövidebb út
  • Átmérő
  • Páros gráfok
  • Klikk, teljes gráf
  • Összefüggő gráf
  • ...

Gráfok Sage-ben

  • szótáras megadás d = {0: [1,4,5], 1: [2,6], 2: [3,7], 3: [4,8], 4: [9], 5: [7, 8], 6: [8,9], 7: [9]}
  • mátrixos megadás M = Matrix ([ [0, 1, 1], [1, 0, 1], [1, 1, 0] ])
  • Graph, DiGraph
  • gyors layout: G.show()
  • fokszám: G.degree(), G.degree(5)
  • élek : G.edges()
  • szomszédok: G.neighbors(5)
  • utak: G.distance(2,5),G.diameter()
  • Nagyon sok beépített függvény van, most ezekkel nem foglalkozunk, mert a célunk saját algoritmusok írása.

Feladatok

Páros gráfok

  • Írj bipartiteGraph(G) függvényt, mely egy bemenő irányított gráfról eldönti, hogy az páros-e.
  • Segítség: L.count(1) megadja, hogy az "1" elem hányszor szerepel egy listában. Ez nagyon áttételes ötlet, nem innen kell elindulni.
  • Sokféle megoldás van! Lehet szabadon gondolkodni, ötletelni.

Floyd-Warshall algoritmus

Dijkstra algoritmus

Rekurzív algoritmusok

  • Elméleti, órán elhangzott anyag ismétlése
Személyes eszközök