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
Grafteori
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
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.
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).
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).
Blir det feil å si at Titten Tei er lett på tråden?
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å?binge skrev:Det skjønner jeg også, men å begrunne det utifra grafteori er verredischler skrev:Skal du f.eks besøke Berlin må du jo innom Brandenburg to ganger f.eks.
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.
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.