matematikk.net

NB! Har gjort det meste av oppgaven, men jeg oppgir den fullstendig for klarhet. Oppgaven er gitt i kursiv, og den delen jeg lurer på er markert fet/understreket.

La m og n være naturlige tall der [tex]2 \leq m \leq n \leq 3[/tex] , og la V være en mengde med m + n, la oss si V = {[tex]A_1 ,...., A_m, B_1,..., B_n[/tex]}.
Vi kan da danne en enkel graf [tex]K_{m, n}[/tex] med V som nodemengde ved å si at det finnes nøyaktig en kan mellom [tex]A_i[/tex] og [tex]B_j[/tex] for hver [tex] 1 \leq i \leq m[/tex] og hver [tex] 1 \leq j \leq n[/tex] og ingen kan ellers.


a)
Lag en skisse av [tex]K_{2, 2}[/tex], [tex]K_{2, 3}[/tex] og [tex]K_{3, 3}[/tex]
Angi matrisen til [tex]K_{2, 3}[/tex] (m.h.p. listingen [tex]A_1, A_2, B_1, B_2, B_3[/tex] av nodene.)


b) Nøyaktig en av grafene fra a) er semi-Eulersk. Angi en Eulersk vei i denne grafen.
En annen blant disse tre grafene er hverken Eulersk eller semi-Eulersk.
Angi et utspennende tre for denne.


Hva er et utspennende tre? Finner ikke noe i litteraturen om dette (har engelske fagbøker, så det kan være grunnen. )

Kan ikke så mye om grafteori, men angående [tex]K_{3,3}[/tex]

: http://www.supuzzle.com/

Veldig morsomt, synd det er umulig å fullføre den.

Tror jeg fant løsningen på det selv.

"Spanning tree":
1. Løsningen må være et tre
2. Hjørnene i treet må være de samme hjørnene som i den orginale grafen
3. Kantene i treet må velges fra mengden av kanter i den orginale grafen

Da var det jo litt for lett.

Stemmer det. Og du har nok antakeligvis også vært borte i både Prims og Kruskals algoritme for å finne et "minimum spanning tree" i vektede grafer.

Er kjent med Prim's algoritme (har ikke hatt Kruskals ennå). Jeg visste hva et "minimum spanning tree" var. Men siden grafen ikke er vektlagt har den jo ingen. Så det var bare der forvirring oppstod.