Uppgift 10 våren 2014

Uppgiften ska lämnas till din övningsledare på övningen den 18/4 16/4.

För godkänt måste du ha gjort samtliga deluppgifter. Det är tillåtet att göra enstaka fel och misstag men det är viktigt att du försöker lösa samtliga uppgifter.

Hemuppgift

Läs den här texten om grafer.

Skriftlig uppgift

Lämna in svar på följande uppgifter.

• Rita en oriktad graf med 6 hörn, 10 kanter och 2 sammanhängande komponenter. Går det att rita en graf med 5 hörn, 4 kanter och 3 komponenter?
• Låt G vara en oriktad graf som består av 8 hörn numrerade från 0 till 7 och kantmängden {(0,1), (0,3), (1,4), (2,2), (3,4), (3,5), (6,7)}.
  • Rita G.
  • Ange ordningen som hörnen besöks vid en djupetförstsökning (DFS) med start i hörn 0.
  • Ange ordningen som hörnen besöks vid en breddenförstsökning (BFS) med start i hörn 0.
  Du kan anta att grannarna till ett hörn besöks i nummerordning.
• Skulle du representera en graf med hjälp av en närhetsmatris eller med hjälp av närhetslistor i följande fall? Motivera dina svar.
  • Grafen har 1000 hörn och 2000 kanter och det är viktigt att vara sparsam med minnet.
  • Grafen har 1000 hörn och 50000 kanter och det är viktigt att vara sparsam med minnet.
  • Det är viktigt att snabbt (på konstant tid) kunna avgöra om två hörn är grannar. Om möjligt vill du också vara sparsam med minnet.
• Förklara varför DFS tar Θ(n²) tid för en sammanhängande graf med n hörn om grafen representeras med en närhetsmatris.

HashGraph

Bekanta dig med koden i Eclipse-projektet Graph.zip och gör sedan ytterligare en implementation av gränssnittet Graph. Din implementation ska använda närhetslistor implementerade med hjälp av hashtabeller. Datastrukturer och metodsignaturer är redan deklarerade i klassen HashGraph och testkod finns i klassen HashGraphTest. Du får inte ändra koden i gränssnitten Graph, VertexIterator eller VertexAction.

• Lämna in den nyskrivna klassen HashGraph.

Eclipse-tips: Jag har bara hittat ett väl fungerande sätt att importera ett existerande projekt från en zip-fil. Välj alternativet "Import..." från fil-menyn, välj sedan "Existing Projects into Workspace", tryck på "Next >", välj "Select archive file" och tryck till slut på "Finish".

Komponenter i slumpgraf

Prova din nya grafklass genom att skriva ett program som bygger en graf med n noder och n slumpmässigt utplacerade kanter. Programmet ska med hjälp av djupetförstsökning beräkna antalet komponenter i grafen och storleken på den största komponentet.

• Lämna in koden för detta program. (Du behöver naturligtvis inte lämna in de klasser och gränssnitt som redan finns färdiga.)

Prova hur snabbt ditt program blir för olika värden på n, n <= 5000, när man använder närhetsmatris respektive närhetslistor.

• Ange antalet komponenter och den största komponentents storlek när n = 1000.
• Vilken datastruktur är bäst i det här fallet? Varför? Förklara genom att beräkna tidskomplexiteten för DFS med närhetsmatris samt för DFS med närhetslistor.

Alternativ uppgift

Om du vill så kan du istället göra hela uppgiften i Go. Använd då kodskelettet graph_skeleton.zip. How to Write Go Code innehåller de instruktioner du behöver för att komma igång med att bygga och testa egna paket i Go.