TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 284

Aus VoWi
Zur Navigation springen Zur Suche springen

Ein schlichter Graph heißt kubisch, wenn jeder Knoten Knotengrad hat.

a) Geben Sie ein Beispiel für einen kubischen Graphen mit an!

b) Gibt es einen kubischen Graphen mit ungerader Knotenanzahl ?

c) Zeigen Sie, daß es zu jedem einen kubischen Graphen mit gibt!

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:
{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}


Lösungsvorschlag von mnemetz[Bearbeiten | Quelltext bearbeiten]

a) Beispielgraph G = 6[Bearbeiten | Quelltext bearbeiten]

Geben Sie ein Beispiel für einen kubischen Graphen mit an!

ANMERKUNG: heißt 6 Knoten. Die Skizze zeigt allerdings 8 Knoten, kleiner Fehler... Den richtigen Graphen findet man auf Wikipedia bei Kubischer Graph.

b) Kubischer Graph mit ungerader Knotenanzahl[Bearbeiten | Quelltext bearbeiten]

Gibt es einen kubischen Graphen mit ungerader Knotenanzahl ?

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:

Nachdem gemäß der Definition des kubischen Graph aus der Angabe jeder Knoten Knotengrad hat, ist die Summe aller Grad die Anzahl der Knoten multipliziert mit Grad:

Das kann man sich leicht überlegen, in dem man sich den kubischen Graph von weiter oben vorstellt, die Knoten abzählt (entspricht ) und mit der Anzahl der Grad () 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:

Somit muss aber eine gerade Zahl sein, da das Doppelte der Kantenanzahl auch immer gerade ist, der Faktor aber ungerade. Womit es keinen kubischen Graph mit ungerader Knotenanzahl geben kann.

c) Verallgemeinerung kubischer Graph[Bearbeiten | Quelltext bearbeiten]

Zeigen Sie, daß es zu jedem einen kubischen Graphen mit gibt!

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

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