Aufgabe:
ich habe eine Aufgabe zu bearbeiten, die sich auf das Mühle-Spielbrett bezieht. Das Spielbrett wird als ungerichteter Graph betrachtet. Weiter werden zwei Knoten mit der gleichen Anzahl Nachbarn als gradäquivalent beschrieben. Ich soll zeigen, dass es sich dabei tatsächlich um eine Äquivalenzrelation handelt. Ich weiß, dass ich dafür die Symmetrie, die Reflexivität sowie die Transitivität zeigen muss.
Problem/Ansatz:
Wie soll ich eine solche Relation überhaupt formal aufschreiben und wie zeige ich die entsprechenden Eigenschaften daran?
Damit eine bestimmte Relation als Äquivalenzrelation bezeichnet werden kann, müssen drei Bedingungen erfüllt sein:
1.Die Relation muss symmetrisch sein
2.Die Relation muss reflexiv sein
3.Die Relation muss transitiv sein
Äquivalenzklassen:
Für M2: 2 Nachbarn: 8; 3 Nachbarn: 8; 4 Nachbarn: 0
Für M3: 2 Nachbarn: 12; 3 Nachbarn: 8; 4 Nachbarn: 4
Für M4: 2 Nachbarn: 14; 3 Nachbarn: 10; 4 Nachbarn: 8
Ich bedanke mich schon jetzt für eure Hilfe!
Text erkannt:
Aufgabe 3 (Graphentheorie; 3)
Auf dem Bild links sehen Sie ein Mühlebrett. Dieses kann man offenbar als einen ungerichteten Graphen mit 24 Knoten interpretieren.
Wir definieren zwei Knoten als gradäquivalent, sofern sie dieselbe Anzahl an Nachbarn aufweisen. Zeigen Sie, dass es sich dabei tatsächlich um eine Äquivalenzrelation handelt! Bestimmen Sie darüber hinaus sämtliche Äquivalenzklassen und geben Sie jeweils deren Größen an! Der Mühlegraph links ist , offensichtlich \( ^{\text {" }} \) aus drei Ringen aufgebaut. Man kann in naheliegender Weise auch Mühlegraphen \( M_{n} \) mit \( n \) solchen Ringen betrachten. Wie groß sind die Klassen der Knoten vom Grad \( d \) in \( M_{n} \) für \( 2 \leq d \leq 4 ? \)
