Kurs:Diskrete Mathematik (Osnabrück 2020)/Arbeitsblatt 15/kontrolle
- Übungsaufgaben
Skizziere sämtliche Graphen auf der Menge .
Skizziere sämtliche Graphen auf einer -elementigen Knotenmenge (für ), wobei Graphen, die durch eine Umbenennung der Knotenmenge ineinander übergehen, nur einfach aufgeführt werden müssen.
Man soll also nur die „Isomorphieklassen“ auflisten, diesen Begriff werden wir das nächste Mal präzisieren.
Skizziere für die abgebildete Geradenkonfiguration den zugehörigen Graphen.
Man gebe ein Beispiel für einen Graphen, der nicht von einer Geradenkonfiguration im Sinne von Beispiel 15.12. herrührt.
Kommentar:
Der Graph einer Geradenkonfiguration wird gemäß der Lagebeziehung der Geraden konstruiert. Eine elementare Eigenschaft dieser Beziehung: zwei Geraden sind parallel, wenn sie beide parallel zu einer dritten Gerade sind. Der Graph der Konfiguration von 3 Geraden muss also kantenfrei sein, wenn er einen isolierten Knotenpunkt besitzt. Ein Graph mit 3 Knotenpunkten und 1 Kante ist somit kein Graph einer Geradenkonfiguration.
Skizziere den Teilerfremdheitsgraphen zu den Zahlen
Man fertige eine schematische Skizze der eigenen Wohnung als ein Graph an, wobei die Zimmer durch einen Knotenpunkt widergegeben werden sollen und zwei Knoten genau dann miteinander verbunden sein sollen, wenn sie in der Wohnung durch eine Tür verbunden sind.
Bestimme den Grad eines jeden Knotenpunktes im Graphen .
Bestimme den Grad eines jeden Knotenpunktes im Graphen .
Bestimme den Grad eines jeden Knotenpunktes im Graphen .
Bestimme für den durch den Springer auf dem -Schachbrett gegebenen Erreichbarkeitsgraphen, wie viele Punkte welchen Grad besitzen.
Kommentar:
Von jedem Feld des - Schachbretts mit Ausnahme des zentralen Feldes kann der Springer mit einem Zug genau zwei andere Felder erreichen. Dagegen kann der Springer nicht vom zentralen Feld springen. Das zentrale Feld ist also ein isolierter Knotenpunkt des Erreichbarkeitsgraphen. Daher besitzt der Erreichbarkeitsgraph 8 Knotenpunkte vom Grad 2 und einen Knotenpunkt vom Grad 0.
Man kann den Erreichbarkeitsgraphen in diesem Fall explizit bestimmen: er ist ein Rundgang mit Knotenpunkten zusammen mit einem isolierten Knotenpunkt.
Bestimme für den durch den Turm auf dem Schachbrett gegebenen Erreichbarkeitsgraphen, wie viele Punkte welchen Grad besitzen. Was ist die durchschnittliche Gradzahl?
Bestimme für den durch den Läufer auf dem Schachbrett gegebenen Erreichbarkeitsgraphen, wie viele Punkte welchen Grad besitzen. Was ist die durchschnittliche Gradzahl?
.svg)
Es sei die Menge der Haltestellen der Amsterdamer U-Bahn. Es sei der Netzgraph und der zugehörige umsteigefreie Erreichbarkeitsgraph (siehe Beispiel 15.5). Bestimme für die folgenden Stationen den Grad in bzw .
- Isolatorweg.
- Van der Madeweg.
- Noord.
- Centraal Station.
- De Pijp.
- Aufgaben zum Abgeben
Aufgabe (1 Punkt)Referenznummer erstellen
Skizziere für die abgebildete Geradenkonfiguration den zugehörigen Graphen.
Aufgabe (3 Punkte)Referenznummer erstellen
Skizziere den Teilerfremdheitsgraphen zu den Zahlen
Aufgabe (2 Punkte)Referenznummer erstellen
Aufgabe (4 Punkte)Referenznummer erstellen
Zeige, dass man jeden Graphen als einen Teilerfremdheitsgraphen darstellen kann.
Tipp: Komplementärgraph.
Aufgabe (4 Punkte)Referenznummer erstellen
Bestimme für den durch den Springer auf dem Schachbrett gegebenen Erreichbarkeitsgraphen, wie viele Punkte welchen Grad besitzen. Was ist die durchschnittliche Gradzahl?