+2 Daumen
464 Aufrufe

Aufgabe: Breitensuche 

Es sei G = (V, E) ein beliebiger, zusammenhängender Graph in dem ein beliebiger Knoten 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 G
und T:

a) Finden Sie eine möglichst kleine Konstante \( C_1 \), so dass \( D(T) ≤ C_1 · D(G) \) immer gilt (Beweis!). Zeigen Sie durch Beispielgraphen mit \( D(T) = C_1 · D(G) \), dass \( C_1 \) kleinstmöglich gewählt wurde.

b) Finden Sie eine möglichst kleine Konstante \( C_2 \), so dass \( D(G) ≤ C_2 · D(T) \) immer gilt (Beweis!). Zeigen Sie durch Beispielgraphen mit \( D(G) = C_2 · D(T) \), dass \( C_2 \) kleinstmöglich gewählt wurde.


Mein Ansatz:

Kann man es analog so beweisen?

$$ | | a | - | b | | \leq | a - b | \\ < + | b | > \\ \Rightarrow \| a | - | b | + | b | | \leq | a - b + | b | | \\ \\ \begin{array} { r } { < | a | - | b | + | b | = | a | > } \\ { \Rightarrow | a | \leq | a - b + | b | | } \end{array} \\ \\ \begin{aligned} < a & = a - b + b > \\ \Rightarrow | a - b + b | & \leq | a - b + | b | | \end{aligned} \\ \\ \begin{array} { r l } { < | a - b | \text { eliminieren } > } \\ { \Rightarrow b \leq | b | } \end{array} \\ \\ \begin{array} { l } { b \geq 0 \Rightarrow b = | b | } \\ { b < 0 \Rightarrow b < | b | } \end{array} $$

Kann mir jemand helfen?

Gefragt von

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.

Bitte logge dich ein oder registriere dich, um die Frage zu beantworten.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...