Auf der Folie 154 des F3-Skripts (S. 149) ist eine Formel für die (maximale) Länge einer Kodierung eines Graphen gegeben:


[img]http://mokrates.de/cgi-bin/texstring?%7CV%7C%20+%203%20*%20%7CE%7C%20-%201%20+%20%5B%20log_%7Bk%7D%20(%7CV%7C)%20%5D%20*%20(%7CV%7C%20+%202*%20%7CE%7C)[/img]

Die eckigen Klammern sollen dabei die "Aufrundungs-Klammern" darstellen.

Kann mir jemand diese Formel anschaulich erklären, d.h. aufschreiben, wofür jeder einzelne Summand steht?

Besten Dank!

Also ich gehe mal davon aus, dass du verstanden
hast, wie diese Kodierung funktioniert. Wenn ein
Graph G=(V,E) kodiert werden soll, erzeugt man
zwei Zeichenketten: eine für die Liste von Knoten
und eine für die der Kanten.

(1) Der Summand [img]http://mokrates.de/cgi-bin/texstring?%7CV%7C%2B%7CE%7C-1[/img] ist die Zahl der Kommata.
(2) Der Summand [img]http://mokrates.de/cgi-bin/texstring?2%5Ccdot%20%7CE%7C[/img] ist die Anzahl der geschweiften
Klammern.
(3) Wenn man alle Elemente von V darstellt als
(gleichlange) Zahlen zur Basis k, braucht man für
die Darstellung eines jeden Elements von V genau
[img]http://mokrates.de/cgi-bin/texstring?%5Clceil%20%5Clog_k(%7CV%7C)%5Crceil[/img] Zeichen. Für die Liste der
Knoten braucht man also (abgesehen von den Kommata,
die gingen ja oben schon ein) [img]http://mokrates.de/cgi-bin/texstring?%5Clceil%20%5Clog_k(%7CV%7C)%5Crceil%5Ccdot%20%7CV%7C[/img] Symbole.
Und für die Liste der Knoten, die ja aus |E| Einträgen
zu je zwei Knoten besteht, erhält man [img]http://mokrates.de/cgi-bin/texstring?2%5Clceil%20%5Clog_k(%7CV%7C)%5Ccdot%20%7CE%7C[/img]
Zeichen.

In der Summe kommt also obiger Ausdrück raus.

Super, danke für die schnelle, ausführliche Antwort [img]http://www.fb18.de/gfx/sensationell.gif[/img]