Matematické Fórum

ketrin · 22. 07. 2011 17:31

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.

Pavel Brožek

Nestačilo by umocnit matici na délku cesty (v tvém případě na třetí) a vzít vhodný prvek matice?

OiBobik · 22. 07. 2011 18:47

↑ Pavel Brožek:

Obávám se, že takto dostaneme počet sledů, nikoli cest.

check_drummer · 22. 07. 2011 19:06

↑ OiBobik:
Nestačilo by po každém násobení nulovat diagonálu?

OiBobik · 22. 07. 2011 20:31

↑ 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".

Pavel Brožek · 22. 07. 2011 23:29

↑ 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.

Matematické Fórum

#1 22. 07. 2011 17:31

pocet ciest danej dlzky v orientovanom grafe

#2 22. 07. 2011 17:46 — Editoval Pavel Brožek (22. 07. 2011 17:46)

Re: pocet ciest danej dlzky v orientovanom grafe

#3 22. 07. 2011 18:47

Re: pocet ciest danej dlzky v orientovanom grafe

#4 22. 07. 2011 19:06

Re: pocet ciest danej dlzky v orientovanom grafe

#5 22. 07. 2011 20:31

Re: pocet ciest danej dlzky v orientovanom grafe

#6 22. 07. 2011 23:29

Re: pocet ciest danej dlzky v orientovanom grafe