Embed Size (px)
DESCRIPTION
Diskrete Mathe II. Übung 30.5.2005. A. 90. 30. B. 100. 40. E. 20. 10. 40. 8. 5. C. 10. D. Ü4. Notiert die dem obigen Graphen entsprechende Adjazenzmatrix für die Kantengewichte (Kosten). - PowerPoint PPT Presentation
Citation preview
Diskrete Mathe II
Übung
30.5.2005
IKG - Übung Diskrete Mathe II – Jörg Schmittwilken 2
Ü4
2. Wendet den Algorithmus von Floyd auf den Graphen an und notiert die jeweilig aktuellen Kosten in der Adjazenzmatrix.Beschränkt Euch bei der Betrachtung auf alle Kombinationen der Laufvariablen i,j,k, bei denen die if-Bedingung erfüllt ist.
Wählt dazu die Felder der Matrix so groß, dass neue Werte neben den alten geschrieben werden können.
8 5
D
E
A
B
C
3090
2040
100
10
1040
3. Notiert die Matrix der kürzesten Wege (bezogen auf das Ergebnis aus 2.) und wendet den Ausgabealgorithmus auf einen Weg an.
1. Notiert die dem obigen Graphen entsprechende Adjazenzmatrix für die Kantengewichte (Kosten).
IKG - Übung Diskrete Mathe II – Jörg Schmittwilken 3
Ü4
D
E
A
B
C
30
90
20
40
100
10
10
40
IKG - Übung Diskrete Mathe II – Jörg Schmittwilken 4
Ü4 – Adjazenzmatrix C
A B C D E
A 0 90 100 ** 30
B ** 0 20 ** **
C ** ** 0 ** **
D 40 10 ** 0 **
E ** ** 40 10 0
IKG - Übung Diskrete Mathe II – Jörg Schmittwilken 5
Ü4 – neue Wege
A:
DAC : 140
DAE : 70
B:
DBC : 30
C:
D:
EDA : 50
EDB : 20
E:
AEB : 50
AEC : 70
AED : 40
IKG - Übung Diskrete Mathe II – Jörg Schmittwilken 6
Ü4 – Wegematrix A
A B C D E
A 0 50 70 40 30
B ** 0 20 ** **
C ** ** 0 ** **
D 40 10 30 0 70
E 50 20 40 10 0
IKG - Übung Diskrete Mathe II – Jörg Schmittwilken 7
Ü4 – Wegematrix W
A B C D E
A ** 5 5 5 **
B ** ** ** ** **
C ** ** ** ** **
D ** ** 2 ** 1
E 4 4 ** ** **
IKG - Übung Diskrete Mathe II – Jörg Schmittwilken 8
Ü4 - DetailA
E
B
D
30
10
10
90 Reihenfolge der Betrachtung:
D, E oder E, D
IKG - Übung Diskrete Mathe II – Jörg Schmittwilken 9
Ü4 - Detail
Reihenfolge der Betrachtung:
D, E oder E, D
D:
EDB : 20
E:
AEB : 30 + 20 = 50
A
E
B
D
30
10
10
90
20
50
IKG - Übung Diskrete Mathe II – Jörg Schmittwilken 10
Ü4 - Detail
Reihenfolge der Betrachtung:
D, E oder E, D
E:
AED : 40
D:
ADB : 40 + 10 = 50
A
E
B
D
30
10
10
90
40
50
IKG - Übung Diskrete Mathe II – Jörg Schmittwilken 11
Ü4 – Detail
• In beiden Fällen führt der kürzeste Weg von A nach B über E und D– AB = AEB = AEDB– AB = ADB = AEDB
A
E
B
D
30
10
10
90
20
50 A
E
B
D
30
10
10
90
40
50
IKG - Übung Diskrete Mathe II – Jörg Schmittwilken 12
Scan-Line – 1. Idee
• Schnitt von zwei Segmenten– Geradengleichungen g und g‘– Schnittpunkt p– Prüfen ob p auf g und g‘
IKG - Übung Diskrete Mathe II – Jörg Schmittwilken 13
Beispiel1
• Segment 1:– (4/1)– (8/4)
• Segment 2:– (2/3)– (6/1)
IKG - Übung Diskrete Mathe II – Jörg Schmittwilken 14
Scan-Line – 2. Idee
• Schnitt von zwei Segmenten– Prüfen der Lage von Punkt p1 und p1 bezüglich
der Geraden durch p‘1 und p‘2– Berechnen von vier Determinanten
• Alle ungleich Null• Paarweise unterschiedliches Vorzeichen
IKG - Übung Diskrete Mathe II – Jörg Schmittwilken 15
Beispiel1
• Segment 1:– (4/1)– (8/4)
• Segment 2:– (2/3)– (6/1)
IKG - Übung Diskrete Mathe II – Jörg Schmittwilken 16
Übung5
• Prüft, ob sich folgende Segmente schneiden:– P1(1/7) P2(3/1)– P3(-4/10) P4(8/5)
• Zur Prüfung verwendet– Schnittpunktberechnung zweier Geraden, und– Viermaliges Prüfen der Lage eines Punktes zu einem
Segment mithilfe von Determinanten.
• Vergleicht die beiden Verfahren indem ihr jeweils Vor- und Nachteile erläutert.
• Was leisten die beiden Verfahren bei der Überprüfung von n Segmenten?
