Hallo, wir haben jetzt eine ganze Weile mit Graphen gearbeitet, aber vermutlich ist es

erstmal an der Zeit, dass wir uns darüber unterhalten, wie man einen Graphen erzeugt.

Denn nicht immer hat man bereits einen Graphen gegeben, also eine Menge von Knoten und wohl

definierte Kanten und Gewichte darauf, sondern oft startet man mit einem Datensatz, also

etwas der Form von D, ist eine Menge von Punkten, x1, xm und diese xi sind Daten und Datenpunkte

mit verschiedenen Einträgen, also zum Beispiel könnte es jetzt zwar sein, wie bei diesem

Beispiel mit den gebrauchten Autos, dann ist der erste Eintrag von diesem xi eventuell

die Marke, der zweite ist das Baujahr, der dritte ist der Preis, das vierte ist vielleicht

ein Textfeld, wo Mängel beschrieben werden, zum Beispiel, das heißt es ist ein kompensiertes

Objekt und die Frage ist, wie baut man aus so einem Datensatz einen Graphen?

Und die Idee ist hier die folgende, also wir formulieren das Ganze erstmal in einem Datentraum,

das heißt dieses geschwungen D ist jetzt der Raum, in dem die Datenobjekte xi drin liegen,

das heißt diese Daten ist jetzt eine M-fache Kopie von diesem Datentraum.

Beim einfachsten ist der Fall, wo der Datentraum der R hoch N ist, das heißt xi ist in R hoch

N, ist aber nicht notwendigerweise so in der Falle.

Also jetzt bauen wir eine Abstandsfunktion, die uns erlaubt zu zwei geren Daten xi und

xj einen Abstand zu definieren.

Das ist jetzt hier ein bisschen falsch, also was hier dranstehen soll ist das hier, das

heißt wir nehmen zwei Daten x und y, ich schreibe es x und y und das ist dann eine reelle

Karte, die Größe gleich Null ist, das heißt ist das hier Größe gleich Null.

Und damit können wir jetzt einen vollständigen Graphen bauen, also zum Beispiel sagen wir

mal wir haben jetzt hier diese vier Datenpunkte, das ist x1, das ist x2, x3 und x4 und hier

in diesem Bild sind die xi natürlich in R2, so wie ich sie zeichne.

Das heißt zu einer geren Abstandsfunktion, also zbd von x und y könnte jetzt einfach

der ökologische Abstand sein von x und y, das ist eine Wahl die möglich ist.

Dann können wir diese Punkte einfach zeichnen und die Abstände zwischen ihnen, das sind

einfach die ökologischen Abstände, das heißt jeder Punkt ist mit jedem Punkt verbunden

und die Gewichte auf diesen Kanten sind die ökologischen Abstände zwischen ihnen.

Das kann man machen, das Problem ist aber wenn wir jetzt wirklich jeden Knot mit jedem

anderen Knoten verbinden, dann ist die Größe der Kantenmenge extrem groß, das ist quasi

die Quartaratschneider Anzahl der Knoten, das wollen wir also nicht machen, also wenn

wir zum Beispiel 10.000 Knoten haben, dann haben wir bereits 100 Millionen Kanten, das

ist einfach viel zu viel.

Das heißt was man eigentlich stattdessen machen möchte ist einen unvollständigen Graphen

zu erzeugen aus diesem Datenplatz.

Also gerade zum Beispiel wenn man viele Punkte hier hat und viele Punkte hier hat, dann möchte

man eigentlich nicht dass jetzt jeder Punkt von da mit jedem Punkt von hier verbunden

ist, sondern möchte eigentlich hier irgendwelche Verbindungen hier drin haben, vielleicht sowas

und hier irgendwelche Verbindungen, es geht jetzt hier nur ganz grob ein und dann hat man

vermutlich hier Gewichte dazwischen, vielleicht diese hier, irgendwas in der Art wie das hier,

das heißt es gibt schon eine gewisse Verbindung zwischen diesen beiden Cluster wenn man das

so möchte, aber nicht jeden Knot mit jedem Knot verbinden, das möchten wir gerne vermeiden.

Und welche Möglichkeiten so einen unvollständigen Graphen zu bauen gibt es?

Es gibt mehrere Alternativen, aber jetzt möchte ich gerne über drei spezielle sprechen.

Die erste Möglichkeit ist, man betrachtet erstmal den vollständigen Graphen, also man

muss ihn nicht tatsächlich aufbauen, weil wie gesagt diese ganzen Kanten, die Anzahl

davon die skaliert ziemlich schnell hoch, aber man kann ja zu jeder virtuellen oder

abstrakten Kante das Gewicht einfach ausrechnen über diese Abstandfunktion, also man stellt

sich den quasi erstmal vor, aber dann berechnet man den minimalen aufspannenden Baum aus

diesen vollständigen Graphen, das heißt, jetzt machen wir mal ein Beispiel, vielleicht