Big-O Notation und Graphen Darstellungen mit Hilfe der Big-O-

Question

Frage:

Ein gerichteter Graph G = (V, E) kann durch eine Adjazenzliste, eine Adjazenzmatrix oder eine
Inzidenzmatrix repräsentiert werden. Finden Sie für jede der Darstellungen mit Hilfe der Big-O-
Notation geeignete Abschätzungen für die folgenden Aufgaben:

Aufgabe:


a) Zeigen Sie: Mindestens einer der Graphen G oder G¯ ist zusammenhängend.
b) Widerlegen Sie: Höchstens einer der Graphen G¯ oder G ist zusammenhängend.

Answer 1

a) Sei \(G\) nicht zusammenhängend mit Zusammenhangskomponenten \(V_1,\dots,V_n\).

Sei \(v_i\in V_i\) für jedes \(i\in\{1,\dots,n\}\). Dann existiert in \(\overline G\) der Weg \(v_1\rightarrow \dots\rightarrow v_n\) auf dem jedes der \(v_i\) liegt.

Sei \(w\in V_1\). Dann existiert in \(\overline G\) der Weg \(v_1\rightarrow v_2 \rightarrow w\).

Also ist \(\overline G\) zusammenhängend.

b) Finde einen zusammenhängenden Graphen, dessen Komplement zusammenhängend ist.

Comments

Danke dir .

Ich habe noch eine Aufgabe:


Ein gerichteter Graph G = (V, E) kann durch eine Adjazenzliste, eine Adjazenzmatrix oder eine
Inzidenzmatrix repräsentiert werden. Finden Sie für jede der Darstellungen mit Hilfe der Big-O-
Notation geeignete Abschätzungen für die folgenden Aufgaben:

a) Überprüfung, ob für u, v ∈ V eine Kante von v nach u existiert
b) Bestimmung des Innengrades d- (v) für einen Knoten v ∈ V
c) Überprüfung, ob es einen Knoten v ∈ V mit Außengrad d+ (v) = 0 gibt

Ich wäre sehr dankbar .