Mengen und Graphen

Inhalt des Themas


Mengen, Schnitte, Vereinigungen und Konsorten
Mengen, Schnitte, Vereinigungen und Konsorten Wenn wir eine Menge A haben, dann ist das deren Komplement: alles, was um sie herum ist. Interessanter wird es dann, wenn Menge A Gesellschaft bekommt: die Menge B. Komplement der Menge A: Der Teil, der in beiden Mengen enthalten ist, ist die Schnittmenge der Mengen A und B (auch Schnitt oder Durchschnitt genannt). Schnitt der Mengen A und B: Und das ist die Vereinigung der Mengen A und B. Vereinigung der Mengen A und B: Und wenn wir eine Schere nehmen und aus Menge A fein säuberlich jenen Teil ausschneiden, der auch in B enthalten ist, dann erhalten wir die Differenz der beiden Mengen (auch Restmenge genannt). Differenz der Mengen A und B: Jetzt kommen wir zum Begriff der Teilmenge. Eine Teilmenge von A ist zum Beispiel die Menge der geraden Zahlen: Eine weitere Teilmenge ist die Menge der ungeraden Zahlen: Die Menge der durch 3 teilbaren Zahlen ist ebenfalls eine Teilmenge von A: Nehmen wir mal die folgenden Mengen A und B: Bestimmen wir … a) den Schnitt der beiden Mengen b) die Vereinigung der beiden Mengen c) B\A Eine Versicherung erhielt in einem Monat Kfz-Schadensmeldungen von 24 Versicherten. 8 von diesen meldeten auch andere Schäden. Es gab 7 Schadensmeldungen bei Hausratversicherungen sowie 17 sonstige Schadensfälle. 30 Versicherte reichten nur eine einzige Schadensmeldung ein, je ein Versicherter meldete außer einem Hausratsschaden eine der beiden anderen Schadensarten, und bei keinem der Versicherten traten alle drei Schadensarten ein. Zeichnen wir ein Diagramm und bestimmen wir die Anzahl der Versicherten, die genau zwei Schäden gemeldet haben. Diese Versicherten meldeten genau zwei Schäden: Und jetzt kommt eine sehr spannende Geschichte von Schafen und Zahlenmengen … Unterhalten wir uns ein bisschen über Zahlen. Das ist zum Beispiel die 3. Und das ist die 4. Und leider brauchen wir manchmal auch negative Zahlen. Und so bekommen wir Schritt für Schritt die Menge der ganzen Zahlen, die wir mit Z bezeichnen. Manchmal können wir auch Zahlen brauchen, die Verhältnisse ausdrücken. Diese nennen wir rationale Zahlen. Diese Gleichung hat zum Beispiel folgende Lösung: Die Menge der rationalen Zahlen bezeichnen wir mit Q. Dann gibt es auch Gleichungen, deren Lösungen nicht rationale Zahlen sind. So zum Beispiel diese Gleichung: Und so kommen wir zu den irrationalen Zahlen, die auf der Zahlengeraden die Lücken zwischen den rationalen Zahlen füllen. Die rationalen und irrationalen Zahlen bilden zusammen die Menge der reellen Zahlen.
Was wir über Graphen wissen sollten
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.
Die Siebformel
Die Siebformel Schauen wir uns nun etwas ganz Spannendes an. In einer Klasse gibt es 12 Schülerinnen und Schüler, die Mathe hassen, und 18, die Physik nicht ausstehen können. 20 Schüler und Schülerinnen hassen mindestens eines der beiden Fächer. Wie viele hassen beide Fächer? Komplement der Menge A: Schnitt der Mengen A und B: Vereinigung der Mengen A und B: Differenz der Mengen A und B: 12 hassen Mathe … Diese beiden vertikalen Striche bezeichnen die Anzahl der Elemente in der Menge A (ihre Mächtigkeit). 18 hassen Physik. 20 hassen mindestens eines der beiden. Die Frage ist, wie viele Elemente die Schnittmenge enthält. Es gibt eine tolle Formel, mit der wir das berechnen können: die sogenannte Siebformel. Die Siebformel besagt: Wenn wir die Mächtigkeit der Vereinigungsmenge von A und B berechnen wollen, müssen wir die Mächtigkeiten von A und B addieren. Elemente, die in beiden Mengen enthalten sind, haben wir dabei allerdings doppelt gezählt, also müssen wir die Schnittmenge einmal abziehen. Wie funktioniert das in unserem konkreten Fall? Also gibt es 10 Schüler (oder Schülerinnen), die beide Fächer hassen. In einer Klasse sind 20 Schülerinnen und Schüler. 9 von ihnen mögen Mathe, darunter 5 Mädchen. Wir wissen auch, dass 5 Jungen Mathe nicht mögen. Wie viele Mädchen sind in der Klasse? In dieser Aufgabe setzen wir voraus, dass jeder, der kein Mädchen ist, ein Junge ist, und hoffen, dass wir mit dieser Vereinfachung niemandem zu nahe treten. Jetzt kommt die Siebformel: Was wissen wir denn alles? Es gibt 5 Schüler, die keine Mädchen sind und Mathe nicht mögen. Umgekehrt bedeutet dies, dass 15 Mädchen und/oder Mathe-Fans sind. Es gehen also 11 Mädchen in die Klasse.
AUFGABE | Mengen
AUFGABE | Mengen Wir haben die Mengen A und B: Bestimmen wir die Mengen … und … . Menge A enthält die positiven Teiler von 28, und Menge B enthält die positiven Teiler von 49. Welche Elemente haben die Mengen … und … ? Positive Teiler von 28: Positive Teiler von 49: Wie viele aus zwei Elementen bestehende Teilmengen hat die Menge (2, 3, 5, 7, 11)?
AUFGABE | Graphen
AUFGABE | Graphen Hier haben wir einen Graphen mit fünf Knoten. Ergänzen wir den Graphen um weitere Kanten, bis jeder Knoten eine Gradzahl von 2 hat. Und noch eine trickreichere Lösung: In einer sechsköpfigen Gesellschaft wurde jede Person gefragt, wie viele der anderen Teilnehmer sie kennt (die Bekanntschaften sind gegenseitig). Die Antworten der ersten fünf Personen: 5, 4, 3, 2, 1. Stellen wir in einem Graphen die Bekanntschaften zwischen den Teilnehmern dar. Wie viele Bekanntschaften hat die sechste Person in der Gesellschaft? Zeichnen wir einen Graphen mit sechs Knoten. Die Knoten sollen die Gradzahlen 0, 1, 2, 2, 3, 4 haben. In einem Büro arbeiten insgesamt 11 Personen. An einem bestimmten Tag begegneten diese 11 Personen der folgenden Anzahl von Kolleginnen und Kollegen: 0, 1, 2, 2, 2, 5, 0, 0, 4, 4, 2. Stellen wir eine mögliche Kombination der Begegnungen in einem Graphen dar. Wie viele Begegnungen gab es insgesamt? Gesamtzahl der Begegnungen: