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
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗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
Stránky: 1
- Hlavní strana
- » Projekty a příklady z Diskrétní matematiky
- » Najdenie vsetkych rezov v grafe
#1 25. 02. 2016 11:14
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
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
Stránky: 1
- Hlavní strana
- » Projekty a příklady z Diskrétní matematiky
- » Najdenie vsetkych rezov v grafe