Informatik 11

Benutzer-Werkzeuge

Webseiten-Werkzeuge

Zuletzt angesehen:
graphen:adjazenzmatrix:start

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

Link zu dieser Vergleichsansicht

Beide Seiten der vorigen RevisionVorhergehende Überarbeitung
Nächste Überarbeitung		Vorhergehende Überarbeitung
graphen:adjazenzmatrix:start [2023/10/13 07:08] – [Aufgabe 5] Martin Pabstgraphen:adjazenzmatrix:start [2023/10/18 07:17] (aktuell) – [Aufgabe 3] Martin Pabst
Zeile 1: Zeile 1:
 ====== Adjazenzmatrix ====== ====== Adjazenzmatrix ======
 <WRAP center round info 80%> <WRAP center round info 80%>
-Die oben verwendete graphische Darstellung ist zwar anschaulich, für algorithmische Verarbeitung aber häufig eher ungünstig. Eine andere Darstellung von Graphen ist ihre **Adjazenzmatrix** (man nennt zwei Knoten, die durch eine Kante verbunden sind, auch **adjazent**). Dabei wird eine Art Tabelle aufgestellt, deren Spalten- und Zeilenanzahl der Anzahl der Knoten entspricht (die im Folgenden verwendeten Zeilen- und Spaltenbeschriftungen sind nicht Teil der Adjazenzmatrix und dienen nur der Veranschaulichung). Die Adjazenzmatrix enthält dann als Eintrag+Die bisher verwendete graphische Darstellung ist zwar anschaulich, für algorithmische Verarbeitung aber häufig eher ungünstig. Eine andere Darstellung von Graphen ist ihre **Adjazenzmatrix** (man nennt zwei Knoten, die durch eine Kante verbunden sind, auch **adjazent**). Dabei wird eine Art Tabelle aufgestellt, deren Spalten- und Zeilenanzahl der Anzahl der Knoten entspricht (die im Folgenden verwendeten Zeilen- und Spaltenbeschriftungen sind nicht Teil der Adjazenzmatrix und dienen nur der Veranschaulichung). Die Adjazenzmatrix enthält dann als Eintrag
   * 0, wenn es keine Kante zwischen dem links stehenden und dem oben stehenden Knoten gibt   * 0, wenn es keine Kante zwischen dem links stehenden und dem oben stehenden Knoten gibt
   * 1, wenn es eine Kante zwischen den Knoten gibt und der Graph ungewichtet ist   * 1, wenn es eine Kante zwischen den Knoten gibt und der Graph ungewichtet ist
Zeile 7: Zeile 7:
 </WRAP> </WRAP>
  
-==== Beispiel 2 ====+==== Beispiel 1 ====
 (Adjazenzmatrix eines gerichteten Graphen) \\  (Adjazenzmatrix eines gerichteten Graphen) \\ 
 {{ :graphen:pasted:20211106-152817.png?200}} {{ :graphen:pasted:20211106-152817.png?200}}
Zeile 15: Zeile 15:
 ^ Knoten 3 | 0 | 0 | 0 | ^ Knoten 3 | 0 | 0 | 0 |
  
-==== Beispiel 3 ====+==== Beispiel 2 ====
 {{ :graphen:pasted:20211106-153459.png?200}} {{ :graphen:pasted:20211106-153459.png?200}}
 ^ ^ Knoten 1 ^ Knoten 2 ^ Knoten 3 ^ ^ ^ Knoten 1 ^ Knoten 2 ^ Knoten 3 ^
Zeile 23: Zeile 23:
 Die Adjazenzmatrix eines ungerichteten Graphen ist immer **symmetrisch bzgl. der Diagonale** von links oben nach rechts unten. Die Adjazenzmatrix eines ungerichteten Graphen ist immer **symmetrisch bzgl. der Diagonale** von links oben nach rechts unten.
  
-==== Aufgabe 4 ====+==== Aufgabe 1 ====
 Modellieren Sie den folgenden Graphen als Adjazenzmatrix. Modellieren Sie den folgenden Graphen als Adjazenzmatrix.
 {{ :graphen:20211107-152623.png?400 |}} {{ :graphen:20211107-152623.png?400 |}}
 [[..aufgabe4loesung:start|Lösung]] [[..aufgabe4loesung:start|Lösung]]
-==== Aufgabe 5 ====+==== Aufgabe 2 ====
 Zeichne eine graphische Darstellung des durch die folgende Adjazenzmatrix gegebenen Graphen: Zeichne eine graphische Darstellung des durch die folgende Adjazenzmatrix gegebenen Graphen:
  
 ^   ^ A ^ B ^ C ^ D ^ E ^ ^   ^ A ^ B ^ C ^ D ^ E ^
-| A |   | 8 |   | 5 |   | +| A | 0 | 8 | 0 | 5 | 0 | 
-| B |   |   | 6 |   |   | +| B | 0 | 0 | 6 | 0 | 0 | 
-| C |   | 2 |   | 4 | 1 | +| C | 0 | 2 | 0 | 4 | 1 | 
-| D | 5 |   |   |   |   | +| D | 5 | 0 | 0 | 0 | 0 | 
-| E |   |   | 4 |   |   |+| E | 0 | 0 | 4 | 0 | 0 |
  
 [[..aufgabe5loesung:start|Lösung]] [[..aufgabe5loesung:start|Lösung]]
 +
 +==== Aufgabe 3 ====
 +Ein Graph ist durch die folgende Adjazenzmatrix gegebenen:
 +
 +^   ^ A ^ B ^ C ^ D ^ E ^
 +| A | 1 | 0 | 1 | 1 | 0 |
 +| B | 0 | 0 | 0 | 0 | 0 |
 +| C | 1 | 0 | 1 | 0 | 0 |
 +| D | 0 | 0 | 0 | 0 | 1 |
 +| E | 0 | 0 | 1 | 0 | 0 |
 +
 +**Bewerten Sie die Aussagen:**
 +  * Der Graph ist gewichtet.
 +  * Der Graph ist gerichtet.
 +  * Es gibt einen Pfad von D nach A.
 +  * Der Graph ist zyklisch.
 +  * Es gibt mindestens einen Knoten, der eine Kante auf sich selbst hat (d.h. eine Kante, die von diesem Knoten ausgeht und auf diesen Knoten zeigt).
 +  * Es gibt einen isolierten Knoten.
 +
 +[[..aufgabe3loesunga:startx|Lösung]]
 +
 +
 ===== Modellierung von Graphen durch Adjazenzmatrizen ===== ===== Modellierung von Graphen durch Adjazenzmatrizen =====
 Graphen werden in Java-Programmen oft implementiert, indem man ihre Adjazenzmatrix in einem zweidimensionalen Integer-Array speichert. Graphen werden in Java-Programmen oft implementiert, indem man ihre Adjazenzmatrix in einem zweidimensionalen Integer-Array speichert.
Zeile 50: Zeile 72:
 </code> </code>
 Falls Du Dein Wissen über Arrays auffrischen möchtest, [[https://learnj.de/doku.php?id=types:arrays:start|schau' Dir die Wiki-Seite aus Jgst. 10 dazu an!]] \\ \\  Falls Du Dein Wissen über Arrays auffrischen möchtest, [[https://learnj.de/doku.php?id=types:arrays:start|schau' Dir die Wiki-Seite aus Jgst. 10 dazu an!]] \\ \\ 
-Hier zur Wiederholung eine [[.fingeruebungarrays:start|kleine Fingerübung zu eindimensionalen Arrays]] (Umkehrung eines Arrays). \\ +Hier zur Wiederholung eine [[..fingeruebungarrays:start|kleine Fingerübung zu eindimensionalen Arrays]] (Umkehrung eines Arrays). \\ 
 Ein **zweidimensionales** Array speichert "ein Schachbrett voller Zahlen". Die Speicherung von bspw. $4 \times 3$ Zahlen geht so: Ein **zweidimensionales** Array speichert "ein Schachbrett voller Zahlen". Die Speicherung von bspw. $4 \times 3$ Zahlen geht so:
 <code> <code>
graphen/adjazenzmatrix/start.1697180918.txt.gz · Zuletzt geändert: 2023/10/13 07:08 von Martin Pabst
Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki