Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung Nächste Überarbeitung | Vorherige Überarbeitung Nächste ÜberarbeitungBeide Seiten, nächste Überarbeitung | ||
faecher:informatik:oberstufe:graphen:zpg:einfuehrung:start [09.11.2022 17:29] – Frank Schiebel | faecher:informatik:oberstufe:graphen:zpg:einfuehrung:start [09.11.2022 17:36] – [Definition: Graph?] Frank Schiebel | ||
---|---|---|---|
Zeile 17: | Zeile 17: | ||
* Entscheide, ob es eine derartige Rundtour gibt. Gib die Rundtour gegebenenfalls an. | * Entscheide, ob es eine derartige Rundtour gibt. Gib die Rundtour gegebenenfalls an. | ||
* Entscheide, ob es möglich ist, eine einzige Strecke zu fahren, bei der jede Route genau einmal bedient wird. Gib an, von welchen Häfen aus dies möglich ist. | * Entscheide, ob es möglich ist, eine einzige Strecke zu fahren, bei der jede Route genau einmal bedient wird. Gib an, von welchen Häfen aus dies möglich ist. | ||
- | * (**) Kannst du angeben, unter welchen Voraussetzungen es eine Rundtour (Starthafen = Zielhafen) gibt, die alle Routen genau einmal abfährt? | + | * Kannst du angeben, unter welchen Voraussetzungen es eine Rundtour (Starthafen = Zielhafen) gibt, die alle Routen genau einmal abfährt? |
++++ Lösungen | | ++++ Lösungen | | ||
Zeile 44: | Zeile 44: | ||
++++ | ++++ | ||
- | Zur Modellierung kommt also ein Modell zum Einsatz, welches die **Häfen** und die **Verbindungen zwischen den Häfen** umfassen muss. Allgemeiner kann man davon sprechen, dass man Knoten modellieren möchte, deren Verbindung | + | Zur Modellierung kommt also ein Modell zum Einsatz, welches die **Häfen** und die **Verbindungen zwischen den Häfen** umfassen muss. Allgemeiner kann man davon sprechen, dass man **Knoten** modellieren möchte, deren Verbindungen |
Für unser Archipel sieht das so aus: | Für unser Archipel sieht das so aus: | ||
Zeile 50: | Zeile 50: | ||
{{ : | {{ : | ||
+ | Die Anordnung der Elemente auf der Zeichenfläche spielt dabei überhaupt keine Rolle, solange die Kanten und ihre Verbindungen gleich bleiben, modellieren wir dasselbe Archipel: | ||
+ | {{ : | ||
+ | |||
+ | |||
+ | ===== Definition: | ||
+ | |||
+ | {{ : | ||
+ | |||
+ | <WRAP center round important 90%> | ||
+ | Wichtig-Box | ||
+ | |||
+ | |||
+ | |||
+ | Ein Graph ist ein Gebilde, das aus Knoten und Kanten besteht. Jede Kante verbindet zwei Knoten oder einen Knoten mit sich selbst. Von einem Knoten können eine, mehrere oder keine Kanten ausgehen. | ||
+ | Formal schreibt man: | ||
+ | |||
+ | Graph '' | ||
+ | </ | ||