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. )
Utspennende tre
Moderators: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
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.
"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.
Those who know a lot, don't know more about how much they know than those who know less.
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.
Those who know a lot, don't know more about how much they know than those who know less.