Graphentheorie Baumanzahl

Meinst du die Anzahl der Teilgraphen, die Bäume sind, oder die Anzahl der verschiedenen vorkommenden Bäume ? (derselbe Baum kann natürlich mehrfach in einem Graphen als Teilgraph vorkommen)

Ferner wäre es interessant, zu überprüfen, ob die Anzahl der gesuchten Bäume nicht vom vorgegebenen Graphen abhängt. Mir scheint hier eine Abhängigkeit gegeben zu sein.

Grüße Abakus smile

25.06.2007, 21:12

-Gernot-

Auf diesen Beitrag antworten »

Zitat:

Original von Abakus
Meinst du die Anzahl der Teilgraphen, die Bäume sind, oder die Anzahl der verschiedenen vorkommenden Bäume ? (derselbe Baum kann natürlich mehrfach in einem Graphen als Teilgraph vorkommen)

Ferner wäre es interessant, zu überprüfen, ob die Anzahl der gesuchten Bäume nicht vom vorgegebenen Graphen abhängt. Mir scheint hier eine Abhängigkeit gegeben zu sein.

Grüße Abakus smile

Danke für deine Antwort.

Das weiß ich leider nicht. Das Beispiele lautet nur

Zitat:

Wie viele mögliche Bäume gibt es in einem Wald aus n Knoten und m Kanten?

leider ohne irgendwelche Zusatzinformationen.

Liebe Grüße,

Gernot

25.06.2007, 22:02

Mazze

Auf diesen Beitrag antworten »

Zitat:

Meinst du die Anzahl der Teilgraphen, die Bäume sind, oder die Anzahl der verschiedenen vorkommenden Bäume ? (derselbe Baum kann natürlich mehrfach in einem Graphen als Teilgraph vorkommen)

Per Definition ist ein Baum ein zusammenhängender Wald, und ein Wald ein Graph ohne Zyklus.

Die maximale Anzahl aller möglichen Bäume aus einem Wald hängt entscheidend von der Struktur des Waldes ab. Ich würde erstmal den Wald in ZSHG-Komponenten unterteilen, also

$\begin{eqnarray*} Z_i = (V_i,E_i) \subseteq G \end{eqnarray*}$

Jetzt kann es zum Beispiel zwischen den Zusammenhangskomponenten jeweils nur eine Kante geben da sonst ein Zyklus entsteht. Jetzt musst Du Dir nur noch überlegen wie viele Kanten ich so zwischen den Komponenten legen kann und vor allem wie!

Neue Frage »

Antworten »

Graphentheorie Baumanzahl

Verwandte Themen