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
Téma zavřeno
- Hlavní strana
- » Zajímavé úlohy z diskrétní matematiky
- » pocet ciest danej dlzky v orientovanom grafe (TOTO TÉMA JE VYŘEŠENÉ)
#1 22. 07. 2011 17:31
pocet ciest danej dlzky v orientovanom grafe
zdravim, momentalne sa ucim na statnice a neviem si rady s jednou ulohou, bola by som rada, ak by sa nasiel niekto ochotny a nasmeroval ma k rieseniu ci uz formou preudokodu alebo popisu algoritmu...
orientovany graf je reprezentovany pomocou matice susednosti (0 ak hrana medzi vrcholmi i a j neexistuje, 1 ak existuje). Navrhnite, ako mozno pomocou tejto matice zistit pocet ciest danej dlzky (v mojom pripade dlzky 3) medzi jednotlivymi vrcholmi grafu.
Offline
- (téma jako vyřešené označil(a) byk7)
#2 22. 07. 2011 17:46 — Editoval Pavel Brožek (22. 07. 2011 17:46)
- Pavel Brožek
- Místo: Praha
- Příspěvky: 5694
- Škola: Informatika na MFF UK
- Pozice: Student
- Reputace: 194
Re: pocet ciest danej dlzky v orientovanom grafe
Nestačilo by umocnit matici na délku cesty (v tvém případě na třetí) a vzít vhodný prvek matice?
Offline
#3 22. 07. 2011 18:47
- OiBobik
- Moderátor
- Místo: Brno/Praha
- Příspěvky: 1013
- Škola: MFF UK Mat. struktury
- Pozice: student
- Reputace: 82
Re: pocet ciest danej dlzky v orientovanom grafe
↑ Pavel Brožek:
Obávám se, že takto dostaneme počet sledů, nikoli cest.
"The first rule of Tautology Club is the first rule of Tautology Club." [xkcd]
Offline
#4 22. 07. 2011 19:06
- check_drummer
- Příspěvky: 4901
- Reputace: 105
Re: pocet ciest danej dlzky v orientovanom grafe
↑ OiBobik:
Nestačilo by po každém násobení nulovat diagonálu?
"Máte úhel beta." "No to nemám."
Offline
#5 22. 07. 2011 20:31
- OiBobik
- Moderátor
- Místo: Brno/Praha
- Příspěvky: 1013
- Škola: MFF UK Mat. struktury
- Pozice: student
- Reputace: 82
Re: pocet ciest danej dlzky v orientovanom grafe
↑ check_drummer:
no, to by možná stačilo, to je pravda : ) to znamená vlastně "vždy, když nám vyjde cyklus (nebo hrana použitá tam a zpět), tak ten neuvažujeme".
"The first rule of Tautology Club is the first rule of Tautology Club." [xkcd]
Offline
#6 22. 07. 2011 23:29
- Pavel Brožek
- Místo: Praha
- Příspěvky: 5694
- Škola: Informatika na MFF UK
- Pozice: Student
- Reputace: 194
Re: pocet ciest danej dlzky v orientovanom grafe
↑ ketrin:
To se nedělá, zakládat duplicitní témata. Je to proti pravidlům. Téma zavírám, nechť diskuse pokračuje v původním tématu.
Offline
Téma zavřeno
Stránky: 1
- Hlavní strana
- » Zajímavé úlohy z diskrétní matematiky
- » pocet ciest danej dlzky v orientovanom grafe (TOTO TÉMA JE VYŘEŠENÉ)