Pomoc Oko Grafova
Dragi clanovi i posetioci foruma,
Mozda ce vam ova brojka zvucati neverovatno, ali Forum Matematicke gimnazije postoji vec vise 6 godina - od januara 2006. godine, ako zelimo da budemo precizni.
Sa vise od 1.000 clanova, 4.000 tema i 100.000 poruka predstavlja najvecu zajednicu orijentisanu ka Matematickoj gimnaziji i ucinio je nase srednjoskolske dane barem iole zanimljivijima. Ne samo da je bio mesto za visokointelektualne razgovore ucenika Matematicke gimnazije, vec i forum na koji smo dolazili da se druzimo sa ljudima iz cele Srbije, pa i regiona. Verujem da ne govorim samo u nase ime kada kazem da su ovde nastala mnoga poznanstva koja su se kasnije dalje razvijala u "pravom svetu".
Nazalost, ta idilicna vremena su sada iza nas. Tokom poslednjih nekoliko godina Internet u regionu je doziveo vrtoglav razvoj, i potreba za ovakvim forumima vise ne postoji. Pojavile su se socijalne mreze kao sto su Facebook i Twitter, i komunikacija je na mnogo visem nivou. Forum, iako pun korisnih informacija, vise ne sluzi svojoj prvobitnoj nameni.
Iz tog razloga, teska srca smo doneli odluku da Forum Matematicke gimnazije prestane sa radom. Od danas registracije na forumu nece biti moguce, ali ce sve poruke i dalje biti dostupne za pregled. Takodje, od prvog septembra forum vise nece biti dostupan na adresi mg-forum.net, ali ce se arhivi i dalje moci pristupiti preko adrese bozidarevic.com/mgforum . Takodje bismo zeleli da iskoristimo priliku i da uputimo sve bivse ucenike na Alumni Matematicke gimnazije - almagi.mg.edu.rs.
Hvala svima koji su ucestvovali u diskusijama i koji su pomogli da ovaj forum bude jedno prijatno mesto.
Administratorski tim MG Foruma
   |
| darkokg |
  Mar 6 2009, 05:20 PM
Post
#1
|
|
Group: Članovi Joined: 1-April 08 Member No.: 992 Status: Van MGa Ime i prezime: Darko Antonijevic  |
Potrebno je da ukoliko imam matricu povezanosti cvorova (0 ako nisu povezani i 1 ako jesu) pronadjem put koji ukoliko ne bi postojao, graf ne bi bio jedna celina vec bi se podelio na dva dela tako da je iz jednog nemoguce stici u drugi deo.
Ne morate kucati ceo kod, pretostavljam da je poprilicno dug, dajte mi samo ideju ili bar linkove ka nekoj literaturi koja se bavi ovom problematikom posto ja nisam mogao da pronadjem nista. Pomogli bi mi ukoliko mi neko odgovori do 20-21h veceras, posle... i nije toliko bitno jer mi zadatak treba za sutra..... EDIT: Da, znam da sam pogresio u naslovu, ali izgleda da ne moze da se izmeni sada..... lol This post has been edited by darkokg: Mar 6 2009, 05:23 PM |
   |
 
|
| maxydelanoche |
Mar 6 2009, 06:50 PM
Post
#2
|
 Group: Članovi Joined: 3-May 06 From: Zion Member No.: 61 Status: Van MGa |
Sigurna sam da ce ti primena nekog od ovih: http://en.wikipedia.org/wiki/List_of_algor...raph_algorithms algoritama pomoci
 -------------------- Mi znamo sta se desava sa ljudima koji zastanu nasred puta. Bivaju pregazeni.
Nista nije nemoguce. Za nemoguce je samo potrebno malo vise vremena. I'm doing the best I ever did, I'm doing the best that I can. www.viva-fizika.org |
|
|
|
| pyost |
Mar 6 2009, 06:55 PM
Post
#3
|
 Deus Ex Makina  Group: Administratori Joined: 25-January 06 From: Beograd Member No.: 2 Status: Bivši učenik MGa Škola/Razred: RAF |
Mozda da brojis na koliko nacina su koja dva cvora povezana? Ako izmedju neka dva cvora postoji samo 1 put, onda je to trazeni put... Valjda
 -------------------- Baby, it's a violent world.
Registrovani korisnik Linuxa broj 460770 [Ubuntu 7.10] |
|
|
|
| calamity |
Mar 6 2009, 07:03 PM
Post
#4
|
 Group: Članovi Joined: 4-April 07 From: Cambridge, MA, USA Member No.: 491 Status: Van MGa Škola/Razred: MIT junior, RAF alumna, Grobarska alumna |
Cek, treba da nadjes bilo koji put koji povezuje sve cvorove ako postoji?
Kako mi se cini, mozes da pustis neki algoritam za obilazak grafova (guglaj Depth First Search ili Breadth First Search). Krenes iz jednog cvora, pa obilazis dok mozes. Ako si obisao sve cvorove, postoji takav put (negde usput ga zapamti ako ti treba). Mada hmmm... ne znam koliko je zgodno tako pamtiti put... i sta u stvari radis u zadatku ako recimo imas 4 cvora a povezani su ti (1, 2), (1,3), (1,4). Ako treba da pamtis i vracanje u prvi cvor i sta ja znam, mooooozda je to prilcno zeznuto   A mozda i ja ne kapiram zadatak.This post has been edited by calamity: Mar 6 2009, 07:06 PM |
|
|
|
| maxydelanoche |
Mar 6 2009, 07:10 PM
Post
#5
|
|
Group: Članovi Joined: 3-May 06 From: Zion Member No.: 61 Status: Van MGa |
Eeeee, da... ovaj, dakle
grana bez koje graf ne bi bio povezan zove se most... Jel' znas sta je DFS? Kada ides DFS-om po grafu, ukoliko pritom neki cvor u ima neko dete cvor v u DFS stablu, pri cemu vazi el[v]<ulazni[u], onda je grana koja spaja ta dva cvora - most. Pri tome je ulazni niz dobijen uobicajeno DFS pretragom, a u nizu el je na mestu i minimalni od ulaznih stepenova cvorova do kojih se moze stici unazad granama grafa od cvora i, tj najdalji predak cvora i povezan sa delom DFS stabla koji sadrzi potomke cvora i. Ako i nema nijednog takvog pretka, onda je el[i]=ulazni[i]. This post has been edited by maxydelanoche: Mar 6 2009, 07:16 PM -------------------- Mi znamo sta se desava sa ljudima koji zastanu nasred puta. Bivaju pregazeni.
Nista nije nemoguce. Za nemoguce je samo potrebno malo vise vremena. I'm doing the best I ever did, I'm doing the best that I can. www.viva-fizika.org |
|
|
|
| pyost |
Mar 6 2009, 07:30 PM
Post
#6
|
|
Deus Ex Makina Group: Administratori Joined: 25-January 06 From: Beograd Member No.: 2 Status: Bivši učenik MGa Škola/Razred: RAF |
Errr... Mislim da ovo poslednje bas i nije od pomoci
 -------------------- Baby, it's a violent world.
Registrovani korisnik Linuxa broj 460770 [Ubuntu 7.10] |
|
|
|
| darkokg |
Mar 6 2009, 07:34 PM
Post
#7
|
|
Group: Članovi Joined: 1-April 08 Member No.: 992 Status: Van MGa Ime i prezime: Darko Antonijevic |
Hvala na odgovorima, ali jos kad bih i nesto ukapirao. Prvo, ne znam sta znaci DFS, ako bi mi malo pojasnili, mozda bih i mogao da uradim nesto...
|
|
|
|
| pyost |
Mar 6 2009, 07:35 PM
Post
#8
|
|
Deus Ex Makina Group: Administratori Joined: 25-January 06 From: Beograd Member No.: 2 Status: Bivši učenik MGa Škola/Razred: RAF |
Depth First Search (google)
-------------------- Baby, it's a violent world.
Registrovani korisnik Linuxa broj 460770 [Ubuntu 7.10] |
|
|
|
| darkokg |
Mar 6 2009, 07:36 PM
Post
#9
|
|
Group: Članovi Joined: 1-April 08 Member No.: 992 Status: Van MGa Ime i prezime: Darko Antonijevic |
QUOTE(pyost @ Mar 6 2009, 07:55 PM) Mozda da brojis na koliko nacina su koja dva cvora povezana? Ako izmedju neka dva cvora postoji samo 1 put, onda je to trazeni put... Valjda  Mislim da ovo nije resenje. Moze da postoji vise parova koji su povezani samo jednim putem a da u isto vreme povezuju iste delove grafa.... |
|
|
|
| maxydelanoche |
Mar 6 2009, 07:39 PM
Post
#10
|
|
Group: Članovi Joined: 3-May 06 From: Zion Member No.: 61 Status: Van MGa |
Ovo moje je resenje sto posto. Treba ti modifikovani DFS koji sam opisala. Izgooglaj sta je DFS, iskodiraj ga i shvati lepo, a onda pokusaj da implementiras i ovo sto sam ti rekla.
-------------------- Mi znamo sta se desava sa ljudima koji zastanu nasred puta. Bivaju pregazeni.
Nista nije nemoguce. Za nemoguce je samo potrebno malo vise vremena. I'm doing the best I ever did, I'm doing the best that I can. www.viva-fizika.org |
|
|
|
| darkokg |
Mar 6 2009, 07:40 PM
Post
#11
|
|
Group: Članovi Joined: 1-April 08 Member No.: 992 Status: Van MGa Ime i prezime: Darko Antonijevic |
Da, sad sam na prvo citanje shvatio da moze da mi posluzi, HVALA!!!!
Nadam se da cu se izvuci...... |
|
|
|
| maxydelanoche |
Mar 6 2009, 07:45 PM
Post
#12
|
|
Group: Članovi Joined: 3-May 06 From: Zion Member No.: 61 Status: Van MGa |
Imam kod za DFS gotov, ali radi sa listama povezanosti, a ne sa matricama, tako da sumnjam da bi ti bio od koristi
Al' ima sigurno dosta o tome na netu, tako da ces se sigurno snaci ako se pomucis dovoljno  -------------------- Mi znamo sta se desava sa ljudima koji zastanu nasred puta. Bivaju pregazeni.
Nista nije nemoguce. Za nemoguce je samo potrebno malo vise vremena. I'm doing the best I ever did, I'm doing the best that I can. www.viva-fizika.org |
|
|
|
| calamity |
Mar 6 2009, 09:33 PM
Post
#13
|
|
Group: Članovi Joined: 4-April 07 From: Cambridge, MA, USA Member No.: 491 Status: Van MGa Škola/Razred: MIT junior, RAF alumna, Grobarska alumna |
@maxydelalonche
Ja apsolutno nisam razumela tvoje resenje a znam i sta je DFS i most itd Ne mogu da ispratim edit: jos jednom procitah... i opet ne kapiram sta pokusavas da kazes This post has been edited by calamity: Mar 6 2009, 09:34 PM |
|
|
|
| maxydelanoche |
Mar 6 2009, 09:37 PM
Post
#14
|
|
Group: Članovi Joined: 3-May 06 From: Zion Member No.: 61 Status: Van MGa |
Aaaaa, moras malo da sednes i da dobro razmislis kako da implementiras to, ali u sustini ne mora nista vise da se objasni
a i mrrrzi me  ja sam bila uspela da na osnovu samo takvog objasnjenja napravim program, uspece i darkokg -------------------- Mi znamo sta se desava sa ljudima koji zastanu nasred puta. Bivaju pregazeni.
Nista nije nemoguce. Za nemoguce je samo potrebno malo vise vremena. I'm doing the best I ever did, I'm doing the best that I can. www.viva-fizika.org |
|
|
|
| calamity |
Mar 6 2009, 09:43 PM
Post
#15
|
|
Group: Članovi Joined: 4-April 07 From: Cambridge, MA, USA Member No.: 491 Status: Van MGa Škola/Razred: MIT junior, RAF alumna, Grobarska alumna |
M' ja ne razumem ni sta radis uopste ;D No, nebitno, ako darkokg razume, sve super
|
|
|
|
 |
2 User(s) are reading this topic (2 Guests and 0 Anonymous Users)
0 Members:
Powered by Invision Power Board(Trial) v2.0.0 © 2024 IPS, Inc.