Oppgave
Hvilke av disse påstandene er sanne?
En vandring er enhver sekvens av noder det finnes kanter i mellom. En sti er en vandring hvor ingen node forekommer mer enn én gang. Altså er alle stier også en vandring, men ikke omvendt.
Nei, for man kan tenke på et tre som en graf med minimalt antall kanter slik at hvis vi fjerner én kant, vil grafen bli usammenhengende, og dermed vil grafen ikke lenger være et tre.
Siden grafen var et tre, vet vi at det allerede finnes en sti mellom alle par av noder. Når vi da legger til en kant mellom to noder, vet vi at det finnes to stier mellom dette paret av noder. Dermed har den nye grafen en sykel, og kan derfor ikke være et tre.
En krets er en vandring hvor første og siste node er den samme (mer presist er det en vandring hvor det finnes en kant mellom siste og første node i vandringen). En sykel, som også kalles en lukket sti, er en sti der første og siste node er den samme. Og siden alle stier også er en vandring, er alle sykler også en krets.
Ja, for eksempel den komplette grafen med tre noder. Lager man en sykel fra hvilken som helst node i den grafen, vil den ha alle de fire egenskapene nevnt i oppgaven.
Denne oppgaven finnes på følgende sider: