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

Aus VoWi
Zur Navigation springen Zur Suche springen

Ein schlichter Graph G = (V, E) heißt kubisch, wenn jeder Knoten v \in V Knotengrad d(v) = 3 hat.

a) Geben Sie ein Beispiel für einen kubischen Graphen mit \alpha_0(G) = 6 an!

b) Gibt es einen kubischen Graphen mit ungerader Knotenanzahl \alpha_0(G)?

c) Zeigen Sie, daß es zu jedem n \geq 2 einen kubischen Graphen mit \alpha_0(G) = 2 \cdot n gibt!

Lösungsvorschlag von mnemetz[Bearbeiten]

a) Beispielgraph G = 6[Bearbeiten]

Geben Sie ein Beispiel für einen kubischen Graphen mit \alpha_0(G) = 6 an!

ANMERKUNG: \alpha_0(G) = 6 heißt 6 Knoten. Die Skizze zeigt allerdings 8 Knoten, kleiner Fehler...

Bsp172 1.png

b) Kubischer Graph mit ungerader Knotenanzahl[Bearbeiten]

Gibt es einen kubischen Graphen mit ungerader Knotenanzahl \alpha_0(G)?

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:

\sum_{v \in V(G)} d(v) = 2 \cdot | E(G) |

Nachdem gemäß der Definition des kubischen Graph aus der Angabe jeder Knoten v Knotengrad d(v) = 3 hat, ist die Summe aller Grad die Anzahl der Knoten \alpha_0(G) multipliziert mit 3 Grad:

\sum_{v \in V(G)} d(v) = 3 \cdot \alpha_0(G)

Das kann man sich leicht überlegen, in dem man sich den kubischen Graph von weiter oben vorstellt, die Knoten abzählt (entspricht \alpha_0(G)) und mit der Anzahl der Grad (3) für jeden Knoten multipliziert. Das ergibt dann die Summe über alle Grad.

Die Summe über alle Grad ist immer noch die doppelte Kantenanzahl nach dem Handschlaglemma:

3 \cdot \alpha_0(G) = 2 \cdot | E(G) |

Somit muss aber \alpha_0(G) eine gerade Zahl sein, da das Doppelte der Kantenanzahl auch immer gerade ist, der Faktor 3 aber ungerade. Womit es keinen kubischen Graph mit ungerader Knotenanzahl \alpha_0(G) gegeben kann.

c) Verallgemeinerung kubischer Graph[Bearbeiten]

Zeigen Sie, daß es zu jedem n \geq 2 einen kubischen Graphen mit \alpha_0(G) = 2 \cdot n gibt!

Bsp172 2.png

Der kubische Graph mit z.B. n = 8 schaut von der Anordnung so aus:

   "unterer Teil"          "oberer Teil"
  |-----------------------------------|
  3   2   1                   1   2   3
      |   |-------------------+---|
      |-----------------------|
        
           ^^^^^^^^^^^^^^^^^^^^
             2   1    1   2
           einfügen n mal