Side 1 av 1
Grafteori
Lagt inn: 19/04-2007 14:10
av binge
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
![Bilde](http://img206.imageshack.us/img206/6135/grafoz7.jpg)
Lagt inn: 19/04-2007 15:15
av dischler
Skal du f.eks besøke Berlin må du jo innom Brandenburg to ganger f.eks.
Lagt inn: 19/04-2007 17:03
av binge
dischler skrev: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
![Razz :P](./images/smilies/icon_razz.gif)
Lagt inn: 19/04-2007 17:21
av Magnus
Lagt inn: 19/04-2007 17:27
av daofeishi
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.
Lagt inn: 19/04-2007 18:11
av gnom2050
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).
Lagt inn: 20/04-2007 08:00
av dischler
binge skrev:dischler skrev: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
![Razz :P](./images/smilies/icon_razz.gif)
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å?
Lagt inn: 20/04-2007 17:34
av KjetilEn
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.