[DSAL] Was ist O(|E|)???

[paganlord]

Hoi,

ich hab mal die Klausur von 02 durchgerechnet und Aufgabe 7.13 lautet:
"In zusammenhängenden Graphen gilt |V|=O(|E|) - [ja|nein]"

-> Was zum Geier ist die Komplexität/Komplexitätsklasse einer Kante? Operationen, Algorithmen haben eine Komplexität, aber eine Kante eines Graphen?

[HE]

|E| ist die Kardinalität der Kantenmenge, O(|E|) heißt also "Aufwand beschränkt durch ein konstantes Vielfaches der Anzahl der Kanten".

[paganlord]

|E| ist die Kardinalität der Kantenmenge, O(|E|) heißt also "Aufwand beschränkt durch ein konstantes Vielfaches der Anzahl der Kanten".

Die Bedeutungen von |E| und O sind mir klar, aber O(|E|) habe ich trotzdem noch nicht verstanden.
Soll das jetzt heißen, dass der Aufwand etwas auf den Kanten eines zusammenhängenden Graphen zu machen so hoch ist wie die Anzahl der Knoten? Dann wärs mir vielleicht klar, weil man über die Knoten laufen muss wenn man Kanten passiert (z.B. Eulerkreis) und es keine losen Knoten gibt, die daran etwas ändern.
Aber toll finde ich diese Fragestellung überhaupt nicht, man könnte ja so fragen dass es jemand versteht...

[pulsar]

Dass HE den Begriff Aufwand eingebracht hat, war evtl. etwas unglücklich. Hier im Beispiel ist das so zu verstehen: Anzahl der Knoten ist beschränkt durch ein konstantes Vielfaches der Anzahl der Kanten.

Das lässt sich sicher auch aus der genauen Definition von O() ableiten, aber die hab ich nicht mehr im Kopf. :)

[paganlord]

so ausgedrückt ja (endlich peile ich was die wollen), denn O(f) = {g:N->R+ : ex n0>0 ex c>0 fa n>n0: g(n) < c f(n)}.

Aber das ist trotzdem mal ganz, ganz, ganz fies, wie ich finde

[fw]

|V|=O(|E|)

Das ist eigentlich etwas hässlich ausgedrückt, aber leider unter Informatikern so üblich. Eigentlich meint man , das Gleichheitszeichen ist also nur "symbolisch" gemeint! Falls dich das irritiert hat...

[HE]

Insgesamt ist das aber Standard-Notation, die man *genau* so noch einige dutzend male sehen wird im Verlaufe eine Info-Studiums, also würde ich das nicht als "ganz, ganz, ganz fies" bezeichnen. Wenn man die Bedeutung der verschiedenen Symbole wirklich verstanden hat, ist das ziemlich trivial.

[paganlord]

Ich hab die Aufgabe trotzdem nicht kapiert, obwohl mir alles nötige von O-Notation (incl. ) und Graphentheorie bekannt ist, was eine gute Note in der BuK-Klausur und ein Schein+Proseminar in Graphentheorie bestätigen

Naja, was solls. Jetzt weiß ich was die eigentlich meinen und mach mich auf andere Knüller dieser Art in der Klausur gefasst

[O.D.]

Knüller

Also eigentlich ist das nun wirklich keine besonders schwierige Angelegenheit. Gilt |V|<=k*|E| für fast alle (also, endlich viele Beispiele ausgenommen) Kardinalitäten von E?

[Coolcat]

Nein. Nimm den Graphen ohne Kanten mit n Knoten.

Edit: Oh, oben in der Ausgangsfrage steht was von zusammenhängend...Du brauchst mindestens n-1 Kanten um n Knoten zu verbinden. Daher kann man wohl k=2 setzen, dann gilt es für alle n >= 2.

[O.D.]

Das Fragezeichen am Ende des Satzes sollte eigentlich aussagen, dass ich die Antwort nicht verraten wollte.

[aRo]

hi!

War grad auch etwas verwirrt. Also die Frage ist, ob die Anzahl der Knoten durch ein Vielfaches der Kanten beschränkt ist, nicht wahr?

Das muss aber nicht für alle Graphen gelten, oder? Denn laut Definition muss es nur ab einem bestimmten n0 gelten. (kann ich hier n als Anzahl Knoten wählen?)

D.h.:
Für zusammenhängende Graphen ist das richtig, für unzusammenhängende falsch, weil es unendlich viele Graphen gibt, die mehr Knoten als Kanten haben, egal welche Konstante man nimmt (einfach |E|=0 wählen).

Hab ich das soweit richtig zusammengefasst?

[TheStranger]

Naja, es gibt eine Ausnahme, nämlich der Graph, welcher nur aus einem Knoten besteht und keine Kanten besitzt. Er ist zusammenhängend, doch die Kantenanzahl ist null.

Ansonsten sollte es stimmen, da du für jeden Knoten, der dem Graphen hinzugefügt wird, mindestens eine Kante brauchst, damit dieser mit dem Restgraphen zusammenhängt. Dieses kann man sich gut vorstellen, wenn man den minimalen Spannbaum vor Augen hat. Dann brauch man nämlich immer genau |V|-1 Kanten für diesen.

[aRo]

okay, das ist eine Ausnahme. Die dürfte doch aber nichts daran ändern, dass die Aussage stimmt oder?
Es muss schließlich nur ab einem bestimmten n stimmen (vgl Definition auf Folie) und ich nehme an, man kann hier n=Knotenzahl setzen?

[TheStranger]

ich hab mal die Klausur von 02 durchgerechnet und Aufgabe 7.13 lautet:
"In zusammenhängenden Graphen gilt |V|=O(|E|) - [ja|nein]"

Da ich die Folien nicht habe, habe ich mich nur auf diese Frage bezogen. Laut Aussage soll dies für jeden Graphen gelten, d.h. |V| kann beliebig sein.

Und wenn ich ein Bsp finde, wo die Aussage dann nicht gilt, nämlich |V| = 1, dann ist die Aussage falsch. Falls irgendwo steht, das |V| > 1, dann ist sie richtig

EDIT:
Muss mich hier ein wenig korrigieren. In der O-Notation geht man eigentlich immer von großen Werten aus. Siehe mit . Denke deshalb ist der eine Fall mit |V| = 1 doch zu vernachlässigen.