Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

binärer Baum Kanten Knoten!?
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Informatik-Forum -> binärer Baum Kanten Knoten!?
 
Autor Nachricht
rumpi
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 06.11.2008
Beiträge: 110

BeitragVerfasst am: 20 Jan 2009 - 21:22:47    Titel: binärer Baum Kanten Knoten!?

Gegeben sei ein binärer Baum. Sei n0 die Anzahl der Blätter und n2 die Anzahl der Knoten mit zwei ausgehenden Kanten. Zeige, dass
n0=n2+1 gilt!

Wie soll man denn das zeigen? Ich meine, es stimmt (habs durch probieren gesehen), aber zeigen?

Hat jemand ne Idee?

Grüße,

rumpi
Mörf
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 30.10.2006
Beiträge: 37

BeitragVerfasst am: 20 Jan 2009 - 21:27:47    Titel:

stehe auch noch aufm schlauch...
hab mal rumprobiert, bin aber noch zu keinem ergebnis gekommen...
rumpi
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 06.11.2008
Beiträge: 110

BeitragVerfasst am: 20 Jan 2009 - 21:43:41    Titel:

Habs mit Induktion versucht, aber ob das so stimmt, weiß ich nicht Razz
Keine ne andere Idee?
sarc
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 21.09.2006
Beiträge: 2657

BeitragVerfasst am: 20 Jan 2009 - 22:06:20    Titel:

Induktion klingt vernünftig.
rumpi
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 06.11.2008
Beiträge: 110

BeitragVerfasst am: 20 Jan 2009 - 22:10:09    Titel:

Im Induktionsschritt muss man ne Fallunterscheidung machen, oder?
Einmal wird ein Knoten eingefügt und mit einem Knoten verbunden, der ein Kind hat und einmal wird der eingefügte Knoten mit nem Blatt verbunden, dieses ist dann keines mehr und so gilt auch wieder die Induktionvoraussetzung.

Das wäre meine Idee...
sarc
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 21.09.2006
Beiträge: 2657

BeitragVerfasst am: 20 Jan 2009 - 22:15:32    Titel:

Ja, auch die Fallunterscheidung klingt sinnvoll. Smile
rumpi
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 06.11.2008
Beiträge: 110

BeitragVerfasst am: 20 Jan 2009 - 22:24:17    Titel:

Dann kann ich beruhigt die HA abgeben Razz

Danke!
Armin Gibbs
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 06.02.2008
Beiträge: 992

BeitragVerfasst am: 20 Jan 2009 - 22:35:03    Titel:

Kennt ihr das Handschlaglemma?

2*m = Summe alle Knotengrade = n0 + 2*n1 + 3*n2 - 1

m = Anz. Kanten
n0 = Anz. Blätter
n1 = Anz. Knoten mit einem Nachfolger (haben Grad 2, bis auf Wurzel, die hat Grad 1)
n2 = Anz. innere Knoten mit zwei Nachfolgern (haben Grad 3, bis auf Wurzel, die hat Grad 2)

Nun weiß man von einem Baum, dass gilt:

m = n-1 = n0 + n1 + n2 - 1

Damit:

2*(n0 + n1 + n2 - 1) = n0 + 2*n1 + 3*n2 - 1

=> n0 = n2+1
rumpi
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 06.11.2008
Beiträge: 110

BeitragVerfasst am: 20 Jan 2009 - 23:08:59    Titel:

Ne, das haben wir nicht, aber so machts natürlich Sinn!
Aber mit Induktion gings dann letztendlich auch.

Du hast nicht zufällig hierzu ne Idee:

http://www.uni-protokolle.de/foren/viewtopic.php?p=1733225#1733225

?
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Informatik-Forum -> binärer Baum Kanten Knoten!?
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum