Baum < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Ein Baum mit 7 Knoten
Kantendichte berechnen
|
Hallo!
Ein Baum hat kein Kreis -> stimmt das ?
Kanten für einen vollständigen Graphen berechnen
[mm] \vektor{7 \\ 2} [/mm] = 21 Kanten
21-7 = 14 Kanten für meinen Baum
14/21 => Kantendichte
PS: Ich hab leider in meinen Unterlagen oder im Inet keine genaue Ausage gefunden ob ein Baum jetzt mit oder ohne Kreis berechnet wird
Weil ein Wald hat KEINEN Kreis -> laut meinen Unterlagen ;)
Mfg
Frankster
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:55 Mo 22.05.2006 | | Autor: | piet.t |
Hallo Frankster,
ich habe jetzt zwar auf die schnelle keine ordentliche Definition von "Kantendichte" gefunden, aber hier ein paar Anmerkungen:
>
> Hallo!
>
> Ein Baum hat kein Kreis -> stimmt das ?
Ja!
>
> Kanten für einen vollständigen Graphen berechnen
> [mm]\vektor{7 \\ 2}[/mm] = 21 Kanten
Stimmt!
>
> 21-7 = 14 Kanten für meinen Baum
Wieso das? Im Baum hat jeder Knoten höchstens einen Vorgänger, die Wurzel hat gar keinen=> Ein Baum mit 7 Knoten hat 6 Kanten (Man kann sich den einfach mal hinmalen)
>
> 14/21 => Kantendichte
Bei mir dann also 6/21 ?
>
> PS: Ich hab leider in meinen Unterlagen oder im Inet keine
> genaue Ausage gefunden ob ein Baum jetzt mit oder ohne
> Kreis berechnet wird
>
> Weil ein Wald hat KEINEN Kreis -> laut meinen Unterlagen
> ;)
Nachdem ein Wald aus lauter Bäumen besteht haben die dann wohl auch keinen. Aber eigentlich ist es andersrum: Ein Baum ist per Definition kreisfrei, ein Wald deswegen weil er aus Bäumen besteht....
>
> Mfg
> Frankster
>
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
Gruß
piet
|
|
|
| |
|
OK Danke vielmals!!
Aber schau dir das mal an
![[]](/images/popup.gif) Unterlagen -> BAUM
Da hab ich einen Baum mit 2 Vorgängern
|
|
|
| |
|
Hallo zusammen,
in der Grafik steht es doch: Hier geht es um ungerichtete Bäume, da ist die Sprechweise von ''Vorgángern'' unsinnig.
Also wenn die Kantendichte eines Graphen G=(V,E) definiert ist als [mm] \frac{|E|}{|V|}, [/mm] so hat ein Baum mit |V|=n immer Dichte
[mm] \frac{n-1}{n}, [/mm] und ein Wald mit k Zusammenhangskomponenten hat dann immer Dichte [mm] \frac{n-k}{n}.
[/mm]
Gruss,
Mathias
|
|
|
|
![[]](http://www.unet.univie.ac.at./~a0000378/baum.jpg){kind=small}
Unterlagen -> BAUM