Flugverbindungen als Graphen

Lösungen zu den Aufgaben

1. Graph

2. Typ des Graphen

Es handelt sich um einen gerichteten, ungewichteten Graphen.

3. Adjezenzmatrix

4. Zusammenhängender Graph?

Der Graph ist nicht stark zusammenhängend, da von London aus keine Kanten ausgehen - die Zeile in der Matrix enthält nur 0 als Eintragungen. Von London aus ist damit kein anderer Knoten erreichbar. Er ist schwach zusammenhängend, da in einem ungerichteten Graphen jeder Knoten von jedem anderen Knoten erreicht werden kann. In der Matrix gibt es in jeder Spalte mindestens eine 1, d.h. jeder Knoten kann von einem anderen erreicht werden.

5. Kanten, die von M ausgehen

Die Kanten zu den Zielen stehen in der Matrix in einer Zeile.

6. Kanten, die in M enden

Die Kanten von den Startorten stehen in der Matrix in einer Spalte.

7. Das Feld knoten

private String[] knoten = {"M","F","H","P","L"};

8. Das Feld kanten

private int[][] kanten = {
  {0,1,0,0,0},
  {1,0,1,1,0},
  {1,0,0,0,0},
  {0,0,0,0,1},
  {0,0,0,0,0}
};

9. Alle kanten, die von start ausgehen

kanten[start][0]
kanten[start][1]
kanten[start][2]
kanten[start][3]
kanten[start][4]

10. Alle Kanten, die in ziel enden

kanten[0][ziel] kanten[1][ziel] kanten[2][ziel] kanten[3][ziel] kanten[4][ziel]

11. Methode printKantenZiel

public void printKantenZiel(int start){
  for (int ziel=0;ziel<knoten.length;ziel++){
    print(kanten[start][ziel]);
  }
  println();
}

12. Methode printKantenStart

public void printKantenStart(int ziel){
  for (int start=0;start<knoten.length;start++){
    print(kanten[start][ziel]);
  }
  println();
}

13. Verbesserte Methode printKantenZiel

public void printKantenZiel(int start){
  print("Kanten gehen von ");
  print(knoten[start]);
  print(" nach ");
  for (int ziel=0;ziel<knoten.length;ziel++){
    if (kanten[start][ziel]>0){
       print(knoten[ziel]);
       print(", ");
    }
  }
  println();
}

14. Verbesserte Methode printKantenStart

public void printKantenStart(int ziel){
  print("Kanten enden in ");
  print(knoten[ziel]);
  print(" aus ");
  for (int start=0;start<knoten.length;start++){
    if (kanten[start][ziel]>0){
       print(knoten[start]);
       print(", ");
    }
  }
  println();
}

weiter

Index