Oppgaver med vandringer og stier

Gitt en graf:

Hvis sekvensen $abcedbc$ er en vandring i grafen, finn lengden til vandringen.

Gitt en graf:

Hvis sekvensen $abcdbc$ er en vandring i grafen, finn lengden til vandringen.

Gitt en graf:

Hvis sekvensen $abcea$ er en vandring i grafen, finn lengden til vandringen. Er vandringen åpen eller lukket?

Gitt en graf:

Hvis sekvensen $abced$ er en vandring i grafen, finn lengden til vandringen. Er vandringen åpen eller lukket?

Hvis sekvensen $eabde$ er en vandring i grafen:

1. Finn lengden til vandringen
2. Er vandringen åpen eller lukket?
3. Er vandringen en sti?
4. Er vandringen en krets?
5. Er vandringen en sykel?

Hvis sekvensen $ecbaea$ er en vandring i grafen:

1. Finn lengden til vandringen
2. Er vandringen åpen eller lukket?
3. Er vandringen en sti?
4. Er vandringen en krets?
5. Er vandringen en sykel?

Hvis sekvensen $bdec$ er en vandring i grafen:

1. Finn lengden til vandringen
2. Er vandringen åpen eller lukket?
3. Er vandringen en sti?
4. Er vandringen en krets?
5. Er vandringen en sykel?

Er følgende graf sammenhengende?

Er følgende graf sammenhengende?

Er følgende graf sammenhengende?

Er følgende graf sammenhengende?

Er følgende graf asyklisk?

Er følgende graf asyklisk?

Er følgende graf asyklisk?

Er følgende graf asyklisk?

Er følgende graf asyklisk?

En graf har 8 noder og 8 kanter. Kan grafen være asyklisk?

En graf har 8 noder og 6 kanter. Er grafen asyklisk?

Et veinett modelleres som en graf der kryssene er noder og veiene er kanter.

• Forklar hva det betyr at veinettet er asyklisk.
• Gi én fordel ved et slikt veinett.
• Gi én ulempe ved et slikt veinett.

Er følgende graf et tre?

Er følgende graf et tre?

Er følgende graf et tre?

Hvor mange ikke-isomorfe trær med tre noder finnes?

Hvor mange ikke-isomorfe trær med fire noder finnes?

Hvor mange ikke-isomorfe trær med fem noder finnes?

Hvor mange ikke-isomorfe trær med seks noder finnes?

En graf har syv noder og seks kanter, og er sammenhengende. Kan grafen være et tre?

En graf har syv noder og syv kanter, og er sammenhengende. Kan grafen være et tre?

Et tre har 12 noder. Hvor mange kanter har grafen?

Et slektstre bakover i tid tar utgangspunkt i en person og innholder foreldre, besteforeldre og så videre så langt man har funnet aner.

1. Tegn et slektstre for Mathias, hans biologiske foreldre og biologiske besteforeldre.
2. Forklar hvorfor et slikt slektstre er et eksempel på et tre i grafteori.
3. Hva representerer løvnodene i et slikt slektstre?

Ivan har tre barn. De to første har tre barn hver, og den tredje har to barn.

1. Tegn et slektstre for Ivan og hans etterkommere.
2. Forklar hvorfor et slektstre med etterkommere er et eksempel på et tre i grafteori.
3. Hva representerer løvnodene i et slikt slektstre?

I et nytt boligområde skal det bygges 85 hus og veier mellom husene slik at alle kan besøke alle. Det skal kun være veikryss ved husene og man ønsker ikke flere veier enn absolutt nødvendig.

1. Forklar hvorfor veinettet kan modelleres som et tre.
2. Hvor mange veier må bygges?
3. Hva skjer hvis hvis man bygger en ekstra vei i forhold til det som er absolutt nødvendig?
4. Hva er en løvnode i denne sammenhengen?

Karina har laget et beslutningstre for å hjelpe studenter til å velge riktig teknik når de skal integrere.

1. Hva representerer noder og kanter i et beslutningstre?
2. Forklar hvorfor et beslutningstre kan modelleres som et tre.
3. Hvorfor er det viktig at et beslutningstre ikke inneholder sykler?
4. Hva representerer en løvnode i et beslutningstre?