Informatika1-2012/Gyakorlat6

A MathWikiből
(Változatok közti eltérés)
15. sor: 15. sor:
 
===Gráfok Sage-ben===
 
===Gráfok Sage-ben===
  
* szótáas megadás <code> d = {0: [1,4,5], 1: [2,6], 2: [3,7], 3: [4,8], 4: [9], 5: [7, 8], 6: [8,9], 7: [9]} </code>
+
* szótáras megadás <code> d = {0: [1,4,5], 1: [2,6], 2: [3,7], 3: [4,8], 4: [9], 5: [7, 8], 6: [8,9], 7: [9]} </code>
 
* mátrixos megadás  <code>M = Matrix ([ [0, 1, 1], [1, 0, 1], [1, 1, 0] ]) </code>
 
* mátrixos megadás  <code>M = Matrix ([ [0, 1, 1], [1, 0, 1], [1, 1, 0] ]) </code>
 
* <code>Graph, DiGraph</code>
 
* <code>Graph, DiGraph</code>

A lap 2012. október 8., 18:39-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)
  • 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)<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.
Személyes eszközök