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

#1 22. 07. 2011 17:31

ketrin
Zelenáč
Příspěvky: 6
Reputace:   
 

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: 4622
Reputace:   99 
 

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

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson