Wurzelbaum

Die Wurzel hat Minimale Exzentrizität, d.h. auf gut deutsch sie ist mittig und hat die gleiche Anzahl Kanten zu allen Blättern. Wenn die Mitte 2 Knoten sind werden sie getrennt betrachtet und dann der Code zusammengesetzt, dabei lexikographische Reihenfolge beachten.
Lexikographische heißt: immer kleinste zuerst: also öffnende Klammer ist kleiner als schließende Klammer.

lexiographisch ordnen geht einfacher wenn du ( = a und ) = b setzt,
dann musst du aaababbabb
und aabb
und ab
lexiographisch ordnen, was ja hier gemacht ist.

Die Wurzel findest du wenn du dir den Baum aufmalst und für jeden Knoten den längsten Weg ranschreibst. Der Knoten der dann den kürzesten längsten Weg hat ist dann die Wurzel.

glaub das hab ich verstanden.
vielen dank. jetzt hab ich nur noch ein problem mit dem Matching und bipartit. dazu finde ich keinen zugang

cat112 schrieb:

glaub das hab ich verstanden.
vielen dank. jetzt hab ich nur noch ein problem mit dem Matching und bipartit. dazu finde ich keinen zugang 🙁

Zum Vergrößern anklicken....

Perfektes Matching ist, wenn zu jedem Knoten auf der linken Seite einer (genau einer) von der rechten Seite zugeordnet werden kann.
In den bisherigen Klausuren war es eigentlich fast immer so, dass es nicht ging.

Als Erklärung/Nachweis reicht dann sowas wie
Die Menge der Nachbarknoten von (linkerKnoten1, linkerKnoten3, linkerKnoten5) ist kleiner als die Menge (linkerKnoten1, linkerKnoten3, linkerKnoten5).

Am besten auf das Bild gucken und auf der rechten Seite die 3 oder 4 Knoten mit den wenigsten Verbindungen zur linken Seite ansehen.
Die dann mal im Geiste abfahren und verbinden dann fallen ja andere Verbindungen weg und in der Regel sieht man schnell, ob dadurch auf der rechten Seite einer isoliert wäre.