Steiner-Bäume

Wissenschaft Physik
1

Hallo!
Ich muss einen Vortrag über Steiner-Bäume halten. Weiss jemand ein gutes Buch über dieses Thema? Oder vielleicht eine Seite, wo Definitionen und ähnliches stehen?
Kirstin

2

Ich weiß noch nichtmal was das ist, postest du uns deinen Vortrag?

3

Kürzestes Netzwerk?
Hallo, Kirsten!

Ich nehme an, daß es sich um das sogenannte Steiner-Problem handelt, richtig?
Dabei geht es um das Finden von kürzesten Netzwerken.

Etwas darüber findest Du in folgender Literatur:

-) Spektrum der Wissenschaft, März 1989;

-) Moderne Mathematik (Spektrum-Verlag, 1996)
(das ist der gleiche Artikel wie darüber);

In diesem Artikel findet sich die folgende Literaturangabe:

-) Z.A. Melzal: Companion to Concrete Mathematics. John Wiley & Sons. 1973;

-) Pawel Winter: An Algorithm for the Steiner Problem in the Euclidian Plane. In: Networks, Band 15, Heft 3, S. 323-345, 1985.

Ich hoffe, es geht um dieses Problem. Anderswo kenne ich keine Steiner-Bäume.

CU,

Frank.

4

Ich nehme an, daß es sich um das sogenannte Steiner-Problem
handelt, richtig?

Ja, das geht in die richtige Richtung.

Dabei geht es um das Finden von kürzesten Netzwerken.

Etwas darüber findest Du in folgender Literatur:

-) Spektrum der Wissenschaft, März 1989;

-) Moderne Mathematik (Spektrum-Verlag, 1996)
(das ist der gleiche Artikel wie darüber);

In diesem Artikel findet sich die folgende Literaturangabe:

-) Z.A. Melzal: Companion to Concrete Mathematics. John Wiley
& Sons. 1973;

-) Pawel Winter: An Algorithm for the Steiner Problem in the
Euclidian Plane. In: Networks, Band 15, Heft 3, S. 323-345,
1985.

Ich hoffe, es geht um dieses Problem. Anderswo kenne ich keine
Steiner-Bäume.

CU,

Frank.

Vielen Dank, ich werd mir das mal angucken.

5

Zwei Varianten

  1. Graphentheoretisch:
    gegeben ein Graph G und eine Teilmenge X der Knotenmenge V. Finde einen Baum minimalen Gewichts/minimaler Groesse etc. der alle
    Knoten aus der Teilmenge verbindet (wenn X=V dann ist es das
    minimale Spannbaumproblemm)

  2. geometrisch: gegeben k Punkte in der Ebene. fuege moeglichts wenige Punkte hinzu, so dass mann mit ausgewählten (geraden) Punkt zu Punkt Verbindungen eine moeglicht kurze Verbindung der
    k Punkte erzeugen kann.

was Literatur angeht, muesste in den meisten Buechern zu Approximationsalgorithmen was drinstehen.

MFG
Martin