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

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).

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 (Benutzer:dlaxar)

a

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

b

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

c

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).

"In einem ungerichteten Graphen reicht dafür schon eine Kante weniger also 5 Kanten" -> wieso?? -> Ich glaube man kann sich das so vorstellen, dass im ungerichteten Graphen ein Knoten mit allen anderen Knoten verbunden werden kann, und so quasi eine Sonne entsteht. Jede "Sonnenstrahlen-Spitze" ist ein Knoten und jeder dieser Knoten hat eine Kante. Nur der Knoten, er die Mitte der Sonne darstellt, hat keine Kante. Deshalb einer weniger.

Oder hat jemand eine bessere Erklärung, gibts dafür eine Erklärung anhand dem Lemma?