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} $$
