Avatar
Jůlie
Člen
Avatar
Jůlie:

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.

 
Odpovědět 14. srpna 9:10
Avatar
Lubor Pešek
Člen
Avatar
Lubor Pešek:

Zdravím, teď jsem byl pár dní mimo, tak se nejdřív zeptám...
Ticket je z 14.8. a dnes je 12.9. - je to ještě aktuální?

Nahoru Odpovědět  +1 12. září 17:54
Existují dva způsoby, jak vyřešit problém. Za prvé vyhoďte počítač z okna. Za druhé vyhoďte okna z počítače.
Avatar
Jůlie
Člen
Avatar
Odpovídá na Lubor Pešek
Jůlie:

Jelikož jsem práci ještě neudělala, ano je to aktuální...

 
Nahoru Odpovědět 19. září 16:59
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 3 zpráv z 3.