EntwurfRZ

Wiki-Quelltext dieser Seite.

=Relevanz und Motivation=

==Entstehung von Theorien und Modellen==
* Meist aus einem praktischen Problem heraus
* Zusammentragen aller Fakten die damit irgendwie zu tun haben
* Weglassen aller Dinge die keinen direkten Einfluss haben
* Verallgemeinerung / Abstraktion
* Finden von Ähnlichkeiten mit bekannten einfacheren Dingen
* Entwurf eines Modells mit diesen einfacheren Dingen
* Verhältnismäßig einfache Bestimmung von übertragbaren Eigenschaften und Konsequenzen

==Leonard Euler 1737==
* Problem der Königsberger Brücken
* Weglassen von Entfernungen und Ausmaßen
* Einfluss haben nur Stadtteile und Brücken
* Abstraktion zu Punkten mit Verbindungslinien
* Lösung des Problems mit Punkten und Verbindungen löst auch das Problem mit Stadtteilen und Brücken
* Entstehung des Graphenmodells

==Die Graphentheorie als Modell==
* Sehr minimalistisch, nur Punkte mit Verbindungen
* Dadurch übertragbar auf alle Arten von Beziehungen zwischen Objekten 
** Städte und Zugverbindungen
** Freundschaften zwischen Menschen
** Verlinkung von Internetseiten
* Viele praktische Probleme lassen sich zu einem Graphenproblem umformulieren
** Ausfallwahrscheinlichkeit von Netzwerken
** Routenermittlung bei der Navigation
** Einstufung der Wichtigkeit von Einzelnen in einer Gruppe
* Graphentheorie stellt bereits Lösungen zur Verfügung
* Meist ist "nur noch" eine Interpretation erforderlich

==Arbeiten mit dem Graphenmodell==
* Mathematik des Modells ist gut dokumentiert
* Kritisch sind die Transformationen
** Formulierung eines praktischen Problems im Graphenmodell
** Interpretation des mathematischen Ergebnisse für die Praxis
* Falsche Formulierung oder falsche Interpretation liefert keine Problemlösung
* Zeitverteilung eines Softwareentwicklers: 10% tippen, 90% denken
* Gute Programmierer denken immer abstrakt (also in Modellen)
* Wenn man viele Modelle kennt, muss man sich selbst keine ausdenken
* Die Einfachheit der Graphentheorie macht sie zu einem Universalmodell

=Knoten und Kanten=
;Definition Graph
:$G=(V,E)|V=\{v_i|i>0\}, E=\{(v_i,v_j)|\{v_i, v_j\} \in V\}$

<popup name="Ausführliche Definition">
;Definition Graph
:$\color{red}G=\color{blue}(V,E\color{blue})\color{magenta}|V=\color{green}\{v_i \color{magenta}| i>0\color{green}\},E=\color{green}\{\color{blue}(v_i,v_j\color{blue})\color{magenta}|\{v_i, v_j\} \in V\color{green}\}$
<br/>
:Ein $\color{red}{Graph}$ ist ein $\color{blue}{geordnetes Paar}$, $\color{magenta}{wobei}$ dessen erstes Element eine $\color{green}{Menge}$ ist, $\color{magenta}{welche}$ nicht leer sein darf, und dessen zweites Element eine $\color{green}{Menge}$ von $\color{blue}{geordneten Paaren}$ ist, $\color{magenta}{deren}$ Elemente in der ersten Menge enthalten sein müssen.
<br/>
:Ist eine Menge von Knoten die durch Kanten verbunden sein können.
</popup>

==Was ist ein Graph==
Zur grafischen Darstellung bieten sich Punkte und Linien an:<br/>
Bilder: Punkt, nur Kante, Kante mit einem Punkt, Punkt mit Schlinge, 3 Punkte, 3 Punkte mit nur einer Kante, 2 Kanten mit Punkten nebeneinander, 2 Punkte die durch mehrere Kanten verbunden sind, Punkte die durch geschwungene Kanten verbunden sind

==Konsequenzen==
* Ein Graph muss mindestens einen Knoten enthalten
* Ein Graph muss nicht unbedingt Kanten haben
* Eine Kante muss immer durch 2 (nicht zwingend verschiedene) Knoten begrenzt sein
* Ein Knotenpaar kann durch mehrere Kanten verbunden sein
* Zwei Graphen sind gleich, wenn sie die gleichen Knoten enthalten, die durch die gleichen Kanten verbunden sind
* Adjazenz = Nachbarschaft = Es gibt etwas trennendes dazwischen
** Nur zwischen Knoten und Knoten bzw. zwischen Kante und Kante
** Dazwischen ist immer eine Kante oder ein Knoten
* Inzidenz = Angrenzung = Es gibt direkten Kontakt
** Nur zwischen Knoten und Kante

==In der Praxis==
* Knoten und Kanten werden immer als Objekte mit Beziehungen interpretiert
* Dadurch werden die Konsequenzen intuitiv klar
* Erst wenn es ein Objekt gibt, kann man etwas darüber aussagen: "ist allein"
* Zwei Objekte ohne Verbindung sind auch sinnvoll: "nicht allein, aber isoliert"
* Eine Beziehung findet per Definition immer zwischen Objekt'''en''' statt
* Objekte müssen dabei nicht zwingend verschieden sein (z.B. Besitzer$\leftrightarrow$Eigentümer)

==Modellierung==
* Transformation einer Gegebenheit/eines Problems ins Graphenmodell
* Scheinbar offensichtlich (Computernetzwerke, Straßen, Facebook-Freundschaften)
* In der Praxis: Immer abhängig von der Problemstellung!
* z.B. Stromkabelverlegung in einem Haus
** Wie verlegt man die Kabel, sodass die verwendete Gesamtkabellänge minimal ist?
** Wie teile ich eine 50m Kabelrolle auf, sodass der Verschnitt möglichst gering ist?
* Kein Patentrezept um von der konkreten Problemstellung zum abstrakten Graphenmodell zu gelangen
* Hilfreiche Fragen die man sich stellen kann
** Welches Ergebnis wird gebraucht?
** Welches Ergebnis der Graphentheorie soll genutzt werden?
* Oft helfen Zwischen-Abstraktionen anstatt direkt zu Knoten und Kanten zu abstrahieren
** Zustände und deren Übergänge
** Situationen und deren Änderung
* Grafische Darstellung von Graphen kann geometrische Körper ergeben

=Programmiertechnische Verarbeitung=
* Wahl der Datenstruktur nach Problemstellung und Problemgröße

==Hilfsmittel==
* Abhängig von der Programmiersprache

==Adjazenzmatrix==
* Abbildung, Funktionsweise, Zugriff, Codebeispiel,...

==Adjazenzliste==

==Kantenliste==

==Die Qual der Wahl==
*Gegenüberstellung

=Grad eines Knotens=
;Definition
:$d(v)=|\{\{v, w\}|\{v, w\} \in E\}|$

<popup name="Ausführliche Definition">
;Definition
:$\color{red}d(\color{orange}v)=\color{blue}|\color{green}\{\color{black}{\{v, w\}}\color{magenta}{|\{v, w\} \in E}\color{green}\}\color{blue}|$
<br/>
:Der $\color{red}{Grad}$ eines $\color{orange}{Knotens}$ ist die $\color{blue}{Mächtigkeit}$ der$ \color{green}{Menge}$ an $\color{black}{Kanten}$, $\color{magenta}{aus~der~Gesamtmenge~der~Kanten~des Graphen}$, die zu v inzident sind.
<br/>
:Die Anzahl der Kantenenden die an einem Knoten anliegen.
</popup>

==Konsequenzen==
* Einzelner Knoten ohne anliegende Kanten hat Grad 0 (isolierter Knoten)
* Schleife an einem Knoten erhöht den Grad um 2
* Ein Graph hat: Minimalgrad, Maximalgrad, Durchschnittsgrad
* Wichtig: $\sum_{i=1}^n d(v_i)=2\cdot m$
** Summe aller Grade entspricht doppelter Kantenanzahl im Graph
** Da jede Kante den Grad ihrer 2 angrenzenden Knoten um 1 erhöht
* Daraus folgt: Anzahl der Knoten mit ungeradem Grad muss gerade sein, denn<br><popup name="Beweis">
# Summe aller Grade ist $\color{blue}{gerade}$ wegen $\textbf{2}\cdot m$
# Summe aller $\color{blue}{geraden}$ Grade ist auch $\color{blue}{gerade}$
# Wegen 1. muss die Summe aller $\color{red}{ungeraden}$ Grade auch $\color{blue}{gerade}$ sein
# Wegen 3. muss die Anzahl der Knoten mit $\color{red}{ungeradem}$ Grad $\color{blue}{gerade}$ sein
</popup>
* Haben alle Knoten den gleichen Grad ist der Graph regulär<br/>genauer: bei Grad k $\leftarrow$ k-regulär
*

=Isomorphie=