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
Zdravím, omlouvám se za zdlouhavý nadpis.
Doufám že je to také matematické téma :) Potřeboval bych poradit jak Topologicky očíslovat vrcholy grafu.
Nevím totiž, jestli to chápu spárvně. Mám graf, dejme tomu s 12 vrcholy. Najdu si vrchol do kterého nevede žádná hrana z jiného vrcholu, přiradím mu číslo 1. Pak tento vrchol odeberu z grafu, pokud to chápu správně tak odeberu i všechny hrany co z něho vychází? A pak zase najdu vrchol do kterého nic nevstupuje a přiradím mu číslo 2 a pokračuji takto až do konce? :-) Co se stane když na začátku budu mít 3 vrcholy do kterých nic nevede ?
A k Eulerovským tahů: Potřeboval bych poradit jaký algorytmus použit pro hledání uzavřeného Eul. tahu. Zatím jsem to nějak moc nepochopil, a pokoušel jsem se hledat Eul. tah tím způsobem, že jsem si nakreslil graf a ten postupně obtahoval propiskou tak dlouho dokud se nepovedlo najít Eul. tah :-)
Offline
U toho Topologického uspořádání postup vypadá ok a je jedno, jaký "volný" vrchol se vybere.
Dva případy, na které je třeba si ověřit je, že
- "volný" vrchol nedostane nižší číslo než nějaký vrchol ze kterého do něj vedou hrany. Ale to nemůže, protože kdyby do něj vedla nějaká hrana z "předchozího" vrcholu, tak by ještě nebyla odstraněna
- výběr libovolného "volného" vrcholu nemá vliv na ostatní vrcholy - pokud to byla jediná hrana, která do následujícího vrcholu vedla, tak není důvod (všechny hrany (i tranzitivní), které do něj vedly už byly odstraněny), proč by se nemohlo pokračovat tam. A pokud to nebyla jediná hrana, tak nebude volným vrcholem a musí se prvně očíslovat vrcholy, ze kterých do něj hrany vedou
Offline
Stránky: 1