Dersom grafen er enkel, er det kun tre mulige kanter vi kan ta med. Da må nødvendigvis de to kantene vi velger forbinde alle tre nodene. Dersom vi tillater enten løkker eller parallelle kanter, har vi flere enn tre kanter å velge mellom. Hvis vi da velger for eksempel to parallelle kanter eller minst én løkke blant de to kantene, vil ikke grafen være sammenhengende.
Kapitteltest – Kapittel 22
Test deg selv
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.
Test deg selv
La en graf ha tre noder og to kanter. Er den sammenhengende?
Test deg selv
La $G$ være en enkel graf med $n$ noder. Hva er det minimale antallet kanter $G$ kan ha og allikevel være sammenhengende?
Test deg selv
Hvilke(n) av egenskapene har den komplette grafen med fire noder?
Grafen har fire noder med odde grad, og dermed har den hverken en eulervei eller eulerkrets. Enhver komplett graf har en hamiltonsykel, og alle hamiltonsykler er også en hamiltonsti.
Test deg selv
La nodene i en graf med fire noder ha følgende grader: $2,2,3,3$. Hvilke(n) av disse egenskapene kan vi vite at grafen har?
Grafen har to noder med odde grad, og dermed har den en eulervei.
For at en graf skal ha en eulerkrets graden til enhver node være et partall.
Alle grafer med disse gradene er isomorfe, så man trenger bare å undersøke én slik graf.
Alle grafer med disse gradene er isomorfe, så vi trenger bare å undersøke én slik graf.
Test deg selv
Hvilke(n) av egenskapene har grafen?
Grafen har to noder med odde grad, og dermed finnes det en eulervei.
Ikke alle nodene i grafen har partall grad, og da finnes det ikke noen eulerkrets.