Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenDonnerstag, 18. Juli 2019 

Typen von Graphen in der Graphentheorie


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.

Inhaltsverzeichnis

Einleitung

Anschaulich besteht ein Graph in der Graphentheorie aus einer Menge von Punkten zwischen Linien verlaufen. Die Punkte nennt man Knoten oder Ecken die Linien nennt man meist Kanten manchmal auch Bögen . Auf die Form der Knoten und kommt es im allgemeinen dabei nicht an.

In so genannten Multigraphen können zwei Knoten auch durch mehrere verbunden sein was in einfachen Graphen nicht ist. Statt mehrere Linien zwischen zwei Punkten zeichnen kennzeichnet man Mehrfachkanten auch häufig durch Vielfachheit.

In gerichteten Graphen werden Kanten statt durch Linien durch gekennzeichnet wobei der Pfeil vom ersten zum Knoten zeigt.

Hypergraphen sind meist nur schwer vor-/darstellbar. In Regel zeichnet man eine Menge von Punkten den Knoten entsprechen welche durch geschlossene Linien werden. Die geschlossenen Linien entsprechen dann den Hyperkanten .

Definitionen

Ein Graph G ist ein Tupel ( V E ) wobei V eine Menge von Knoten (oft auch Ecken genannt) und E eine (höhere) Menge von Kanten (manchmal auch Bögen genannt) bezeichnet. Dabei ist E in

  • ungerichteten Graphen ohne Mehrfachkanten eine Teilmenge aller 2-elementigen Teilmengen von V
  • gerichteten Graphen ohne Mehrfachkanten eine Teilmenge des kartesischen Produktes V x V
  • ungerichteten Graphen mit Mehrfachkanten eine Multimenge über der Menge aller 2-elementigen Teilmengen V
  • gerichteten Graphen mit Mehrfachkanten eine Multimenge über dem kartesischen Produkt V x V
  • Hypergraphen eine Teilmenge der Potenzmenge von V .

Den Zusatz "ohne Mehrfachkanten" lässt man weg und nennt Graphen mit Mehrfachkanten Multigraphen . Ferner verzichtet man meist auf das "ungerichtet" und kennzeichnet nur gerichtete Graphen explizit. Graphen ohne Mehrfachkanten nennt man auch häufig schlicht oder einfach . Eine andere Bezeichnung für gerichtete Graphen Digraph .

Um kürzer schreiben zu können definiert gewöhnlich zwei Abbildungen V und E die einem Graphen G =( V E ) seine Knoten- bzw. Kantenmenge zuordnen d.h. V ( G ) := V und E ( G ) := E . Man beachte dass trotz der selben ( V bzw. E ) die Knoten- bzw. Kantenmenge etwas anderes die gerade definierten Abbildungen darstellen. Wenn es anders gesagt wird meinen V bzw. E ohne Argument gewöhnlich die Knoten- bzw. Kantenmenge des betrachteten Graphen. V bzw. E mit Argument meinen hingegen immer die definierten Abbildungen deren Ergebnis dann natürlich wieder Knoten- bzw. Kantenmenge ist und zwar die als Argument angegebenen Graphen.

Ist G ein Graph so sagt man allgemein v ist Knoten (bzw. Ecke ) von G wenn v zu V ( G ) gehört. Ferner sagt man falls G

  • ungerichteter Graph ohne Mehrfachkanten ist und e zu E ( G ) gehört e ist eine ungerichtete Kante von G
  • gerichteter Graph ohne Mehrfachkanten ist und e zu E ( G ) gehört e ist eine gerichtete Kante von G
  • ungerichteter Graph mit Mehrfachkanten ist und E ( G )( e ) > 0 e ist eine ungerichtete Kante von G
  • gerichteter Graph mit Mehrfachkanten ist und E ( G )( e ) > 0 e ist eine gerichtete Kante von G
  • Hypergraph ist und e zu E ( G ) gehört e ist eine Hyperkante von G .
In einer ungerichteten Kante e ={ v w } bezeichnet man v und w als Endknoten von e . In einer gerichteten Kante e =( v w ) bezeichnet man v als Startknoten und w als Endknoten von e .

Ist in Multigraphen sogar E ( G )( e ) > 1 so spricht man auch einer Multi- oder Mehrfachkante . E ( G )( e ) bezeichnet man auch als die Vielfachheit von e . Hat eine Kante e in gerichteten Graphen die Form ( v v ) so spricht man von einer Schleife . Ist e in einem Multigraphen G zusätzlich eine Mehrfachkante so spricht man einer Mehrfachschleife . Eine 1- oder 2-elementige Menge von Paaren mit der Eigenschaft dass sie neben v w ) auch ( w v ) enthält (im 1-elementigen Fall ist dies nur bei v = w möglich) nennt man falls G

  • gerichteter Graph ohne Mehrfachkanten ist und sowohl v w ) als auch ( w v ) Kante von G sind ungerichtete Kante von G
  • gerichteter Graph mit Mehrfachkanten ist und E ( G )(( v w )) = E ( G )(( w v )) ungerichtete Kante von G .
1-elementige ungerichtete Kanten in gerichteten Graphen offensichtlich also immer Schleifen. Umgekehrt lässt sich jeder Schleife e leicht eine ungerichtete Kante konstruieren (nämlich e }). Schleifen sind in diesem Sinne also ungerichtet weshalb man gewöhnlich das Attribut "gerichtet" lässt. Ist jede Kante eines gerichteten Graphen G Element einer ungerichteten Kante von G so nennt man G auch symmetrisch .

Man lässt gewöhnlich in ungerichteten Graphen Attribut "ungerichtet" für Kanten weg. In gerichteten lässt man das Attribut "gerichtet" für Kanten nur dann weg falls man keine ungerichteten Kanten betrachtet. In Hypergraphen sagt man Hyperkante auch oft einfach nur Kante.

Gerichtete Graphen ohne Schleifen nennt man schleifenlos oder schleifenfrei .

Als Knotenzahl n ( G )=| V ( G )| eines Graphen G bezeichnet man die Anzahl seiner Knoten Kantenzahl m ( G )=| E ( G )| bezeichnet man die Anzahl seiner Kanten Multigraphen summiert man über die Vielfachheit der

Einen Graph dessen Knotenmenge endlich ist man endlicher Graph . Zwangsläufig ist in diesen auch die endlich. Im Gegensatz dazu nennt man einen dessen Knotenmenge unendlich ist unendlicher Graph . Meist betrachtet man nur endliche Graphen lässt daher das Attribut "endlich" weg während "unendliche Graphen" explizit kennzeichnet.

Bemerkungen

Ungerichtete Graphen ohne Mehrfachkanten sind offensichtlich von Hypergraphen. Multigraphen in denen keine Mehrfachkanten sind zwar nicht formal aber anschaulich äquivalent Graphen ohne Mehrfachkanten weshalb man auch diese Graphen ohne Mehrfachkanten bezeichnet. Es gibt offensichtlich einfache bijektive Zuordnung zwischen den beiden Varianten. diesem Sinne sind Graphen ohne Mehrfachkanten also von Graphen mit Mehrfachkanten. Ähnlich verhält es mit ungerichteten Graphen die in gewissem Sinn von gerichteten Graphen sind. Ist ein gerichteter symmetrisch und schleifenlos so bezeichnet man diesen als ungerichtet da es offensichtlich auch hier eine eineindeutige Zuordnung zwischen beiden Varianten gibt (siehe Repräsentation von Graphen im Computer ).

Es lassen sich natürlich auch ungerichtete mit Schleifen definieren wobei man diese wohl einfachsten wie eben als (formale) Spezialfälle von Graphen definiert und die Bedingung der Schleifenlosigkeit lässt. Solche Graphen sind aber nur selten der Betrachtungen in der Graphentheorie.

Der wohl allgemeinste Typ von Graphen gerichtete Hypergraphen mit Mehrfachkanten. Jeder oben definierte kann dann als Spezialfall von diesem betrachtet Solche Graphen sind aber so gut wie nicht Gegenstand der Betrachtungen in der Graphentheorie sie hier auch nicht näher erläutert werden.

Erweiterungen

Oft erweitert man Graphen G =( V E ) zu knotengefärbten Graphen indem man das Tupel ( V E ) zu einem Tripel ( V E f ) ergänzt wobei f eine Abbildung von V in die Menge der natürlichen Zahlen ist. Anschaulich gibt man jedem Knoten eine Farbe.

Statt der Knoten kann man in ohne Mehrfachkanten und in Hypergraphen auch die färben und spricht dann von einem kantengefärbten Graph . Dazu erweitert man ebenfalls das Tupel V E ) zu einem Tripel ( V E f ) wobei f aber eine Abbildung von E (statt von V ) in die Menge der natürlichen Zahlen ist. Anschaulich gibt man jeder Kante eine Farbe. In Graphen mit Mehrfachkanten ist zwar prinzipiell auch möglich aber schwieriger zu insbesondere wenn Mehrfachkanten entsprechend ihrer Vielfachheit mehrere Farben zugeordnet werden sollen.

Statt von knoten- bzw. kantengefärbten Graphen man von knoten- bzw. kantengewichteten Graphen falls f statt in die natürlichen Zahlen in reellen Zahlen abbildet. Knoten- bzw. kantengefärbte Graphen sind Spezialfälle von knoten- bzw. kantengewichteten Graphen.

Man bezeichnet f ( v ) bzw. f ( e ) auch als Gewicht des Knotens v bzw. der Kante e . Zur Unterscheidung spricht man auch von Knotengewicht bzw. Kantengewicht .

Man kann auch gleichzeitig oder mehrfach und Kanten färben bzw. wichten. Die genaue wird dann normalerweise beim speziellen Anwendungsfall erläutert.

Man beachte dass die Begriffe "Färbung" "färben" in der Graphentheorie auch eine speziellere besitzen. Exakt spricht man dann zwar von gültiger Färbung lässt das Attribut "gültig" aber meist

Wichtige spezielle Graphen

Es gibt einige spezielle Typen von die vielen Fragestellungen der Graphentheorie immer wieder Einige dieser wichtigen Graphen werden im Folgenden vorgestellt.
  • Ein vollständiger Graph ist ein ungerichteter Graph ohne Mehrfachkanten dem jeder Knoten mit allen anderen Knoten eine Kante verbunden ist.
  • Ein bipartiter Graph ist ein ungerichteter Graph ohne Mehrfachkanten dem die Menge der Knoten aus zwei Teilmengen besteht und es keine Kanten zwischen derselben Teilmenge gibt.
  • Ein k-partiter Graph stellt eine Verallgemeinerung des bipartiten Graphen Graph) dar bei dem die Menge der eine k-Partition bildet also aus k disjunkten besteht. Analog zum bipartiten Graph darf hier Kante nur zwei Knoten aus jeweils unterschiedlichen verbinden.
  • Ein vollständig k-partiter Graph ist ein k-partiter Graph bei dem alle möglichen Kanten zwischen den Knoten der existieren.
  • Ein Hyperwürfel Q n ist ein ungerichteter Graph ohne Mehrfachkanten n Knoten und 2 n Kanten. Die Knoten werden dabei mit 1-Folgen der Länge n (Zahlen in Binär-Darstellung)
  • Ein weiterer wichtiger Graph ist der genannte Petersen Graph.



Bücher zum Thema Typen von Graphen in der Graphentheorie

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

ImpressumLesezeichen setzenSeite versendenSeite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Typen_von_Graphen_in_der_Graphentheorie.html">Typen von Graphen in der Graphentheorie </a>