Informatika1-2012/Gyakorlat6
A MathWikiből
(Változatok közti eltérés)
(→Feladatok) |
|||
(egy szerkesztő 16 közbeeső változata nincs mutatva) | |||
1. sor: | 1. sor: | ||
− | + | ==Bevezetés== | |
− | + | ||
− | + | ||
* Csúcsok, és közöttük futó élek | * Csúcsok, és közöttük futó élek | ||
* Irányított vs. irányítatlan gráfok | * Irányított vs. irányítatlan gráfok | ||
11. sor: | 9. sor: | ||
* Klikk, teljes gráf | * Klikk, teljes gráf | ||
* Összefüggő 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 <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> | ||
* <code>Graph, DiGraph</code> | * <code>Graph, DiGraph</code> | ||
* gyors layout: <code> G.show() </code> | * gyors layout: <code> G.show() </code> | ||
21. sor: | 20. sor: | ||
* élek : <code>G.edges()</code> | * élek : <code>G.edges()</code> | ||
* szomszédok: <code>G.neighbors(5)</code> | * szomszédok: <code>G.neighbors(5)</code> | ||
+ | * utak: <code>G.distance(2,5),G.diameter()</code> | ||
* Nagyon sok beépített függvény van, most ezekkel nem foglalkozunk, mert a célunk saját algoritmusok írása. | * Nagyon sok beépített függvény van, most ezekkel nem foglalkozunk, mert a célunk saját algoritmusok írása. | ||
− | + | ==Feladatok== | |
+ | |||
+ | [https://docs.google.com/document/d/1sn7MQl8hyO0ixGrzFWusmmqFbv1x_rwyDEP2PFUHpXA/edit?pli=1 Google doc] | ||
+ | |||
+ | ===Gráfok=== | ||
====Páros 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. | * Í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. | + | * 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. | ||
+ | ====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==== | ||
+ | * Implementáld a Dijkstra algoritmust | ||
+ | http://en.wikipedia.org/wiki/Dijkstra's_algorithm | ||
+ | ===Egyéb Rekurzív algoritmusok=== | ||
+ | * Elméleti, órán elhangzott anyag ismétlése, két egyszerű algoritmus kipróbálása. | ||
+ | * http://wiki.math.bme.hu/view/Informatika1-2012/Eloadas4 | ||
+ | === A gráfok lehetnek nagyon nagyok!=== |
A lap jelenlegi, 2012. október 9., 08:55-kori változata
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
- Implementáld a Dijkstra algoritmust
http://en.wikipedia.org/wiki/Dijkstra's_algorithm
Egyéb Rekurzív algoritmusok
- Elméleti, órán elhangzott anyag ismétlése, két egyszerű algoritmus kipróbálása.
- http://wiki.math.bme.hu/view/Informatika1-2012/Eloadas4