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 21. 07. 2011 14:37
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