Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forendiskussionen (Übersicht)

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

--- pruefungen:bachelor:aud:loesungss12 [31.03.2015 10:52] – xenexi
+++ pruefungen:bachelor:aud:loesungss12 [28.03.2016 01:38] (aktuell) – tomabrafix
@@ Zeile 31: / Zeile 31: @@
 {{:pruefungen:bachelor:aud:08-12-graph1.png|:pruefungen:bachelor:aud:08-12-graph1.png}}
+Lösungsweg:
+Alle Spalten mit einem unendlichen Kantengewicht legen die Knoten fest mit dem Spaltenindex als Knotennamen. In diesem Fall gibt es also die Knoten 0-4 (einschl.). Die Zahlen in der ersten Zeile geben dabei einen Indexbereich im zweiten Teil des Arrays an. Im Folgenden "IK-Zahlen" genannt.
+Der zweite Teil des Arrays ohne unendliche Kantengewichte wird nun also in mehrere Bereiche für jeden Knoten aufgeteilt. Dabei geben die jeweiligen IK-Zahlen die erste Spalte zu einem Bereich an. Für Knoten 0 fängt der Bereich 0 also mit Spalte 5 an. Bereich 1 für Knoten 1 fängt aber auch bei Knoten 5 an, weshalb für Knoten 0 keine Spalte übrig bleibt. Bereich 2 fängt ab Spalte 6 an und damit umfasst Bereich 1 nur Spalte 5. Am Ende sieht unser geteiltes Array also so aus:
+<code>Knoten	_1__|_______2_______|___________3___________|_______4____
+   |    3     4    |     0     1     4     |   0    1
+γ       12  |    6     7    |     10    8     5     |   11   9
+</code>
+Jetzt kann man die Kanten ganz einfach ablesen. Die Kanten gehen dabei immer vom jeweiligen Knoten des Bereiches zu dem Knoten in der ersten Zeile der Tabelle. Somit enstehen aus obiger Tabelle folgende Kanten:
+->0, 2->3, 2->4, 3->0, 3->1, 3->4, 4->0, 4->1
+Die zweite Zeile repräsentiert die Kantengewichte.
 **b)**