Barion Pixel Was wir über Graphen wissen sollten | MATHEKING
 
Graphen, Einfache Graphen, Knoten, Kanten, Pfad, Kreis, Zusammenhängende Graphen, Isolierter Punkt, Zyklenfreie Graphen, Baum
Text of slideshow
Was wir über Graphen wissen sollten Jeder von uns hat in seinem Leben bereits Graphen gesehen. Diese U-Bahn-Karte ist zum Beispiel ein Graph. Ein Graph besteht aus Knoten, die durch Kanten verbunden sind. Die Knoten sind hier die U-Bahn-Stationen. Die Kanten des Graphen sind die U-Bahn-Verbindungen zwischen den Haltestellen. Wenn wir von einer beliebigen Haltestelle aus alle anderen Haltestellen erreichen können, dann ist der Graph zusammenhängend. Diese Wege innerhalb des Graphen nennen wir Pfade. Ein Graph ist zusammenhängend, wenn alle Kombinationen von zwei Knoten durch einen Pfad verbunden sind. Gibt es zwei Knoten, die nicht durch einen Pfad verbunden sind, ist der Graph nicht zusammenhängend. Dann müssen wir auf Ersatzbusse ausweichen … Sehen wir uns nun an, in wie viele Richtungen wir an einem bestimmten Knoten losfahren können. Das nennen wir die Gradzahl des Knotens. Und jetzt kommen wir zu einem weiteren spannenden Gebilde: dem Zyklus. Der Zyklus ist ein Pfad, der über lauter verschiedene Knoten und Kanten zum Ausgangsknoten zurückführt. Ob es noch weitere Zyklen gibt? Natürlich. Wenn ein Graph keinen Zyklus enthält, aber zusammenhängend ist, wird er Baum genannt. Wenn wir aus unserem U-Bahn-Netz die überflüssigen Verbindungen entfernen, erhalten wir einen Baum. Dann gibt es immer nur genau eine Möglichkeit, von einer Haltestelle zu einer anderen zu kommen. Für die Reisenden ist das zwar nicht immer praktisch, die U-Bahn kann günstiger gebaut werden, denn es werden alle überflüssigen Parallelverbindungen eingespart. Wollten wir den Reisenden maximalen Komfort bieten, müssten wir jede Haltestelle mit jeder anderen Haltestelle direkt verbinden. Aber das können wir nicht einmal richtig einzeichnen, geschweige denn bauen. Einen Graphen, bei dem jeder Knoten mit jedem anderen Knoten verbunden ist, nennen wir einen vollständigen Graphen. Ein vollständiger Graph mit vier Knoten: Ein vollständiger Graph mit fünf Knoten: Hier sind ein paar unterschiedliche Graphen. Sehen wir mal, um welche Arten es sich handelt. Da jeder Baum zusammenhängend und zyklenfrei ist, sieht die Situation eher so aus: Diese Graphen zählen allesamt zu den sogenannten einfachen Graphen. Ein Graph ist dann nicht einfach, wenn er über eine der folgenden Besonderheiten verfügt: Mehrfachkante Schleife Zu Beginn einer Sitzung schüttelt jeder Teilnehmer allen anderen Teilnehmern die Hand. Dabei gibt jeder Teilnehmer vier Personen die Hand. Wie viele Personen nehmen an der Sitzung teil und wie viele Handschläge gab es insgesamt? Da jeder Teilnehmer vier anderen Personen die Hand gibt, sieht der Graph in etwa so aus: Der Graph hat fünf Knoten, also nehmen an der Sitzung fünf Personen teil. Jeder Knoten hat die Gradzahl 4. Wenn wir bei einem Graphen die Gradzahlen der Knoten zusammenzählen, zählen wir jede Kante genau zweimal. Einmal bei dem einen Knoten … und einmal beim anderen. Es gibt also halb so viele Kanten wie die Summe der Knotengrade: Es gab also insgesamt 10 Handschläge. Am besten merken wir uns Folgendes: Kantenzahl eines vollständigen Graphen mit n Knoten: Bei einem Schülerwettkampf treten Anna, Berto, Cedric, David, Emil, Fritzi, Gabi und Hanna gegeneinander an. Jeder spielt genau einmal gegen alle anderen. Anna hat bereits gegen Berto, Gabi und Hanna gespielt. Berto hat gegen Anna, Cedric und Gabi gespielt. Cedric hat nur gegen Berto, und David nur gegen Emil gespielt. Zeichnen wir einen Graphen, der den aktuellen Stand darstellt. Wie viele Spiele stehen noch aus? Der Graph hat insgesamt 6 Kanten. Das heißt, 6 Spiele haben bereits stattgefunden. Da jeder einmal gegen jeden spielt, wird das ein vollständiger Graph. Die Kantenzahl eines vollständigen Graphen mit 8 Knoten beträgt: Somit stehen noch 28–6=22 Spiele aus. Ein vollständiger Graph soll die fünf Knoten A, B, C, D, E haben. a) Welche Gradzahl hat der Knoten B? b) Wenn wir aus dem Graphen zwei Kanten entfernen, welche Gradzahlen können sich für B ergeben? c) Wie ändert sich die Summe der Knotengrade, nachdem wir die beiden Kanten aus dem Graphen entfernt haben? d) Wie viele Kanten müssen wir entfernen, damit jeder Knoten die Gradzahl 3 hat? Die Summe der Knotengrade beträgt derzeit: Beim Entfernen einer Kante nimmt die Summe der Knotengrade immer um 2 ab, denn es sind immer zwei Knoten betroffen. Wenn wir eine weitere Kante wegnehmen, reduziert sich erneut die Gradzahl zweier Knoten jeweils um 1. Durch Entfernen von zwei Kanten reduziert sich also die Summe der Knotengrade um 4. Nach Entfernen der zwei Kanten beträgt die Gradzahl also 20–4=16. Löschen wir als Erstes zum Beispiel die Kante zwischen A und B. Damit haben A und B auch schon die richtige Gradzahl. Löschen wir nun eine von C ausgehende Kante. Diese können wir nicht löschen, denn dann hätte B die falsche Gradzahl. Und so hätte A die falsche Gradzahl. Löschen wir also die Kante zwischen C und E. Jetzt stimmen alle Knoten bis auf D, allerdings bekommen wir hier ein Problem. Egal welche aus D ausgehende Kante wir weglassen, reduzieren wir damit die Gradzahl eines anderen Knotens auf 2. Es kann also nicht jeder Knoten die Gradzahl 3 haben. Es ist nämlich so, dass in einem Graphen die Summe der Knotengrade immer der doppelten Kantenzahl entspricht. Wenn in einem solchen Graphen jeder Knoten die Gradzahl 3 hat, beträgt die Summe der Knotengrade: Aber als ungerade Zahl kann das nicht der doppelten Kantenzahl entsprechen.
 

Was wir über Graphen wissen sollten

02
Auf zum
Tutorial Mathematik Mittelschule.
Jetzt sind Sie dran. Lösen Sie die Aufgabe alleine und überprüfen Sie die Lösung anschließend in diesem Video!
Wir zeigen dir, wie die Seite funktioniert!
LoginaberRegistrieren Back arrow Alle Episoden
aus diesem Thema