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
- Hlavní strana
- » Vysoká škola: úvod do studia
- » matice sousednosti -> matice dosazitelnosti
#2 04. 05. 2012 18:12
- check_drummer
- Příspěvky: 4901
- Reputace: 105
Re: matice sousednosti -> matice dosazitelnosti
Ahoj. Zkus se podívat co vyjadřuje druhá mocnina matice sousednosti - a co obecně n-tá.
"Máte úhel beta." "No to nemám."
Offline
#4 04. 05. 2012 22:38
- check_drummer
- Příspěvky: 4901
- Reputace: 105
Re: matice sousednosti -> matice dosazitelnosti
↑ xxxxx19:
V tom případě navrhuji průchod do hloubky - a na základě navštívených vrcholů zapsat na příslušné místo matice dosažitelnosti hodnotu 1.
"Máte úhel beta." "No to nemám."
Offline
#6 06. 05. 2012 14:30
- check_drummer
- Příspěvky: 4901
- Reputace: 105
Re: matice sousednosti -> matice dosazitelnosti
↑ xxxxx19:
Naopak - záleží jak se naprogramuje. Nesmíš si zafixovat "backtracking = exponenciální složitost"...
"Máte úhel beta." "No to nemám."
Offline
#8 06. 05. 2012 16:06
- check_drummer
- Příspěvky: 4901
- Reputace: 105
Re: matice sousednosti -> matice dosazitelnosti
↑ xxxxx19:
Opravdu? Jen stručně:
Začnu s vrcholem 1 a budu hledáním do hloubky označovat ty vrcholy, které při prohledávání navštívím (vede do nich cesta). Čas strávený na vrcholu i je O(n) a každý vrchol navštívím jen jednou (budu si pamatovat, že už jsem tam byl). Tj. po jedné naznačené iteraci budu mít označeny ty vrcholy, které jsou v jedné komponentě souvislosti - a to zaznamenám do matice dosažitelnosti. Následně vyberu první dosud neoznačený vrchol a pro ten budu postupovat stejně.
Díky tomu, že čas strávený na každém vrcholu je O(n), pak celková složitost je O(n^2). Rychleji to stejně nejde, vzhledem k tomu, že matice incidence má n^2 prvků...
"Máte úhel beta." "No to nemám."
Offline
Stránky: 1
- Hlavní strana
- » Vysoká škola: úvod do studia
- » matice sousednosti -> matice dosazitelnosti