Mathematik: Diskrete Mathematik: Graphentheorie

Aus Wikibooks

Wechseln zu: Navigation, Suche
Go-up.svg Hoch zu Diskrete Mathematik Inhaltsverzeichnis

Baustelle.svg


An diesem Kapitel wird gerade gearbeitet. Bitte keine Änderungen vornehmen oder vorher kurz Verbindung mit dem gerade aktiven Autor aufnehmen: SpiderTom.
Hinweis: Dieser Vermerk muss nicht beachtet werden, wenn die Unterschrift schon älter als einen Tag ist.

Gez.: --enomil 18:19, 5. Mär. 2009 (CET).



Vorwort


Die Graphen, mit denen sich die Graphentheorie beschäftigt, sind eine interessante mathematische Struktur. Sie spielen einerseits eine Rolle bei den Markov-Ketten aus dem Bereich der Wahrscheinlichkeitstheorie, sind ein wichtiges Instrument in fast jeder Disziplin der Informatik - angefangen von Endlichen Automaten aus der Theoretischen Informatik bis hin zur Routenberechnung für Navigationssysteme in der Geoinformatik - und spiegeln dabei Denkstrukturen wieder, die auch im Alltag oft vorkommen. So stehen hinter schematischen Darstellungen von U-Bahnnetzwerken genauso Graphen, wie sie auch hinter einem Organigramm stehen, das die Hierarchie einer Organisation beschreibt. Und so mancher Rätselfreund musste - möglicherweise nach langem Tüfteln - feststellen, dass es vom K3,3 keine planare Darstellung gibt.


Inhaltsverzeichnis

[Bearbeiten] Graphentheorie

[Bearbeiten] Definitionen

[Bearbeiten] Graph

Ein Graph G ist eine mathematische Struktur, die aus einer Knotenmenge V und einer Kantenmenge E besteht. Dabei gilt, dass V\neq\varnothing und V < \infty. Eine Kante verbindet zwei Knoten miteinander und E\subseteq\tbinom{V}{2}.

Schreibweise: G = (V,E)


Ein Beispiel:

Graph G

G = {V,E}

V = {1,2,3,4,5,6}

E = {(1,2),(1,5),(2,3),(2,5),(3,4),(4,5),(4,6)}










[Bearbeiten] Nachbarschaft und Grad

Zwei Knoten x,y\in{V} heißen benachbart (auch adjeziert), wenn \{x,y\}\in E.

Im obigen Beispiel sind z.B. 1 und 2 benachbart, 1 und 3 aber nicht.


Die Menge NG(x) wird als Nachbarschaft des Punktes x im Graphen G bezeichnet. Es gilt N_G(x)=\{y\in V:\{x,y\}\in E\}.

Im obigen Beispiel ist z.B. NG(2) = {3,5}.


Als Grad von x bezeichnet man deg(x) = | NG(x) | .

Im obigen Beispiel ist somit deg(2) = 2.


Ein Knoten x wird als isoliert bezeichnet, wenn deg(x) = 0.

Ein Konten x wird als Blatt bezeichnet, wenn deg(x) = 1.

[Bearbeiten] Isomorphe Graphen

Zwei Graphen G1 = (V1,E1) und G2 = (V2,E2) heißen isomorph, wenn es eine Bijektion f: V_1 \rightarrow V_2 gibt, so dass \forall x,y \in V_1 : \Bigl\{\{x,y\} \in E_1 \Rightarrow \{f(x), f(y)\} \in E_2 \Bigr\}.

[Bearbeiten] Subgraph

Ein Graph H=(W,F) heißt Subgraph von G=(V,E), wenn W \subseteq V und F \subseteq E.

Schreibweise H \subseteq G.

[Bearbeiten] Induzierter Subgraph

[Bearbeiten] Pfad

[Bearbeiten] Kreis

[Bearbeiten] Klique und Stabile Menge

[Bearbeiten] gerichtete Graphen

In vielen Anwendungen ist es notwendig, den Kanten eine Richtung zu geben. In der Darstellung stellt man diese Richtung durch einen kleinen Pfeil dar.

Hier ein Beispiel für die Darstellung eines gerichteten Graphen: (Graphik stammt aus Wiki-Commons)

Beispiel für eine Darstellung eines gerichteten Graphen

[Bearbeiten] Algorithmen

Von „http://de.wikibooks.org/wiki/Mathematik:_Diskrete_Mathematik:_Graphentheorie“
Persönliche Werkzeuge