Bsp 31

  • Zwar schon recht knapp vor der Uebung, aber sicherlich auch interessant fuer die anderen Gruppen:



    Wie kann man denn das "gscheit" zeigen? Mir faellt dazu nur ein, dass ein binaerer Baum mit 3 Knoten auf jeden Fall (da ja vollstaendig) 2 Endknoten und einen internen Knoten hat (m interne Knoten, m+1 Endknoten). Wenn nun ein Endknoten gegen einen internen Knoten mit 2 weiteren Teilbaeumen getauscht wird, kommt 1 weiterer Endknoten hinzu (m+1 interne Knoten, m+2 Endknoten). Bewiesen ist damit natuerlich wenig... so eine Art vollstaendige Induktion waere halt nett. Hat hier vielleicht jemand einen Denkanstoss?


    Den Zusammenhang bei t-aeren vollstaendigen Baeumen hat man ja auch relativ rasch: (t-1)*m + 1 .. aber ich vermute mal, dass auch hier ein Beweis gefragt waere...

  • Tja, so einfach kann es sein:


    Code
    1. 1: |V| = |E| + 1 /*<-- Knoten gibt es immer einen mehr als die Anzahl der Kanten */
    2. 2: m+n = |E| + 1 /* m ist die Anzahl der internen Knoten, n die Anzahl der Endknoten */
    3. 3: m+n = m*t + 1 /* das Produkt von der Anzahl der internen Knoten mit der Anzahl der "Maechtigkeit" des Baumes (t-aerer Baum) ist aquivalent zur Anzahl der Kanten: klar, da ja der Baum vollstaendig ist und jeder interne Knoten zumindest t ausgehende Kanten hat */
    4. 4: n = (t - 1)*m + 1 /* umformungsmagic */