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

Aus VoWi
Zur Navigation springen Zur Suche springen

Bezeichne G = (V, E) einen gerichteten Graphen, V die Knoten-, E ⊆ V 2 die Kantenmenge. Definitionsgemäß heißen zwei gerichtete Graphen Gi = (Vi,Ei), i = 1,2, isomorph, wenn es eine bijektive Abbildung f : V1 → V2 gibt mit: (x, y) ∈ E1 (d.h. die Knoten x und y sind in G1 durch eine Kante verbunden) genau dann, wenn (f(x),f(y)) ∈ E2 (d.h., wenn auch f(x) und f(y) in G2 durch eine Kante verbunden sind).

Lösungsvorschlag (Benutzer:dlaxar)[Bearbeiten]

a[Bearbeiten]

G1: 1->2->3->4->5->6
G2: 1->2->3->4->5<-6

b[Bearbeiten]

Es kann keine bijektive Abbildung geben, da es in G1 eine eulersche Linie gibt und in G2 nicht

c[Bearbeiten]

In einem stark zusammenhängenden Graphen muss jeder Knoten von jedem anderen Knoten erreicht werden. Das ist nur dann gewährleistet, wenn d+ >= 1 und d- >= 1. Nach dem Handschlaglemma ist die Summe der Hin/Weggrade gleich der Anzahl der Kanten. In einem stark zusammenhängenden Graphen mit 6 Knoten benötigt man also mindestens 6 Kanten. In einem ungerichteten Graphen reicht dafür schon eine Kante weniger also 5 Kanten (1-2-3-4-5-6).