Bäume im Wald < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 18:49 Do 19.06.2008 | | Autor: | m.dutzler |
| Aufgabe | | Wieviele Bäume enthält ein Wald mit n Knoten und m Kanten? |
Ich hätte jetzt mal gesagt einen Baum. Da ein Baum ja ein zusammenhängender Graph sein muss. Es kann zwar verschiedene Bäume geben, aber immer nur einen.
Kann man das vll auch etwas mathematischer formulieren?
Ist das so richtig oder hab ich da einen groben Denkfehler drin.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Aufgabe | > Wieviele Bäume enthält ein Wald mit n Knoten und m Kanten?
> Ich hätte jetzt mal gesagt einen Baum. Da ein Baum ja ein
> zusammenhängender Graph sein muss. Es kann zwar
> verschiedene Bäume geben, aber immer nur einen.
>
> Kann man das vll auch etwas mathematischer formulieren?
> Ist das so richtig oder hab ich da einen groben Denkfehler
> drin.
>
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt. |
Hallo Markus !
Was ist in diesem Zusammenhang ein "Wald" ? ...
ich stelle mir vor: ein Graph, der aus verschiedenen, disjunkten
"Bäumen" bestehen kann, aber keinen einzigen Kreis enthält ?
Nun, ein Baum mit k Knoten hat genau (k-1) Kanten.
Wenn dein Wald also genau aus t Einzelbäumen mit
den Knotenzahlen [mm] n_i [/mm] und den Kantenzahlen [mm] m_i [/mm] besteht,
dann gelten die Gleichungen:
[mm] \summe_{i=1}^t{n_i} [/mm] = n
[mm] \summe_{i=1}^t{m_i}=m =\summe_{i=1}^t{(n_i-1)} =\left(\summe_{i=1}^t{n_i}\right)-t=n-t
[/mm]
[mm]m=n-t\ \Rightarrow t=n-m[/mm]
Die Anzahl der Bäume wäre also einfach t=n-m
(falls meine Interpretation des Begriffes "Wald" zutreffend war ...)
LG
al-Chwarizmi
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:35 Sa 21.06.2008 | | Autor: | m.dutzler |
In unserem Skript lautet die einzige Definition für wald die ich finden konnte wie folgt:
"Ein Graph ohne kreis (nicht unbedingt zusammenhängend) heißt wald. Sogesehen ist ein Baum ein zusammenhängender wald."
Ich würde mal sagen das passt mit deiner Interpretation recht gut zusammen.
Viele danke
|
|
|
| |
|
> In unserem Skript lautet die einzige Definition für wald
> die ich finden konnte wie folgt:
>
> "Ein Graph ohne kreis (nicht unbedingt zusammenhängend)
> heißt wald. Sogesehen ist ein Baum ein zusammenhängender
> wald."
>
> Ich würde mal sagen das passt mit deiner Interpretation
> recht gut zusammen.
absolut.
und ein Wald ohne Kanten ist dann quasi einer, der aus lauter
isolierten Punkten oder, um im Bild zu bleiben, "Sämlingen"
besteht...
|
|
|
|
