TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 278

Aus VoWi
Wechseln zu: Navigation, Suche

Konstruieren Sie, wenn möglich, einen ungerichteten Graphen mit den Graden

a) 2, 2, 3, 3, 4, 4

b) 2, 3, 3, 4, 4, 4

c) 2, 3, 3, 3, 4, 4

Theoretische Grundlagen (von mnemetz)[Bearbeiten]

Ein Graph G ist ein Tupel (V, E), wobei V eine Menge von Knoten (englisch vertex, oft auch Ecken genannt) und E eine Menge von Kanten (englisch edge, manchmal auch Bögen genannt) bezeichnet. Dabei ist E in

  • ungerichteten Graphen ohne Mehrfachkanten eine Teilmenge aller 2-elementigen Teilmengen von V,
  • gerichteten Graphen ohne Mehrfachkanten eine Teilmenge des kartesisches Produkt|kartesischen Produktes V x V,
  • ungerichteten Graphen mit Mehrfachkanten eine Multimenge über der Menge aller 2-elementigen Teilmengen von V,
  • gerichteten Graphen mit Mehrfachkanten eine Multimenge über dem kartesischen Produkt V x V,
  • Hypergraphen eine Teilmenge der Potenzmenge von V.
1. ungerichteter Graph ohne Mehrfachkanten
2. gerichteter Graph ohne Mehrfachkanten
3. ungerichteter Graph mit Mehrfachkanten
4. gerichteter Graph mit Mehrfachkanten

Somit können wir in den Aufgabenstellungen einen ungerichten Graphen ohne Mehrfachkanten nur dann zeichnen, wenn das Handschlaglemma gilt: Die Summe über die Grade aller Knoten eines Graphen ist gleich der doppelten Kantenanzahl in dem Graphen.

Da die doppelte Kantenanzahl gerade ist, muss die Summe über die Grade aller Knoten auch gerade sein. In der Summe darf ich beliebig Klammern setzen, also auch einmal um alle geraden Summanden (diese Summe ist auf jeden fall gerade), und dann einmal um alle ungeraden Summanden; damit die zweite Summe gerade ist, muss die anzahl deren Summanden gerade sein. Nun ist aber jeder Summand Grad eines Knotens; diese Knoten haben alle ungeraden Grad; d.h. die Anzahl der Knoten mit ungeradem Grad ist gerade.

Lösungsvorschlag von mnemetz[Bearbeiten]

Beispiel a[Bearbeiten]

Grade: 2, 2, 3, 3, 4, 4

Gerade Anzahl ungerader Knotengrade \Rightarrow kann gezeichnet werden!

Bsp171 1.png

Beispiel b[Bearbeiten]

Grade: 2, 3, 3, 4, 4, 4

Gerade Anzahl ungerader Knotengrade \Rightarrow kann gezeichnet werden!

Bsp171 2.png

Beispiel c[Bearbeiten]

Grade: 2, 3, 3, 3, 4, 4

Ungerade Anzahl ungerader Knotengrade: \Rightarrow kann nicht gezeichnet werden!