Her kan du stille spørsmål vedrørende problemer og oppgaver i matematikk på høyskolenivå. Alle som har kunnskapen er velkommen med et svar. Men, ikke forvent at admin i matematikk.net er spesielt aktive her.
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
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.
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
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å?