Köningsbergs broar
Hej!
Uppgiften lyder:
Jag har problem på uppgift a). Mitt lösningsförsök är:
Ja, man kan ta bort en av broarna som binder A och C eller ta bort en av broarna mellan A och D för att få en Eulerväg (högst två kanter får vara udda kanter), vilket blir uppfyllt i detta fall då A och C blir jämna hörn eller A och D blir jämna hörn.
Enligt facit så kan man inte göra det, VARFÖR???
Du har rätt.
Om du till exempel tar bort en av vägarna mellan A och C så finns det åtminstone följande Eulerväg:
Yngve skrev :Du har rätt.
Om du till exempel tar bort en av vägarna mellan A och C så finns det åtminstone följande Eulerväg:
Saken är bara att facit säger att det inte går. Därmed vet jag inte hur jag ska angripa fråga b). Jag anser då att man måste lägga till en bro mellan A och C respektive A och D.
Men facit säger då att man bör lägga till en bro mellan A och C samt B och D.
Varför får jag fel igen ...
Då har facit fel.
Vad det gäller b) kan du tänka såhär: Det finns fyra hörn, varav alla har udda valens. Om du lägger till en koppling mellan två punkter innebär det +1 valens till två hörn. Då är det endast två udda hörn kvar, och det finns en Eulerväg. Därför borde det gå att endast lägga till en bro, som borde kunna gå mellan alla kombinationer av två hörn.
Det som står i facit är bara ett förslag och inte "den enda rätta" lösningen.
Ditt förslag fungerar bra även det.
Men du har fel om du säger att man måste lägga till bro AC AD.
Det räcker med en extra bro, till exempel mellan A och C.
Yngve skrev :Det som står i facit är bara ett förslag och inte "den enda rätta" lösningen.
Ditt förslag fungerar bra även det.
Men du har fel om du säger att man måste lägga till bro AC AD.
Det räcker med en extra bro, till exempel mellan A och C.
Insåg det nu då jag var insatt i Eulerkrets istället för Eulerväg :)
Smutstvätt skrev :Då har facit fel.
Vad det gäller b) kan du tänka såhär: Det finns fyra hörn, varav alla har udda valens. Om du lägger till en koppling mellan två punkter innebär det +1 valens till två hörn. Då är det endast två udda hörn kvar, och det finns en Eulerväg. Därför borde det gå att endast lägga till en bro, som borde kunna gå mellan alla kombinationer av två hörn.
Men enligt rättelserna på matematik 5000 boken som jag har så borde det inte finnas någon fel i facit med just denna uppgift ...
Smutstvätt skrev :Då har facit fel.
Vad det gäller b) kan du tänka såhär: Det finns fyra hörn, varav alla har udda valens. Om du lägger till en koppling mellan två punkter innebär det +1 valens till två hörn. Då är det endast två udda hörn kvar, och det finns en Eulerväg. Därför borde det gå att endast lägga till en bro, som borde kunna gå mellan alla kombinationer av två hörn.
Facit har inte fel, förslaget fungerar, men det är olyckligt formulerat om det står att man bör göra så. Det bör stå att man kan göra så.
Yngve skrev :Smutstvätt skrev :Då har facit fel.
Vad det gäller b) kan du tänka såhär: Det finns fyra hörn, varav alla har udda valens. Om du lägger till en koppling mellan två punkter innebär det +1 valens till två hörn. Då är det endast två udda hörn kvar, och det finns en Eulerväg. Därför borde det gå att endast lägga till en bro, som borde kunna gå mellan alla kombinationer av två hörn.
Facit har inte fel, förslaget fungerar, men det är olyckligt formulerat om det står att man bör göra så. Det bör stå att man kan göra så.
Men när man ger ett exempel, borde då inte det enklaste exemplet var "den bästa". Det vill säga att i detta fall att lägga till en bro mellan AC eller AD?
Jo, jag håller med om det.
Eller ännu hellre, att det uttryckligen står att det finns flera möjliga alternativ och så kan de nämna ett par stycken.
Yngve skrev :Jo, jag håller med om det.
Eller ännu hellre, att det uttryckligen står att det finns flera möjliga alternativ och så kan de nämna ett par stycken.
Min "hypotes" är därför att de menar verkligen att deras exempel är den lättaste utifrån hur de ser på frågan. Men hur ser de frågan då?
Kombinatorik skrev :Yngve skrev :Jo, jag håller med om det.
Eller ännu hellre, att det uttryckligen står att det finns flera möjliga alternativ och så kan de nämna ett par stycken.
Min "hypotes" är därför att de menar verkligen att deras exempel är den lättaste utifrån hur de ser på frågan. Men hur ser de frågan då?
Jag tror att de tog ett exempel som gör att alla noder får ett jämnt antal bågar, bara för att det därmed blir väldigt lätt att hitta en Eulerväg i den nya grafen.
Yngve skrev :Kombinatorik skrev :Yngve skrev :Jo, jag håller med om det.
Eller ännu hellre, att det uttryckligen står att det finns flera möjliga alternativ och så kan de nämna ett par stycken.
Min "hypotes" är därför att de menar verkligen att deras exempel är den lättaste utifrån hur de ser på frågan. Men hur ser de frågan då?
Jag tror att de tog ett exempel som gör att alla noder får ett jämnt antal bågar, bara för att det därmed blir väldigt lätt att hitta en Eulerväg i den nya grafen.
Nu förstår jag! Tack för hjälpen!
Yngve skrev :Smutstvätt skrev :Då har facit fel.
Vad det gäller b) kan du tänka såhär: Det finns fyra hörn, varav alla har udda valens. Om du lägger till en koppling mellan två punkter innebär det +1 valens till två hörn. Då är det endast två udda hörn kvar, och det finns en Eulerväg. Därför borde det gå att endast lägga till en bro, som borde kunna gå mellan alla kombinationer av två hörn.
Facit har inte fel, förslaget fungerar, men det är olyckligt formulerat om det står att man bör göra så. Det bör stå att man kan göra så.
Jag kanske var lite otydlig, med att facit har fel menade jag att facit har fel i a). Det går att ta bort en bro och få en eulerväg.
Smutstvätt skrev :Jag kanske var lite otydlig, med att facit har fel menade jag att facit har fel i a). Det går att ta bort en bro och få en eulerväg.
Ah, såklart. Sorry, det borde jag har förstått.
