home  |  suche  |  kontakt/johner  |  institut 
studierende  |  tech-docs  |  mindmailer 

Graphen

Ein Graph sind durch Kanten verbundene Knoten. Die Unterschiede zu Bäumen sind

  • es sind mehrere Vorgängerelemente möglich
  • es kann mehre Wurzelelelemente geben
  • zyklische Abhängigkeiten sind erlaubt.

In einem Graphen, können gerichtete und ungerichtete sowie gewichtete und ungewichtete Kanten existieren. Eine Beispielanwendung für einen Graphen mit gewichteten Kanten ist z.B. eine Routenplanung, dabei entsprechen die Gewichtungen den Entfernungen.

Für die Implementierung eines Graphens ist es sinnvoll zuerst eine Adjazenzmatrix zu erstellen. Dafür wird eine quadaratische Matrix mit allen Knoten als Spalten wie auch Reihen aufgestellt. Für jede existierende Verbindung wird eine 1 oder auch die Gewichtung der Kante eingetragen.

Für jeden Knoten kann nun eine lineare Liste angelegt werden. Jeder linearen Liste werden nun alle Knoten hinzugefügt, die in der Reihe des jeweiligen Knotens durch eine Zahl als verbundenen Knoten markiert sind. Das heisst für den Knoten 1 werden die Knoten 2 und 4 angehängt, weil in der Reihe für Knoten 1 bei den Knoten 2 und 4 eine Zahl steht. Die Implementierung für diesen Graphen muss wie folgt aussehen.

Spezielle Graphen

In der Graphentheorie gibt es spezielle Graphen, den Eulerschen Kreis und den Eulerschen Weg.

Eulerscher Kreis: an jedem Knoten gibt es eine gerade Anzahl von Kanten, er kann mit einem Rundweg durchlaufen werden

Eulerscher Weg: es gibt genau 0 oder 2 Knoten mit ungerader Kantenanzahl

Es gilt: Eulerscher Kreis ist immer ein Eulerscher Weg (Umkehrschluss gilt nicht!!)

So ist z.B. das Haus vom Nikolaus kein Eulerscher Kreis aber ein Eulerscher Weg (beide unteren (=genau 2) Knoten haben nur 3 Kanten), siehe folgendes Beispiel.

Page-Rank Algorithmus

Das Erfolgsgeheimnis der Google-Suchmaschine ist das Page-Rank-Verfahren. Der Hauptakspekt dieses Verfahren ist, "wichtige" Internet-Seiten von "unwichtigen" Internet-Seiten zu unterscheiden. Dazu soll jede internetseite einen eigenen PageRank definiert bekommen, die deren Wichtigkeit bewertet.

Der PageRank einer einer Seite berechnet sich wie folgt

 PR(a) = d*(PR(T1)/C(T1)+....+PR(Ti)/C(Ti))+(1-d)*(1/AnzahlSeiten)

dabei ist PR(a) der PageRank der Seite a

               PR(Ti) der PageRank der Seiten Ti, von denen ein Link auf Seite a zeigt

               C(Ti) die Gesamtzahl der Links auf Seite Ti

                d      ein Dämpfungsfaktor.

Der Dämpgunsfaktor liegt zwischen 0 und 1 und soll das Ausmaß der Weitergabe des PageRanks von einer Seite auf eine andere verringern. Das ist deswegen notwendig, weil nicht immer von einer Seite zur anderen navigiert wird, manchmal wird auf eine Seite direkt zugegriffen, oder mit dem Rückwärtsbutton eine vorherige Seite aufgerufen. Die Navigationsmöglichkeiten über Links werde damit übergangen.

Um die Formel mit ihren etwas kryptischen Variablen besser zu verstehen soll folgendes Beispiel helfen. Die folgende Abbildung zeigt 6 Webseiten, die über Links miteinander verbunden sind.

Der Dämpungsfaktor d ist hier 4/5, die Anzahl der Seiten ist gleich 6, es gilt

PR(A) = 4/5 * (PR(D)/3)+ 1/5 * 1/6

dabei ist  PR(T1)/C(T1)                 = PR(D)/3

                (1-d)*(1/AnzahlSeiten) = 1/5 * 1/6

                d                                   = 4/5

die anderen Seiten haben folgenden PageRank

PR(B) = 4/5 * (PR(A)/2 + PR(E)/1) + 1/5 * 1/6

PR(C) = 4/5 * (PR(B)/3 + PR(D)/3) + 1/5 * 1/6

PR(D) = 4/5 * (PR(A)/2 + PR(B)/3 + PR(C)/1) + 1/5 * 1/6

PR(E) = 4/5 * (PR(B)/3) + 1/5 * 1/6

PR(F) = 4/5 * (PR(D)/3) + 1/5 * 1/6

Diese Pagerankformeln für jede Seite stellen normale Gleichungen auf, sie können wie ein normales Gleichungsystem gelöst werden. Falls eine Seite keinen Vorgänger hat, das heißt es gibt keine Links über die die Seite erreicht werden kann, fällt der vordere Teil weg und es gibt bereits eine Lösung, die dann durch Substitution den anderen Gleichungen die Lösung bringt. Die Einstufung einer Webseite bei der Ergebnisseliste von Google hängt aber natürlich nicht nur von dem Ergebnis dieser Gleichung ab. Es fließen auch folgende Dinge mit in die Bewertung mit ein

  • Metakey-words
  • Content, Suchbegriffsdichte, Postition im Text
  • Ist die Seite überhaupt lesbar? Erreichbar? Frames?
  • ...