Informatika1-2012/Gyakorlat6

A MathWikiből
A lap korábbi változatát látod, amilyen Rpalovics (vitalap | szerkesztései) 2012. október 8., 20:59-kor történt szerkesztése után volt.

Tartalomjegyzék

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
  • szomszédsági mátrix vs listás ábrázolás

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

Gráfok

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.

Mélységi keresés

  • Implementáld rekurzív algoritmussal a mélységi keresést.

http://en.wikipedia.org/wiki/Depth-first_search

Szélességi keresés

  • Implementáld rekurzív algoritmussal a szélességi keresést.

http://en.wikipedia.org/wiki/Breadth-first_search

Dijkstra algoritmus

Floyd-Warshall algoritmus

Egyéb Rekurzív algoritmusok

A gráfok lehetnek nagyon nagyok!

Személyes eszközök