Kurs:Diskrete Mathematik (Osnabrück 2020)/Arbeitsblatt 25/kontrolle

Übungsaufgaben

Aufgabe Referenznummer erstellen

Zeige, dass man einen Graphen genau dann eindimensional realisieren kann, wenn jede Zusammenhangskomponente von ihm ein Pfad ist.

Aufgabe Referenznummer erstellen

Zeige, dass ein Graph genau dann planar ist, wenn jede Zusammenhangskomponente von ihm planar ist.

Aufgabe Referenznummer erstellen

Beschreibe eine explizite ebene Realisierung des vollständigen Graphen mit ${}4$ Knotenpunkten. Es sollen insbesondere die stetigen Wege explizit gegeben sein.

Aufgabe Referenznummer erstellen

Es sollen drei Häuser jeweils mit Leitungen an Wasser, Gas und Elektrizität angeschlossen werden. Beschreibe eine Möglichkeit, bei der es nur eine Überschneidung gibt.

Aufgabe Referenznummer erstellen

Kann es bei einem zusammenhängenden ebenen Graphen sein, dass es darin einen Kreis gibt, der die Taille des Graphen realisiert, der echt innerhalb eines Kreises verläuft, der den Umfang des Graphen realisiert.

Aufgabe Referenznummer erstellen

Bestimme für den abgebildeten Graphen die Anzahl der Knotenpunkte, die Anzahl der Kanten und die Anzahl der Gebiete und bestätige die eulersche Polyederformel.

Aufgabe Referenznummer erstellen

Skizziere eine ebene Realisierung des Graphen mit ${}5$ Punkten und ${}9$ Kanten.

Aufgabe Referenznummer erstellen

Ist der Spielzuggraph zur Schachfigur König auf einem ${}3\times 3$ -Feld planar?

Aufgabe * Referenznummer erstellen

Ist der Spielzuggraph zur Schachfigur König auf einem ${}5\times 5$ -Feld planar?

Aufgabe * Referenznummer erstellen

Für welche der Schachfiguren Turm, Läufer, Dame, König ist der Spielzuggraph zu einem ${}8\times 8$ -Feld planar?

Aufgabe Referenznummer erstellen

Ist der Spielzuggraph zur Schachfigur Springer (Pferd) auf einem ${}8\times 8$ -Feld planar?

Aufgabe Referenznummer erstellen

Ist der Spielzuggraph zur Schachfigur Turm auf einem ${}2\times 3$ -Feld planar?

Aufgabe Referenznummer erstellen

Ist der Spielzuggraph zur Schachfigur Turm auf einem ${}3\times 3$ -Feld planar?

Aufgabe Referenznummer erstellen

Ist der Spielzuggraph zur Schachfigur Läufer auf einem ${}4\times 4$ -Feld planar?

Aufgabe Referenznummer erstellen

Zähle auf einem real existierenden Würfel die Eckpunkte, die Kanten und die Seiten. Gilt dafür die eulersche Polyederformel?

Kommentar:

Jeder Würfel hat 8 Eckpunkte, 12 Kanten und 6 Seiten. Da ${}8-12+6=2$ , gilt die eulersche Polyederformel für alle Würfel. Dies sollte uns nicht überraschen, da jeder Würfel eine ebene Realisierung besitzt (siehe die Vorlesung für eine solche Realisierung), in der jede Seite des Würfels einem Gebiet der Realisierung entspricht.

Im Allgemeinen ist es bekannt, dass jedes Polyeder eine ebene Realisierung hat. Die eulersche Polyederformel gilt somit für alle Polyeder.

Diskutieren und Fragen

Aufgaben zum Abgeben

Aufgabe (2 Punkte)Referenznummer erstellen

Bestimme für den abgebildeten Graphen die Anzahl der Knotenpunkte, die Anzahl der Kanten und die Anzahl der Gebiete und bestätige die eulersche Polyederformel.