TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
ahoj, potřebovala bych poradit, vůbec nevím jak začít?
Naprogramujte v JAVA:
Pro zadaný graf (orientovaný nebo neorientovaný) napište program, který zjistí, je-li graf eulerovský. V případě, že tomu tak je, nalezněte a vypište (orientovaný) uzavřený tah obsahující všechny jeho hrany. Graf je zadán obrázkem a vstup je z klávesnice, stejně jako u zadání samostatné práce.
Vaše znalosti z diskrétní matematiky a algoritmů jsou pro vyřešení projektu naprosto postačující. Potřebujete-li poradit, jakým způsobem při řešení postupovat, přečtěte si následující návod.
Návod
Podmínky, aby graf byl eulerovský.
Neorientovaný graf
Musíte zjistit, zda je souvislý a každý vrchol je sudého stupně.
Orientovaný graf
Musíte zjistit, zda je souvislý a vstupní stupeň každého vrcholu je roven jeho výstupnímu
stupni.
Souvislost, zjistíte jeho procházením do šířky nebo do hloubky, což stejně jako vstup můžete
převzít ze semestrální práce. Ověření podmínky pro stupně vrcholů je zřejmé.
Procházením grafu do hloubky pak naleznete kružnici (cyklus). Hrany této kružnice z grafu odstraníte. Pokračujete, dokud postupně neodstraníte
všechny hrany, čímž získáte množinu hranově disjunktních kružnic (cyklů). Pro souvislý graf
mají společné vrcholy. Jejich pospojováním ve tvaru číslice osm ve společném vrcholu
získáte (orientovaný) uzavřený tah obsahující všechny hrany.
Nahlásit jako SPAM
IP: 78.111.127.–
Guru
Zjistit počet nových příspěvků
