Oppgaver med grafteori

Anne, Berit, Cecilie, Dagfinn og Eirik er personer i en vennegruppe der alle kjenner hverandre, bortsett fra Cecilie og Eirik.

Tegn en graf der nodene reprsenterer personer og kantene er representerer personer som kjenner hverandre.

Finn antall noder og kanter til følgende graf:

Finn antall noder og kanter til følgende graf:

Finn antall noder og kanter til følgende graf:

Gitt en graf:

1. Hvor mange noder har $G$?
2. Hvor mange kanter har $G$?
3. Er $a$ og $d$ naboer?
4. Er $b$ og $d$ naboer?

Gitt en graf:

1. Hvor mange noder har $G$?
2. Hvor mange kanter har $G$?
3. Hvor mange naboer har 1?
4. Er 1 og 4 naboer?
5. Er 1 og 5 naboer?

Gitt en graf $G = \langle V,E \rangle$ der $V = \{a,b,c,d\}$ og $E = \{\{a,b\},\{a,c\},\{a,d\}\}$.

1. Hvor mange noder har grafen?
2. Hvor mange kanter har grafen?
3. Er $a$ og $c$ naboer?
4. Er $b$ og $c$ naboer?
5. Tegn grafen.

Gitt en graf $G = \langle V,E \rangle$ der $V = \{1,2,3,4\}$ og $E = \{\{1,2\},\{2,3\},\{3,4\},\{2,4\}\}$.

1. Hvor mange noder har grafen?
2. Hvor mange kanter har grafen?
3. Er 1 og 3 naboer?
4. Tegn grafen.

Gitt en graf $G = \langle V,E \rangle$ der $V = \{a,b,c,d,e\}$ og $E = \{\{a,b\},\{a,c\},\{a,d\},\{b,e\},\{c,e\},\{d,e\}\}$.

1. Hvor mange noder har grafen?
2. Hvor mange kanter har grafen?
3. Er $b$ og $d$ naboer?
4. Tegn grafen.

Finn $V$ og $E$ slik at $G = \langle V, E \rangle$ definerer følgende graf:

Finn $V$ og $E$ slik at $G = \langle V, E \rangle$ definerer følgende graf:

Tegn en enkel graf med tre noder og to kanter.

Tegn en multigraf med tre noder og fire kanter der to av kantene er parallelle.

Tegn en pseudograf med tre noder og fire kanter uten at noen av kantene er parallelle.

Tegn en enkel rettet graf med tre noder og to kanter der det går en rettet kant fra den første noden til den andre og en rettet kant fra den andre noden til den tredje.

Tegn en tom graf med fem noder. Hvor mange kanter har grafen?

Tegn komplementet til følgende graf:

Tegn komplementet til følgende graf:

Finn komplementet til grafen $G = \langle V,E \rangle$ der $V = \{a,b,c,d\}$ og $E = \{\{a,b\},\{a,c\},\{b,c\}\}$.

Finn komplementet til grafen $G = \langle V,E \rangle$ der $V = \{1,2,3\}$ og $E = \{\{1,2\},\{1,3\},\{2,3\}\}$.

Tegn en komplett graf med to noder. Hvor mange kanter har grafen?

Tegn grafen $K_3$. Hvor mange kanter har grafen?

Grafen $G = \langle V,E \rangle$ har nodene $V = \{a,b,c,d\}$ og kantene $E = \{\{a,b\},\{a,c\},\{a,d\},\{b,c\},\{b,d\},\{c,d\}\}$. Tegn grafen. Hvilken type graf er dette?

Tegn en komplett graf med fem noder. Hvor mange kanter har grafen?

Grafen $G$ har seks noder og det skal være maks én kant mellom hvert par av noder. Hva er det største antallet kanter grafen kan ha?

Grafen $G$ har 13 kanter og det er maks én kant mellom hvert par av noder. Hva er det minste antallet noder grafen må ha?

Grafen $G$ har $5$ noder og 7 kanter. Hvor mange kanter har $\overline{G}$?

Lag en formel for antall kanter i en graf med $n$ kanter. Hvor mange kanter har en komplett graf med 10 noder?

Grafen $G$ har $10$ noder og 20 kanter. Hvor mange kanter har $\overline{G}$?

Grafen $G$ har $7$ noder. Hvor mange kanter har $G$ og $\overline{G}$ til sammen?

Gitt en graf $G = \langle V,E \rangle$ der $V = \{a,b,c,d\}$ og $\{\{a,d\},\{b,d\},\{c,d\}\}$.

Er grafen todelt?

Gitt en graf $G = \langle V,E \rangle$ der $V = \{a,b,c,d\}$ og $E = \{\{a,b\},\{b,c\},\{c,d\}\}$.

Er grafen todelt?

Gitt en graf $G = \langle V,E \rangle$ der $V = \{a,b,c,d\}$ og $E = \{\{a,b\},\{b,c\},\{c,a\}\}$.

Er grafen todelt?

• Hvor mange noder har $K_{2,3}$?
• Tegn grafen $K_{2,3}$
• Hvor mange kanter har $K_{2,3}$?

• Hvor mange noder har $K_{2,5}$?
• Tegn grafen $K_{2,5}$
• Hvor mange kanter har $K_{2,5}$?

• Hvor mange noder har $K_{1,5}$?
• Tegn grafen $K_{1,5}$
• Hvor mange kanter har $K_{1,5}$?

Et universitet har både studenter og emner.

• Hvorfor kan hvilke studenter som tar hvilke fag modelleres ved hjelp av en todelt graf?
• Når er denne grafen komplett todelt?

Gitt en graf:

• Finn graden til hver av nodene i grafen.
• Hvor mange kanter har grafen?
• Hva er summen av graden til alle nodene?

Gitt en graf:

• Finn graden til hver av nodene i grafen.
• Hvor mange kanter har grafen?
• Hva er summen av graden til alle nodene?

Gitt en graf $G = \langle V,E \rangle$ der $V = \{a,b,c,d,e\}$ og $E = \{\{a,c\},\{a,d\}, \{b,c\},\{b,e\},\{c,e\},\{d,e\}\}$.

• Finn graden til hver av nodene i grafen.
• Hvor mange kanter har grafen?
• Hva er summen av graden til alle nodene?

I en fotballturnering deltar åtte lag. Hvert lag spiller én kamp mot tre andre lag. Hvor mange kamper spilles totalt?

På en fest er det 10 personer. Vi modellerer situasjonen med en graf $G = \langle V, E \rangle$ der hver person er en node, og et håndtrykk mellom to personer er en kant.

• Hvis alle hilser på alle én gang, hvor mange håndtrykk blir det på festen?
• Hvis alle hilser på alle én gang, hva er summen av gradene til alle nodene?
• Kan det ha vært nøyaktig 15 håndtrykk på festen? Begrunn svaret.

Et flyselskap har direkteruter mellom byer. Vi modellerer rutene med en graf $G = \langle V, E \rangle$, der hver by er en node, og hver direkterute mellom to byer er en kant. Totalt har selskapet 9 direkteruter.

• Hva er summen av gradene i grafen?
• Anta at det er høyst én direkterute mellom hvert par av byer. Hvor mange byer må minst ha direkteruter?
• Anta at selskapet har fem byer med direkteruter, og tegn et eksempel på en graf med ni direkteruter.
• Kan det være nøyaktig tre byer som har et oddetall av direkteruter?

Tegn alle grafer med tre noder som ikke er isomorfe.

Er følgende grafer isomorfe:

Er følgende grafer isomorfe:

Er følgende grafer isomorfe:

Er følgende grafer isomorfe:

Tegn alle grafer med fem noder og fire kanter som ikke er isomorfe.

Gitt to grafer:

1. Sammenlign grafteoretiske egenskaper ved de to grafene.
2. Er de to grafene isomorfe?
3. Finn en isomorfi fra den ene grafen til den andre (dersom den eksisterer).

Gitt to grafer:

1. Sammenlign grafteoretiske egenskaper ved de to grafene.
2. Er de to grafene isomorfe?
3. Finn en isomorfi fra den ene grafen til den andre (dersom den eksisterer).

Gitt to grafer:

1. Sammenlign grafteoretiske egenskaper ved de to grafene.
2. Er de to grafene isomorfe?
3. Finn en isomorfi fra den ene grafen til den andre (dersom den eksisterer).

Gitt to grafer:

1. Sammenlign grafteoretiske egenskaper ved de to grafene.
2. Er de to grafene isomorfe?
3. Finn en isomorfi fra den ene grafen til den andre (dersom den eksisterer).

Gitt to grafer:

1. Sammenlign grafteoretiske egenskaper ved de to grafene.
2. Er de to grafene isomorfe?
3. Finn en isomorfi fra den ene grafen til den andre (dersom den eksisterer).