+2 Daumen
443 Aufrufe

 

kann man es analog so beweisen:

Also mein ansatz lautet

kann mir jemand hier helfen

Aufgabe 4: Breitensuche 3 + 2 PunkteEs sei G = (V, E) ein beliebiger, zusammenhängender Graph in dem ein beliebigerKnoten r als Wurzel gewählt wurde und sei T = (V, E’) ein BFS—Baum von G mit der Wurzel r. Wir suchen allgemeingültige Aussagen über die Durchmesser von Gund T:a) Finden Sie eine möglichst kleine Konstante C1, so dass D(T) 5 C1 - D(G) immergilt (Beweis!). Zeigen Sie durch Beispielgraphen mit D(T) = C1 - D(G), dass C1kleinstmöglich gewählt wurde.
b) Finden Sie eine möglichst kleine Konstante C2, so dass D(G) 5 C2 - D(T) immergilt (Beweis!). Zeigen Sie durch Beispielgraphen mit D(G) = C2 - D(T), dass C2kleinstmöglich gewählt wurde.

Gefragt von

Hi,

also nach deinem Ansatz wäre doch C1=1 oder?

Conde

1 Antwort

0 Daumen
Kann jemand mir sagen was in dem Ansatz mit a und b gemeint ist ? Sonst glaube ich auch ,dass nach dem Ansatz C1=1 ist.
Beantwortet von

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

Willkommen bei der Mathelounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...