Matematické Fórum
Archiv diskusního fóra o matematice, 2006–2026
#1 21. 07. 2011 14:37
- ketrin
- Zelenáč
- Příspěvky: 6
- Reputace: 0
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
#2 21. 07. 2011 16:43 — Editoval petrkovar (21. 07. 2011 16:44)
Re: pocet ciest danej dlzky v orientovanom grafe
Kdyby šlo o počet sledů (dovolíme opakování vrcholů) a nikoliv o počet cest, tak stačí zkoumat mocniny matice sousednosti 
, neboť každý prvek 
udává počet sledů délky 
mezi příslušnými dvěma vrcholy.
Nasměrování: Naštěstí máme omezenu délky na 3, tak z druhé mocniny (
) snadno poznáme cykly délky 2 (dvojice opačně orientovaných hran) a ty pomohou identifikovat sledy, které nejsou cestami. Ani uzavřené sledy délky 3 nebudeme počítat...
EDIT: (jen překlepy)
Offline