Informatik 11

Diese Seite ist nicht editierbar. Sie können den Quelltext sehen, jedoch nicht verändern. Kontaktieren Sie den Administrator, wenn Sie glauben, dass hier ein Fehler vorliegt.
====== Adjazenzmatrix ======
<WRAP center round info 80%>
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
  * 1, wenn es eine Kante zwischen den Knoten gibt und der Graph ungewichtet ist
  * ansonsten das Kantengewicht
</WRAP>

==== Beispiel 1 ====
(Adjazenzmatrix eines gerichteten Graphen) \\ 
{{ :graphen:pasted:20211106-152817.png?200}}
^ ^ Knoten 1 ^ Knoten 2 ^ Knoten 3 ^
^ Knoten 1 | 0 | 0 | 1 |
^ Knoten 2 | 1 | 0 | 0 |
^ Knoten 3 | 0 | 0 | 0 |

==== Beispiel 2 ====
{{ :graphen:pasted:20211106-153459.png?200}}
^ ^ Knoten 1 ^ Knoten 2 ^ Knoten 3 ^
^ Knoten 1 | 0 | 22 | 17 |
^ Knoten 2 | 22 | 0 | 0 |
^ Knoten 3 | 17 | 0 | 0 |
Die Adjazenzmatrix eines ungerichteten Graphen ist immer **symmetrisch bzgl. der Diagonale** von links oben nach rechts unten.

==== Aufgabe 1 ====
Modellieren Sie den folgenden Graphen als Adjazenzmatrix.
{{ :graphen:20211107-152623.png?400 |}}
[[..aufgabe4loesung:start|Lösung]]
==== Aufgabe 2 ====
Zeichne eine graphische Darstellung des durch die folgende Adjazenzmatrix gegebenen Graphen:

^   ^ A ^ B ^ C ^ D ^ E ^
| A | 0 | 8 | 0 | 5 | 0 |
| B | 0 | 0 | 6 | 0 | 0 |
| C | 0 | 2 | 0 | 4 | 1 |
| D | 5 | 0 | 0 | 0 | 0 |
| E | 0 | 0 | 4 | 0 | 0 |

[[..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 =====
Graphen werden in Java-Programmen oft implementiert, indem man ihre Adjazenzmatrix in einem zweidimensionalen Integer-Array speichert.
<WRAP center round info 60%>
**Zweidimensionales int-Array?** \\ \\ 
Du erinnerst Dich vielleicht noch an eindimensionale Arrays, z.B.
<code java>
int[] zahlen = new int[7];   //Das Array zahlen enthält 7 Elemente: zahlen[0] bis zahlen[6].
zahlen[0] = 12;              // speichert im ersten Element die Zahl 12
zahlen[5] = 4;               // speichert im 6. Element die Zahl 4;
println(zahlen[5]);   // Gibt das 6. Element aus
</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!]] \\ \\ 
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:
<code>
int[][] zahlen = new int[4][3];    // Der erste Index geht von 0 bis 3, der zweite von 0 bis 2
zahlen[2][1] = 10;
zahlen[0][2] = 14;
</code>
Man kann sich vorstellen, dass das Array ''zahlen'' aufgebaut ist wie ein Schachbrett. Der erste Index bezeichnet die Zeile des Feldes, der zweite die Spalte. Nach Ablauf dieses Programms sieht die Belegung des Arrays so aus:
^**zahlen**^**0**^**1**^**2**^
^**0**|0|0|14|
^**1**|0|0|0|
^**2**|0|10|0|
^**3**|0|0|0|
Im Array gespeichert sind natürlich nur die 12 Werte der blauen Zellen. Die fettgedruckten Zeilen- bzw. Spaltenköpfe dienen nur zur Veranschaulichung. 
</WRAP>

==== Beispiel 4 - Speicherung eines gerichteten Graphen ====
{{ :graphen:pasted:20211106-171626.png?300}}
Das folgende Programm speichert den Graphen rechts als Adjazenzmatrix:
<HTML>

<div class="java-online" style="height: 350px; width: 60%" data-java-online="{'withBottomPanel': false, 'id': 'Graph1'}">

<script type="text/plain" title="Graph 1.java">
int[][] matrix = new int[4][4];
matrix[0][1] = 1;
matrix[1][0] = 1;
matrix[1][2] = 1;
matrix[2][3] = 1;
matrix[3][1] = 1;

for(int i = 0; i < 4; i++) {
   for(int j = 0; j < 4; j++) {
      print(matrix[i][j] + " ");
   }
   println();
}
</script>

</div>
</HTML>

===== Die Klasse Graph =====
Wir entwickeln eine Klasse ''Graph'', die nützliche Methoden zur Verwaltung und Analyse von Graphen bereitstellt.

<WRAP center round tip 80%>
{{ :graphen:20211107-152623.png?200|}}
Den im Testprogramm unten generierten Graphen siehst Du in graphischer Darstellung im Bild rechts.
</WRAP>


<HTML>
<div class="java-online" style="height: 70vh; width: 100%" data-java-online="{'withBottomPanel': true, 'id': 'Graph2'}">

<script type="text/plain" title="Graph.java">
public class Graph {
   private int[][] adj;

   public Graph(int anzahlKnoten) {
      adj = new int[anzahlKnoten][anzahlKnoten];
   }
    
   public void kanteHinzufügen(int vonIndex, int nachIndex) {
      adj[vonIndex][nachIndex] = 1;
   }
    
   public boolean istDirektVerbunden(int vonIndex, int nachIndex) {
      return adj[vonIndex][nachIndex] > 0;
   }
}
</script>

<script type="text/plain" title="Testprogramm.java">
Graph g = new Graph(8);
g.kanteHinzufügen(0, 1);
g.kanteHinzufügen(1, 0);
g.kanteHinzufügen(1, 2);
g.kanteHinzufügen(2, 3);
g.kanteHinzufügen(3, 4);
g.kanteHinzufügen(2, 4);
g.kanteHinzufügen(4, 2);
g.kanteHinzufügen(3, 5);
g.kanteHinzufügen(5, 2);
g.kanteHinzufügen(5, 6);
g.kanteHinzufügen(1, 6);
g.kanteHinzufügen(6, 7);
g.kanteHinzufügen(7, 0);

println(g.istDirektVerbunden(4, 1));
println(g.istDirektVerbunden(2, 4));
</script>


</div>
</HTML>

<WRAP center round todo 80%>
**Aufgaben:** \\ \\ 
  * Erstelle eine Methode ''void adjazenzmatrixAusgaben()'', die die Adjazenzmatrix folgendermaßen auf dem Bildschirm ausgibt:
<code>
0 1 0
1 0 1
0 1 0
</code>
  * Erstelle eine Methode ''istIsoliert(int knoten)'', die genau dann ''true'' zurückgibt, wenn der Knoten isoliert ist (Definition siehe oben).

</WRAP>