faecher:informatik:oberstufe:graphen:zpg:eulerzug:start []

Diese Seite ist nicht editierbar. Du kannst den Quelltext sehen, jedoch nicht verändern. Kontaktiere den Administrator, wenn du glaubst, dass hier ein Fehler vorliegt.

====== Hat ein gegebener Graph einen Eulerkreis? ======

Um entscheiden zu können, ob ein gegebener Graph einen Eulerkreis besitzt oder nicht, müssen wir zwei Kriterien überprüfen: 

  * Alle Knotengrade müssen gerade sein
  * Der Graph muss zusammenhängen

===== Die Froschperspektive =====

Bei Algorithmen, die auf Graphen operieren, müssen wir einen Perspektivwechsel vornehmen: Wir sehen einen Graphen aus der "Vogelperspektive", d.h. wir nehmen den gesamten Graphen mit all seinen Knoten und Kanten wahr und lassen dann nur unsere Augen wandern - wenn uns eine Information fehlt, schauen wir einfach an die entscheidende Stelle und das Problem ist gelöst.

{{ :faecher:informatik:oberstufe:graphen:zpg:eulerzug:auswahl_379.png |}} 

Wenn wir einen Graphen algorithmisch verarbeiten wollen, müssen wir schrittweise durch die Knotenanordnung wandern - wir sehen niemals weiter als bis zum Ende der nächsten Kante. Wir müssen also die **Frosch-Perspektive** einnehmen. 

{{ :faecher:informatik:oberstufe:graphen:zpg:eulerzug:auswahl_380.png |}}

===== Überprüfung des Knoten-Grades =====

<code>
Setze gradOK auf true
Für jeden Knoten k:
   Wenn Grad(k) ungerade, setze gradOK auf false
</code>

{{ :faecher:informatik:oberstufe:graphen:zpg:eulerzug:auswahl_381.png?700 |}}


===== Überprüfung des Zusammenhangs =====

Aus der Vogelperspektive ist das sofort klar - dieser Graph hängt nicht zusammen:

{{ :faecher:informatik:oberstufe:graphen:zpg:eulerzug:auswahl_383.png |}}

Der Frosch ist allerdings etwas ratlos: 

{{ :faecher:informatik:oberstufe:graphen:zpg:eulerzug:auswahl_384.png |}}


----
{{:aufgabe.png?nolink  |}}
=== (A1) ===
Finde eine algorithmische Vorgehensweise, wie der Frosch herausfinden kann, ob der Graph zusammenhängend ist. Um dieses Ziel zu erreichen, hat der Frosch die folgenden Werkzeuge und Fähigkeiten zur Verfügung:

Der Frosch kann...
  - Knoten / Kanten markieren 
  - Bei Knoten eine Zahl eintragen 
  - Knoten einfärben 
  - Alle Knoten der Reihe nach durchgehen
  - Einen beliebigen Knoten als Startknoten wählen
  - Zum Nachbarknoten springen
  - Eine ToDo-Liste noch zu bearbeitender Knoten anlegen


Lade dir den [[https://codeberg.org/qg-info-unterricht/zpg-graphentester|Graphentester herunter]] und versuche im Experimentiermodus einen Algorithmus zu finden, der herausfindet, ob ein gegebener Graph zusammenhängend ist oder nicht.

Notiere den Algorithmus als Text oder in Pseudocode.

++++ Hilfestellung 1 |

Man startet bei einem beliebigen Knoten. Diesem gibt man die Nummer 1 und **markiert** ihn als
fertig bearbeitet (''Markieren'' & ''Besuchen'').

Alle seine Nachbarknoten fügt man einer ToDo-Liste hinzu und kennzeichnet
sie mit ''Besuchen'', um auszudrücken, dass sie der ToDo-Liste schon hinzugefügt, aber noch nicht
fertig bearbeitet ("besucht") sind.

Dann nimmt man den nächsten Knoten aus der ToDo-Liste, nummeriert ihn und markiert ihn als
fertig bearbeitet. Alle seine **nicht** als **besucht** oder **fertig** bearbeitet gekennzeichneten Nachbarn
fügt man der ToDo-Liste hinzu und kennzeichnet sie als **besucht**.

Diese Schritte werden so lange wiederholt, bis die ToDo-Liste leer ist.

Entspricht die Nummer des zuletzt nummerierten Knotens der Anzahl der Knoten im Graph, ist
der Graph zusammenhängend. Ist sie kleiner, hat man nicht alle Knoten erreicht und der Graph
besteht aus mehreren Zusammenhangskomponenten.

Varianten:
Beim Einfügen in die ToDo-Liste können neue Knoten entweder am Anfang der Liste oder am
Ende der Liste eingefügt werden.

++++


++++ Hilfestellung 2 |
== Pseudocode des Algorithmus, um den Zusammenhang zu testen ==


Der hier beschriebene Algorithmus bestimmt die Anzahl der vom Startknoten aus erreichbaren
Knoten und vergleicht sie mit der Gesamtzahl der Knoten.
<code>
Zusammenhang des Graphen:
Markiere den Startknoten als besucht
Erzeuge eine leere ToDo-Liste und füge den Startknoten hinzu
Setze nr auf 0

Wiederhole solange die ToDo-Liste nicht leer ist
  Erhöhe nr um 1
  Nimm den ersten Knoten aus der ToDo-Liste heraus
  Markiere ihn und gib ihm die Nummer nr

  Wiederhole für jeden seiner Nachbarn
    Falls der Nachbarknoten noch nicht besucht ist
      Kennzeichne ihn als "besucht"
      Füge ihn am Ende der ToDo-Liste hinzu
    Ende-Falls
  Ende-Wiederhole
Ende-Wiederhole

Falls nr = Anzahl der Knoten im Graph
  Der Graph ist zusammenhängend
Sonst
  Es gibt mehrere Zusammenhangskomponenten
Ende-Falls
</code>

Variante: Statt am Ende der ToDo-Liste können die Nachbarn auch am Anfang der ToDo-Liste
eingefügt werden.

++++




==== Dateien ====

{{simplefilelist>:faecher:informatik:oberstufe:graphen:zpg:eulerzug:*}}