Beide Seiten der vorigen Revision Vorhergehende Überarbeitung Nächste Überarbeitung | Vorhergehende ÜberarbeitungLetzte ÜberarbeitungBeide Seiten der Revision |
faecher:informatik:oberstufe:graphen:graphen:einfuehrung [18.03.2022 09:55] – [Eigenschaften von Graphen] Mareike Nutz | faecher:informatik:oberstufe:graphen:graphen:einfuehrung [18.03.2022 11:31] – Mareike Nutz |
---|
**Knotengrad** | **Knotengrad** |
| |
Der Grad eines Knotens (Knotengrad) ist die Anzahl der Kanten, die in diesem Knoten zusammentreffen. Im Graph rechts hat der Knoten a den Grad 2, der Knoten b den Grad 1, c den Grad 4, d den Grad 2 und der Knoten e den Grad 3. | Der Grad eines Knotens (Knotengrad) ist die Anzahl der Kanten, die in diesem Knoten zusammentreffen. Im Graph rechts hat der Knoten **a** den Grad 2, der Knoten **b** den Grad 1, **c** den Grad 4, **d** den Grad 2 und der Knoten **e** den Grad 3. |
| |
{{:aufgabe.png?nolink |}} (3) Ermittle den Grad aller Knoten des sechsten Levels aus dem Spiel "Auf den Spuren eines Handelsreisenden". | {{:aufgabe.png?nolink |}} (3) Ermittle den Grad aller Knoten des sechsten Levels aus dem Spiel "Auf den Spuren eines Handelsreisenden". |
**Zusammenhängende Graphen** | **Zusammenhängende Graphen** |
| |
Ein Graph heißt zusammenhängend, wenn man entlang der Kanten von jedem Knoten zu einem anderen gelangen kann. Der Graph G auf der rechten Seite ist nicht zusammenhängend. Von Knoten a kann der Knoten e nicht erreicht werden. | Ein Graph heißt zusammenhängend, wenn man entlang der Kanten von jedem Knoten zu einem anderen gelangen kann. Der Graph **G** auf der rechten Seite ist nicht zusammenhängend. Von Knoten **a** kann der Knoten **e** nicht erreicht werden. |
| |
| {{:aufgabe.png?nolink |}} (6) Ergänze den Graphen G, sodass er zusammenhängend ist. |
| |
{{ :faecher:informatik:oberstufe:graphen:graphen:zusammenhaengender.drawio.png?500 |}} | {{ :faecher:informatik:oberstufe:graphen:graphen:zusammenhaengender.drawio.png?500 |}} |
{{ :faecher:informatik:oberstufe:graphen:graphen:zyklen.drawio.png?800 |}} | {{ :faecher:informatik:oberstufe:graphen:graphen:zyklen.drawio.png?800 |}} |
| |
{{:aufgabe.png?nolink |}} (6) Zeichne im Graphen aus Aufgabe (1) den Pfad ''p = (1,8),(8,42),(42,3),(3,29),(29,8)'' ein. Handelt es sich um einen einfachen oder einen zyklischen Pfad? Erkläre. | {{:aufgabe.png?nolink |}} (7) Zeichne im Graphen aus Aufgabe (1) den Pfad ''p = (1,8),(8,42),(42,3),(3,29),(29,8)'' ein. Handelt es sich um einen einfachen oder einen zyklischen Pfad? Erkläre. |
| |
Ein Zyklus, der jeden Knoten eines Graphen genau einmal enthält, heißt **Hamilton-Kreis**. Dieses Begriff habt ihr im Spiel bereits unter dem Namen "Rundreise" kennengelernt. | Ein Zyklus, der jeden Knoten eines Graphen genau einmal enthält, heißt **Hamilton-Kreis**. Dieses Begriff habt ihr im Spiel bereits unter dem Namen "Rundreise" kennengelernt. |
| |
{{:aufgabe.png?nolink |}} (7) Findest du jeweils alle Hamilton-Kreise in diesen Graphen? Zeichne sie in dein Heft. | {{:aufgabe.png?nolink |}} (8) Findest du jeweils alle Hamilton-Kreise in diesen Graphen? Zeichne sie in dein Heft. |
{{ :faecher:informatik:oberstufe:graphen:graphen:hamilton_ueb1.png?600 |}} | {{ :faecher:informatik:oberstufe:graphen:graphen:hamilton_ueb1.png?600 |}} |
<sup>Quelle: https://lehrerfortbildung-bw.de/u_matnatech/imp/gym/bp2016/fb1/6_m2_aug/2_kopiervorlagen/3_hamilton/1_uebung/hamilton_ueb1.png</sup> | <sup>Quelle: https://lehrerfortbildung-bw.de/u_matnatech/imp/gym/bp2016/fb1/6_m2_aug/2_kopiervorlagen/3_hamilton/1_uebung/hamilton_ueb1.png</sup> |
| |
{{:aufgabe.png?nolink |}} | {{:aufgabe.png?nolink |}} |
==== (8) Graphen in "Auf den Spuren eines Handelsreisenden" ==== | ==== (9) Graphen in "Auf den Spuren eines Handelsreisenden" ==== |
Im Spiel "Auf den Spuren eines Handelsreisenden" habt ihr in jedem Level auf verschiedenen Beispielen von Graphen gespielt. Auf dieser Seite habt ihr erfahren, was die Datenstruktur Graph genau ist, welche Eigenschaften Graphen haben sowie welche Wege auf Graphen gegangen werden können. Beschreibe, welche Elemente von Graphen im Spiel zu finden sind und welche Eigenschaften diese Graphen haben. | Im Spiel "Auf den Spuren eines Handelsreisenden" habt ihr in jedem Level auf verschiedenen Beispielen von Graphen gespielt. Auf dieser Seite habt ihr erfahren, was die Datenstruktur Graph genau ist, welche Eigenschaften Graphen haben sowie welche Wege auf Graphen gegangen werden können. Beschreibe, welche Elemente von Graphen im Spiel zu finden sind und welche Eigenschaften diese Graphen haben. |
| |
| |
{{:aufgabe.png?nolink |}} | {{:aufgabe.png?nolink |}} |
==== (9) Zusatzaufgabe: TSP ==== | ==== (10) Zusatzaufgabe: TSP ==== |
| |
Herr Schnell muss Waren ausliefern. Er startet bei seiner Spedition in A, muss dann jede der Städte B,C und D genau einmal anfahren und wieder zur Spedition in A zurückkehren. Die Entfernungen sind in der Tabelle (in km) angegeben. | Herr Schnell muss Waren ausliefern. Er startet bei seiner Spedition in A, muss dann jede der Städte B,C und D genau einmal anfahren und wieder zur Spedition in A zurückkehren. Die Entfernungen sind in der Tabelle (in km) angegeben. |