Ohrenzerlegung

Leute 🙂

Ich habe ein kleines (eigtl. habe ich viele) Verständnisproblem mit der KE2,
dabei geht es um (eigtl. alles) die Ohrenzerlegung.

Verstehe ich das richtig, dass das Prinzip/Ziel der Ohrenzerlegung ist, die Knoten/Kanten zu "überbrücken" die bei Wegfall den Zusammenhang des Graphen "gefährden würden"?

Also wenn ich einen Kreis, mit nur einer Verbindung im Kreis habe (quasi Durchmesser), lege ich mein erstes Ohr an den beiden Knoten an, welche die Kante als Anfangs-/Endpunkt hat oder?

Ich hoffe ihr konntet nachvollziehen was ich hier so kryptisch dargestellt habe 🙂

Danke!

MfG

Lars

Ich würde eher sagen, durch das "ankleben" der Ohren ist sichergestellt, dass alle neu hinzugefügten Knoten von jedem anderen durch mindestens zwei disjunkte Wege erreichbar sind

Ich verstehe es immernoch nicht, könnte heulen!
Wie komme ich denn darauf, welche Knoten ich verbinden soll?!

Also am Beispiel der EA 2 Aufgabe 2.3 Graph2.

Du suchst dir zuerst den größten Kreis.

C = (1,3,6,11,13,16,17,15,12,7,5,2)

Nun musst du ja noch den Graph zerlegen und quasi Teilgraphen draus bauen.
Du suchst dir also Pfade die die im Kreis beginnen und im Kreis enden.

Ein Pfad1 ist (1,4,3).

Alle Kanten die du schonmal gelaufen bist brauchst du nicht mehr zu beachten und sind fertig.

Bei dem 2. Graph fehlt dir nun bei dem oberen Konstrukt noch eine Kante und zwar: 2,4

Daher Pfad2 : (2,4)

Das machste denn nun einfach mit allen weiteren Kanten weiter die du noch nicht hattest nach diesem Schema.

Cool, danke für die Erklärung 🙂
Mit einfachen Worten klingt es viel verständlicher, vielen Dank dafür!

Eine Frage hätte ich jedoch noch:
Die zweite und alle nachfolgenden "Ohren" kann ich auch an bereits gelegten Ohren beginnen und enden lassen oder?

Genau.

Das "Ohr" sprich der Pfad kann denn in weitergehenden Schritten auch beginnen oder enden.
Bei Graph 2 musst du dies sogar machen da für die horizontalen Kanten, du diese sonst nicht "verarbeiten" kannst.