Landau Notation < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 09:52 Di 26.02.2013 | | Autor: | hula |
Hallo zusammen
Wenn ich einen Graphen haben, wobei $V$ die Menge der Knoten und $E$ die Menge der Kanten im Graphen bezeichnen, kann ich folgendes irgendwie abschätzen?
Ich würde gerne [mm]\mathcal{O}(|E|+|V|\log (V))[/mm] mit [mm]\mathcal{O}(|E|\log (E))[/mm] nach oben abschätzen. Danke für die Hilfe
hula
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:02 Mi 27.02.2013 | | Autor: | felixf |
Moin hula!
> Wenn ich einen Graphen haben, wobei [mm]V[/mm] die Menge der Knoten
> und [mm]E[/mm] die Menge der Kanten im Graphen bezeichnen, kann ich
> folgendes irgendwie abschätzen?
> Ich würde gerne [mm]\mathcal{O}(|E|+|V|\log (V))[/mm] mit
> [mm]\mathcal{O}(|E|\log (E))[/mm] nach oben abschätzen. Danke für
> die Hilfe
Ist der Graph zusammenhaengend? Dann gilt $|E| [mm] \ge [/mm] |V| - 1$, womit das sofort folgt.
Fuer allgemeine Graphen gilt das nicht, ein nicht zusammenhaengender Graph koennte ja auch $|E| = 0$ haben, waehrend $|V|$ beliebig gross werden kann.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:08 Mi 27.02.2013 | | Autor: | hula |
Hallo felix
Es steht nirgends, dass der Graph zusammenhängend ist. Mein Problem ist, dass von einem "modified Dijkstra" die Rede ist, welcher eine Laufzeit von [mm] $\mathcal{O}(|E|\log|E|)$ [/mm] haben soll. Ich dachte immer, der modifizierte Dijkstra alg. ist, wenn man Fibonacci heaps verwendent. Was kann sonst damit gemeint sein?
hula
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 07:33 Do 28.02.2013 | | Autor: | Helbig |
Hallo hula
> Es steht nirgends, dass der Graph zusammenhängend ist.
Doch. In ![[]](/images/popup.gif) Dijkstras Artikel.
Gruß,
Wolfgang
|
|
|
|
