Spannbaum in gerichteten Graph < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:18 Sa 03.01.2009 | | Autor: | adoon |
| Aufgabe | | Gegeben ist ein gerichteter, kreisfreier Graph, gesucht ist die Anzahl an möglichen Spannbäumen in diesem Graph. |
Also es geht darum, was für Aussagen man anhand eines gegeben Graphen über die Anzahl der Spannbäume in diesem Graphen treffen kann.
Mir würde auch eine Einordnung mit Landausymbolen reichen.
Ich hab bisher in die Richtung gedacht, dass man Spannbäume über Tiefensuche findet, also darüber Aussagen treffen kann. Eine Tiefensuche durch einen gerichteten Graphen liegt soweit ich weiss in O(|V|+|E|), aber das führt mich noch nicht zu der Anzahl der Spannbäume.
|
|
| |
|
> Gegeben ist ein gerichteter, kreisfreier Graph, gesucht ist
> die Anzahl an möglichen Spannbäumen in diesem Graph.
> Also es geht darum, was für Aussagen man anhand eines
> gegeben Graphen über die Anzahl der Spannbäume in diesem
> Graphen treffen kann.
Ein kreisfreier Graph hat wohl genau so viele
Sbannbäume wie er (disjunkte) Bäume enthält -
oder sehe ich da etwas falsch ?
LG
|
|
|
|
