Den längsten Ast eines Grafen finden

[asdf_a47399]

Hallo,

ok, etwas zur Einstimmung zu meine Frage: Ein Graf besteht aus aneinandergehängten Teilabschnitten, die alle eine idividuelle Länge haben. An jeden Teilabschnitt kann nun eines oder mehrere weitere Teilabschnitte anhängen, sodass Verzweigungen entstehen. Einzelne Verzweigungen können als Äste aufgefasst werden. Ein Ast besteht somit aus mehreren Teilabschnitten. Da ein einzelner Ast aus mehreren Teilabschnitten besteht, welche eine idividuelle Länge haben, ist somit die Länge des Astes von der Länge seiner einzelnen Teilabschnitte abhängig.

Frage: Gibt es einen Alogrithmus oder Bestimmungsmethode (für ein Programm) mit den ich mir den längsten Ast mir bestimmen kann?

Besten Dank im Voraus und viele Grüße!

[Newlukai_48fe0e]

Hallo,

das hört sich für mich nach einem Baum an. Ist der Graph (ein Graf ist was anderes ) denn kreis-/zyklusfrei? Falls ja, ist die Höhe des Baums relativ einfach über eine Rekursion zu bestimmen.

function bestimmeHoehe(Knoten k) {
 Wenn k kein Kind hat
 Gib 1 zurueck
 Sonst
 Gib ((Maximum der Hoehen der Kinder) + 1) zurueck
}

Gruß
Newlukai