Matematické Fórum

Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.

Nástěnka
! 04. 11. 2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
17. 01. 2016 (Jel.) Rok 2016 s novými a novějšími krystaly od kolegy Pavla!
17. 01. 2016 (Jel.) Nabídka knih z oborů matematiky, fyziky, chemie
23. 10. 2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.

Nejste přihlášen(a). Přihlásit

#1 25. 02. 2016 11:14

snoby
Příspěvky: 26
Škola: FRI-ZA
Pozice: Študent
Reputace:   
 

Najdenie vsetkych rezov v grafe

Ahojte,

Mam neorientovany graf G=(V,E) kde V je vrcholova mnozina a E je mnozina hran a su dane dva specialne vrcholy S-zdroj a T-spotrebic a mam najst vsetky rezy grafu tak aby ked rozdelim graf na dva podgrafy tak v jednej mnozine bude S a v druhej T. Docital som sa ze moznych rezov bude az 2^n. Vedel by mi niekto poradit nejaky algoritmus ktory by dokazal najst vsetky rezy v grafe? Snazim sa to naprogramovat.

Offline

 

#2 11. 03. 2016 17:32

snoby
Příspěvky: 26
Škola: FRI-ZA
Pozice: Študent
Reputace:   
 

Re: Najdenie vsetkych rezov v grafe

Zravim,

Tak naprogramoval som to na baze "hrubej sily" ale zlozitost to ma 2^n kde n je pocet hran. Nasiel som nejaky clanok kde sa uvadza jeden algoritmus s lepsou zlozitostou ale moc mu nerozumiem. Vedel by mi niekto pomoct prosim? Pridavam aj clanok

http://uloz.to/xATtBgtR/a-simple-algori … tworks-pdf

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson