matematikk.net

Oppgaveteksten er som følgende:
b) Er det mulig å starte i en hvilken som helst stat, komme igjennom alle statene uten å gå igjennom en stat to ganger, for så å ende opp i den staten man startet i? begrunn svaret ut i fra grafteori.

også jeg makter å se at det ikke er mulig å komme gjennom alle stater uten å gå igjennom samme stat flere ganger. Sliter derimot mer i forhold til å begrunne svaret ut i fra grafteori. Er det noen som har et tips eller flere i så henseelse? på forhånd takk

Skal du f.eks besøke Berlin må du jo innom Brandenburg to ganger f.eks.

dischler wrote:Skal du f.eks besøke Berlin må du jo innom Brandenburg to ganger f.eks.

Det skjønner jeg også, men å begrunne det utifra grafteori er verre

Er vel are å sjekke om det er en "Euler-vei".

http://planetmath.org/encyclopedia/EulerPath.html

Det du ønsker å finne ut av, er om grafen har en hamiltonsk løkke. (Hamiltonian cycle.) Løsningen på dette problemet finner du ved å ta for deg nodene av grad en.

Eulerske stier gjelder traversabilitet av kantene mellom nodene, og en eulersk sti kan komme til å gå gjennom en stat flere ganger.

Det er jo tre stater som står for seg selv:

Bremen
Berlin
Saarland

Vi ser lett at man ikke kan komme gjennom uten å være gjennom samme stat to ganger, fordi det kan bare være to utenomstående stater (start og stopp).

binge wrote:

dischler wrote:Skal du f.eks besøke Berlin må du jo innom Brandenburg to ganger f.eks.

Det skjønner jeg også, men å begrunne det utifra grafteori er verre

Her må jeg si at jeg ikke skjønner hva du mener. Har man to noder A og B med bare en felles kant k (og k er eneste kant tilhørende noden A), og man skal traversere grafen slik at man besøker node A - ja da må node B besøkes to ganger. På hvilken måte det skiller seg fra en såkalt "grafteoretisk" begrunnelse aner jeg ikke. Er det noen spesifike teoremer du ønsker å bruke her, eller ønsker du å begrunne det fra aksiomnivå?

Husk at du skal gi et svar for denne grafen, ikke generellt for en vilkårlig graf.

Da vil det f.eks holde å si:

Vi må danne en Hamiltonsk krets. Grafen er ikke Hamiltonsk, fordi enhver krets gjennom Berlin må gå gjennom Brandenburg to ganger.