einfache Graphentheorie < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Menge N(v) = { u [mm] \in [/mm] V | {u,v} [mm] \in [/mm] E} drückt die benachbarten Knoten zu v aus. |
Bedeutet das für folgendes Beispiel:
u - v - r
|
s
N(v) = {u [mm] \in [/mm] V | {u,v,r,s} [mm] \in [/mm] E} = u,r,s
?
Frage 2:
Was ist gemeint mit:
"Adjazenslisten [mm] \rightarrow [/mm] wahre Größe eines Graphen"
Ist das so gemeint, das sie im Endeffekt ja die Anzahl von E, also |E| darstellen?
"Adjasenzmatritzen [mm] \rightarrow [/mm] per Definition [mm] |V|^2"
[/mm]
also hier eher die Ordnung bestimmen als die Größe?
Okay soweit erstmal :)
|
|
| |
|
Inhaltlich ja, aber die Schreibweise ist wohl nicht richtig. Irritierend ist vor allem, dass die vorher allgemeine Variable u nun einen Knoten bezeichnet. Deine Lösungsmenge musst Du also anders beschreiben:
N(v)= {i [mm] \in [/mm] V | (i,v) [mm] \in [/mm] E} = {u,r,s}
da ja (u,v), (r,v), (s,v) [mm] \in [/mm] E.
Nebenbei: schreibt Ihr die Kanten wirklich in geschweiften Klammern?
> Frage 2:
>
> Was ist gemeint mit:
>
> "Adjazenslisten [mm]\rightarrow[/mm] wahre Größe eines Graphen"
>
> Ist das so gemeint, das sie im Endeffekt ja die Anzahl von
> E, also |E| darstellen?
Das kommt ganz darauf an, welche Form von Adjazenzlisten Ihr verwendet! Für ungerichtete Graphen gibt es durchaus auch die Form, wo die Liste für jeden Knoten alle mit ihm verbundenen Knoten aufführt. Immerhin aber wird selbst in dieser Form kein Speicherplatz (darum gehts doch, oder?) für die nicht verbundenen Knoten aufgewandt.
> "Adjasenzmatritzen [mm]\rightarrow[/mm] per Definition [mm]|V|^2"[/mm]
Adjazenzmatrizen haben nun einmal die Größe [mm] v\times \a{}v [/mm] ...
> also hier eher die Ordnung bestimmen als die Größe?
Wieso das denn?
> Okay soweit erstmal :)
lg,
reverend
PS: Insgesamt mehr Mut zum orthographischen "z". Matrizen haben nur das eine "t", und Adjazenz ist ein "s"-freies Phänomen.
|
|
|
|
