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

Aus Wikiversity
Zur Navigation springen Zur Suche springen



Übungsaufgaben

Aufgabe

Es sei eine Teilmenge. Zeige, dass durch die natürliche Inklusion der Potenzmengengraph zu ein voller Untergraph zum Potenzmengengraph von ist.


Aufgabe

Zeige, dass eine Hintereinanderschaltung von Graphhomomorphismen wieder ein Graphhomomorphismus ist.


Aufgabe

Bringe die drei Interpretationen eines U-Bahn-Netzes aus Beispiel 15.5 mit dem Konzept Untergraph in Verbindung.


Aufgabe *

Es sei ein Graphhomomorphismus.

  1. Es sei injektiv. Zeige, dass für den Grad die Abschätzung

    für jeden Punkt gilt.

  2. Wie sieht es aus, wenn nicht injektiv ist?


Aufgabe

Frucht Lombardi.svg
Frucht planar Lombardi.svg

Beschreibe zeichnerisch einen Isomorphismus zwischen den beiden gezeigten Graphen.


Aufgabe *

Es sei ein Graph.

  1. Zeige, dass für die folgenden Eigenschaften äquivalent sind.
    a) Es ist .
    b) Für alle folgt aus auch .
    c) Die Abbildung

    mit

    ist ein Graphhomomorphismus.

  2. Es sei die Relation aus (1). Welche Eigenschaften einer Ordnungsrelation erfüllt sie, welche nicht?


Aufgabe

Graph isomorphism 2.svg

Definiere einen Isomorphismus zwischen den beiden Graphen (es handelt sich um Multigraphen mit Schleifen). Die Farben helfen.


Aufgabe

Skizziere den Kantengraphen zum vollständigen Graphen


Aufgabe

Bull graph.circo.svg

Skizziere den Kantengraphen zu dem abgebildeten Graphen.


Aufgabe

Es sei ein Graph, eine Menge und eine Abbildung. Zeige, dass ein schwacher Homomorphismus von Graphen ist, wenn man mit der Struktur des Bildgraphen versieht.


Aufgabe

Bestimme die Automorphismengruppen sämtlicher Graphen mit drei Knotenpunkten.


Aufgabe

Bestimme die Automorphismengruppen sämtlicher Graphen mit vier Knotenpunkten.


Aufgabe

Bestimme die Automorphismengruppen sämtlicher Graphen mit fünf Knotenpunkten.


Aufgabe

Man gebe einen nichttrivialen Graphen mit trivialer Automorphismengruppen und minimaler Knotenzahl an.


Aufgabe

Parapluie graph.svg

Bestimme die Automorphismengruppe des abgebildeten Graphen.


Aufgabe

6n-graf.svg

Bestimme die Automorphismengruppe des abgebildeten Graphen.


Aufgabe

Beschreibe einen Graphen, dessen Automorphismengruppe gleich ist.


Aufgabe

Zeige, dass es im dreidimensionalen Würfelgraphen Graphautomorphismen gibt, die nicht durch eine geometrische Drehung des Würfels realisierbar sind.


Aufgabe *

Es sei ein Graph und der zugehörige Kantengraph.

  1. Zeige, dass es einen natürlichen Gruppenhomomorphismus

    gibt.

  2. Zeige, dass die Abbildung nicht injektiv sein muss.
  3. Zeige, dass die Abbildung nicht surjektiv sein muss.


Aufgabe

Identity graph1.svg

Zeige, dass der abgebildete Graph starr ist.




Aufgaben zum Abgeben

Aufgabe (5 Punkte)

Zeige, dass sich jeder Graph als voller Untergraph eines Potenzmengengraphen realisieren lässt.


Aufgabe (2 Punkte)

Identity graph5.svg

Skizziere den Kantengraphen zu dem abgebildeten Graphen.


Aufgabe (2 Punkte)

Es seien und isomorphe Graphen. Zeige, dass die zugehörigen Automorphismengruppen ebenfalls isomorph sind.


Aufgabe (2 Punkte)

Zeige, dass ein Graph und sein komplementärer Graph isomorphe Automorphismengruppen besitzen.


Aufgabe (3 Punkte)

Bestimme die Automorphismengruppe eines Rundganges mit Knotenpunkten.


Aufgabe (2 Punkte)

Identity graph7.svg

Zeige, dass der abgebildete Graph starr ist.


Aufgabe (2 (1+1) Punkte)

  1. Zeige, dass ein homogener Graph regulär ist.
  2. Man gebe ein Beispiel für einen regulären Graphen, der nicht homogen ist.


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

PDF-Version dieses Arbeitsblattes

Zur Vorlesung (PDF)