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

Aus Wikiversity
Zur Navigation springen Zur Suche springen



Übungsaufgaben

Aufgabe

Skizziere sämtliche Graphen auf der Menge .


Aufgabe

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.

Aufgabe

5Geraden4Schnittpunkte 2.png

Skizziere für die abgebildete Geradenkonfiguration den zugehörigen Graphen.


Aufgabe

Man gebe ein Beispiel für einen Graphen, der nicht von einer Geradenkonfiguration im Sinne von Beispiel 15.12. herrührt.


Aufgabe

Skizziere den Teilerfremdheitsgraphen zu den Zahlen


Aufgabe

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.


Aufgabe

Der Graph .

Bestimme den Grad eines jeden Knotenpunktes im Graphen .


Aufgabe

Der Graph .

Bestimme den Grad eines jeden Knotenpunktes im Graphen .


Aufgabe

Der Graph .

Bestimme den Grad eines jeden Knotenpunktes im Graphen .


Aufgabe

Bestimme für den durch den Springer auf dem -Schachbrett gegebenen Erreichbarkeitsgraphen, wie viele Punkte welchen Grad besitzen.


Aufgabe

Bestimme für den durch den Turm auf dem Schachbrett gegebenen Erreichbarkeitsgraphen, wie viele Punkte welchen Grad besitzen. Was ist die durchschnittliche Gradzahl?


Aufgabe

Bestimme für den durch den Läufer auf dem Schachbrett gegebenen Erreichbarkeitsgraphen, wie viele Punkte welchen Grad besitzen. Was ist die durchschnittliche Gradzahl?


Aufgabe

AmsterdamMetroWashingtonStyle (from 2018).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 .

  1. Isolatorweg.
  2. Van der Madeweg.
  3. Noord.
  4. Centraal Station.
  5. De Pijp.


Aufgabe

Wir betrachten in einem Kreuzworträtsel die Kästchen als Knotenpunkte eines Graphen und verbinden zwei verschiedene Kästchen durch eine Kante, falls sie zu einem Wort des Rätsels gehören. Welchen Grad hat ein Knoten?


Aufgabe

Wir betrachten in einem Kreuzworträtsel die Wörter als Knotenpunkte eines Graphen und verbinden zwei verschiedene Wörter durch eine Kante, falls sie sich in einem Kästchen treffen. Welchen Grad hat ein Knoten?




Aufgaben zum Abgeben

Aufgabe (1 Punkt)

5Geraden7Schnittpunkte.png

Skizziere für die abgebildete Geradenkonfiguration den zugehörigen Graphen.


Aufgabe (3 Punkte)

Skizziere den Teilerfremdheitsgraphen zu den Zahlen


Aufgabe (2 Punkte)

Ewe d020 house plan with two of the most important rooms.png

Skizziere die gezeigte Wohnung als einen Graphen, wobei die Zimmer zu Knoten und die Türen zu Kanten werden sollen. Bestimme für die einzelnen Knoten ihren Grad.


Aufgabe (4 Punkte)

Zeige, dass man jeden Graphen als einen Teilerfremdheitsgraphen darstellen kann.

Tipp: Komplementärgraph.

Aufgabe (4 Punkte)

Bestimme für den durch den Springer auf dem Schachbrett gegebenen Erreichbarkeitsgraphen, wie viele Punkte welchen Grad besitzen. Was ist die durchschnittliche Gradzahl?



<< | Kurs:Diskrete Mathematik (Osnabrück 2020) | >>

PDF-Version dieses Arbeitsblattes

Zur Vorlesung (PDF)