Informatika1-2012/Gyakorlat6
A MathWikiből
(Változatok közti eltérés)
30. sor: | 30. sor: | ||
* Í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: <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. |
A lap 2012. október 8., 19:56-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.