Linjär algebra - grannmatriser
Har suttit länge och funderat på denna nu och kan inte komma fram till vilken väg som efterfrågas.
Har denna graf:
Och denna grannmatris:
Första termen är 𝑎𝑖1𝑎1𝑗 = 1 om en viss väg mellan två noder i grafen 𝐺 existerar, och 𝑎𝑖1𝑎1𝑗 = 0
om den inte existerar. Vilken väg?
Svarade vägen b -> a -> e men det var fel
Jag förstår inte frågan. Har du en bild på frågans text också?
Frågan är sista stycket där dvs "Första termen är 𝑎𝑖1𝑎1𝑗 = 1 om en viss väg mellan två noder i grafen 𝐺 existerar, och 𝑎𝑖1𝑎1𝑗 = 0
om den inte existerar. Vilken väg?".
Står även detta om grafen:
En graf kan beskrivas med hjälp av en så kallad grannmatris, som vi sedan kan använda för att
studera problem kopplade till grafen.
Antag att vi har en graf 𝐺 = (𝑉, 𝐸) med hörn 𝑉 = {𝑣1, 𝑣2, … , 𝑣𝑛}. Grannmatrisen 𝐴 = [𝑎𝑖𝑗 ] för
grafen 𝐺 är då den 𝑛 × 𝑛-matris som uppfyller att 𝑎𝑖𝑗 = 1 om 𝑣𝑖 och 𝑣𝑗 är grannar och 𝑎𝑖𝑗 = 0
annars. Det innebär att vi också kan tolka element 𝑎𝑖𝑗 i 𝐴 som antal vägar av längd 1 mellan 𝑣𝑖 och
𝑣𝑗 .
Och fick detta som feedback av läraren:
Tips:
Ni bör tänka att vägen gäller för en allmän graf, dvs utgå inte ifrån att det gäller just den grafen som beskrivs i figur 1 i introduktionen.
Börja gärna med att beskriva hörnen som v1, v2, …, vn om grafen har n stycken hörn.
Exempelvis gäller det då att v1 är det första hörnet, vi är det i:te hörnet och vj är det j:te hörnet.
När ni löser uppgift 1d kan ni först betrakta vardera av de två elementen ai1 respektive a1j enskilt.
Observera att om ai1a1j = 1, så måste både ai1 = 1 och a1j = 1 gälla. Vilken väg har vi om ai1 = 1? Vilken väg har vi om a1j= 1?
Fundera sedan på vilken väg av längd 2 som beskrivs av produkten ai1a1j i uppgiften.
Uttryck sedan denna väg med hjälp av hörnen.
Fått hjälp på annat håll men tack ändå!
Bra. Det var onödigt svårt att förstå uppgiften genom att alla index stod på raden. Jag kunde inte förstå att ai1a1j var en produkt av två tal.
Hej! Jag sitter fast med samma uppgift och förstår verkligen inte... Kan du försöka förklara iom du fått hjälp från annat håll?
/ Desperat och väldigt tacksam elev
MEnglund skrev:Hej! Jag sitter fast med samma uppgift och förstår verkligen inte... Kan du försöka förklara iom du fått hjälp från annat håll?
/ Desperat och väldigt tacksam elev
Kan du lägga upp en bild på frågan?
Micimacko skrev:MEnglund skrev:Hej! Jag sitter fast med samma uppgift och förstår verkligen inte... Kan du försöka förklara iom du fått hjälp från annat håll?
/ Desperat och väldigt tacksam elev
Kan du lägga upp en bild på frågan?
vägen ska gälla för en allmän graf G och ts’ kommentarer/beskrivningar ovan gäller för denna uppgiften
ännu ett tips är: ”Det betyder att ai1 talar om ifall det finns en kant mellan vi och v1. På samma sätt talar a1j om huruvida det finns en kant mellan v1 och vj. Om båda dessa kanter existerar kan vi bilda en väg av längd 2 eftersom de har en gemensam nod. Det sista steget är att tänka igenom i vilka fall ai1a1j=1 respektive ai1a1j=0.”
Inte bästa förklaringen, men du får säga till vad som saknas.
Micimacko skrev:
Inte bästa förklaringen, men du får säga till vad som saknas.
Kan svaret vara så enkelt som vi -> v1 -> vj? Jag förstår din förklaring och det känns ju rätt men alla tips hit och dit har krånglat till det så fruktansvärt för mig...
Ja det de vill att du ska inse är att om någon/båda av de 2 bitarna saknas så blir produkten 0. Går att utöka till hur långa vägar som helst.
Micimacko skrev:Ja det de vill att du ska inse är att om någon/båda av de 2 bitarna saknas så blir produkten 0. Går att utöka till hur långa vägar som helst.
Tack så otroligt mycket för hjälpen!
Det är vi -> v1 -> vj jag fick som svar också! :)
