Stichpunkte

Allgemein
	zwischen denen Linien verlaufen
	Anschaulich besteht ein Graph in der Graphentheorie aus einer Menge von Punkten
	Die Punkte nennt man Knoten oder Ecken
	manchmal auch Bögen
	die Linien nennt man meist Kanten
	Auf die Form der Knoten und Kanten kommt es im allgemeinen dabei nicht an
	Knoten und Kanten können auch mit Namen versehen sein
	dann spricht man von einem benannten Graphen
	In so genannten Multigraphen können zwei Knoten auch durch mehrere Kanten verbunden sein
	was in einfachen Graphen nicht erlaubt ist
	kennzeichnet man Mehrfachkanten auch häufig durch ihre Vielfachheit
	Statt mehrere Linien zwischen zwei Punkten zu zeichnen
	In gerichteten Graphen werden Kanten statt durch Linien durch Pfeile gekennzeichnet
	wobei der Pfeil vom ersten zum zweiten Knoten zeigt
	sondern mehrere Knoten gleichzeitig
	Bei Hypergraphen verbindet eine Kante (auch Hyperkante genannt) nicht nur zwei
	Sie sind meist nur schwer darstellbar
	die den Knoten entsprechen
	Bei dünnen Graphen (der Graph enthält nur wenig Kanten) zeichnet man eine Menge von Punkten
	die somit die Teilmenge der zu ihr gehörenden Knoten innerhalb aller Knoten angibt
	Die zu einer Hyperkante gehörigen Punkte werden dann durch eine geschlossene Linie umkreist
	Bei Hypergraphen mit vielen Kanten wird diese Darstellung aber schnell unübersichtlich
	wobei die eine der beiden Bipartitionsmengen den Knoten des Hypergraphen
	die andere Bipartitionsmenge den Hyperkanten des Hypergraphen entspricht
	aber übersichtlicher ist es dann
	einen Hypergraphen als bipartiten Meta-Graphen darzustellen
	Weniger intuitiv
	Die Kanten zwischen diesen beiden Bipartitionsmengen symbolisieren dann die Zugehörigkeit der Knoten zu den Hyperkanten. Inhaltsverzeichnis showTocToggle("Anzeigen"
	"Verbergen") 1 Definitionen 2 Bemerkungen 3 Erweiterungen 4 Wichtige spezielle Graphen [Bearbeiten]
Definitionen
	gerichteten Graphen mit Mehrfachkanten eine Multimenge über dem kartesischen Produkt V x V
	oft auch Ecken genannt) und E eine (höhere) Menge von Kanten (englisch edge
	E)
	Ein Graph G ist ein Tupel (V
	manchmal auch Bögen genannt) bezeichnet. Dabei ist E in ungerichteten Graphen ohne Mehrfachkanten eine Teilmenge aller 2-elementigen Teilmengen von V
	wobei V eine Menge von Knoten (englisch vertex
	Hypergraphen eine Teilmenge der Potenzmenge von V. 1. ungerichteter Graph ohne Mehrfachkanten 2. gerichteter Graph ohne Mehrfachkanten 3. ungerichteter Graph mit Mehrfachkanten 4. gerichteter Graph mit Mehrfachkanten Den Zusatz "ohne Mehrfachkanten" lässt man gewöhnlich weg und nennt Graphen mit Mehrfachkanten Multigraphen
	ungerichteten Graphen mit Mehrfachkanten eine Multimenge über der Menge aller 2-elementigen Teilmengen von V
	gerichteten Graphen ohne Mehrfachkanten eine Teilmenge des kartesischen Produktes V x V
	Ferner verzichtet man meist auf das Attribut "ungerichtet" und kennzeichnet nur gerichtete Graphen explizit
	Ungerichtete Graphen ohne Mehrfachkanten nennt man auch häufig schlicht oder einfach
	Eine andere Bezeichnung für gerichtete Graphen ist Digraph
	definiert man gewöhnlich zwei Abbildungen V und E
	E) seine Knoten- bzw
	die einem Graphen G=(V
	Um kürzer schreiben zu können
	d.h
	Kantenmenge zuordnen
	V(G) := V und E(G) := E
	Man beachte
	dass trotz der selben Symbole (V bzw
	E) die Knoten- bzw
	Kantenmenge etwas anderes als die gerade definierten Abbildungen darstellen
	bedeuten V bzw
	Wenn es nicht anders gesagt wird
	E ohne Argument gewöhnlich die Knoten- bzw
	Kantenmenge des gerade betrachteten Graphen
	V bzw
	E mit Argument bedeuten hingegen immer die gerade definierten Abbildungen
	deren Ergebnis dann natürlich wieder eine Knoten- bzw
	und zwar die des als Argument angegebenen Graphen
	Kantenmenge ist
	so sagt man allgemein v ist Knoten (bzw
	Ist G ein Graph
	wenn v zu V(G) gehört
	Ecke) von G
	gerichteter Graph mit Mehrfachkanten ist und E(G)(e) > 0
	w} bezeichnet man v und w als Endknoten von e
	e ist eine ungerichtete Kante von G
	e ist eine gerichtete Kante von G
	e ist eine gerichtete Kante von G
	falls G ungerichteter Graph ohne Mehrfachkanten ist und e zu E(G) gehört
	gerichteter Graph ohne Mehrfachkanten ist und e zu E(G) gehört
	ungerichteter Graph mit Mehrfachkanten ist und E(G)(e) > 0
	e ist eine ungerichtete Kante von G
	e ist eine Hyperkante von G. In einer ungerichteten Kante e={v
	Ferner sagt man
	Hypergraph ist und e zu E(G) gehört
	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 von 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
	so spricht man von einer Mehrfachschleife
	Ist e in einem Multigraphen G zusätzlich eine Mehrfachkante
	w) auch (w
	w) als auch (w
	dass sie neben (v
	ungerichtete Kante von G. 1-elementige ungerichtete Kanten in gerichteten Graphen sind offensichtlich also immer Schleifen
	Eine 1- oder 2-elementige Menge von geordneten Paaren mit der Eigenschaft
	v) Kante von G sind
	w)) = E(G)((w
	gerichteter Graph mit Mehrfachkanten ist und E(G)((v
	v))
	falls G gerichteter Graph ohne Mehrfachkanten ist und sowohl (v
	ungerichtete Kante von G
	v) enthält (im 1-elementigen Fall ist dies natürlich nur bei v=w möglich) nennt man
	Umgekehrt lässt sich zu jeder Schleife e leicht eine ungerichtete Kante konstruieren (nämlich {e})
	weshalb man gewöhnlich das Attribut "gerichtet" weg lässt
	Schleifen sind in diesem Sinne also immer ungerichtet
	Ist jede Kante eines gerichteten Graphen G Element einer ungerichteten Kante von G
	so nennt man G auch symmetrisch
	falls man keine ungerichteten Kanten betrachtet. In Hypergraphen sagt man statt Hyperkante auch oft einfach nur Kante
	Man lässt gewöhnlich in ungerichteten Graphen das Attribut "ungerichtet" für Kanten weg. In gerichteten Graphen lässt man das Attribut "gerichtet" für Kanten gewöhnlich nur dann weg
	Gerichtete Graphen ohne Schleifen nennt man schleifenlos oder schleifenfrei
	Als Knotenzahl n(G)=|V(G)| eines Graphen G bezeichnet man die Anzahl seiner Knoten
	als Kantenzahl m(G)=|E(G)| bezeichnet man die Anzahl seiner Kanten (in Multigraphen summiert man über die Vielfachheit der Kanten)
	Einen Graph
	nennt man endlicher Graph
	dessen Knotenmenge endlich ist
	dessen Knotenmenge unendlich ist
	Zwangsläufig ist in diesen auch die Kantenmenge endlich. Im Gegensatz dazu nennt man einen Graph
	unendlicher Graph. Meist betrachtet man nur endliche Graphen und lässt daher das Attribut "endlich" weg
	während man "unendliche Graphen" explizit kennzeichnet. [Bearbeiten]
Bemerkungen
	sind zwar nicht formal
	da es offensichtlich auch hier eine einfache eineindeutige Zuordnung zwischen beiden Varianten gibt (siehe auch Repräsentation von Graphen im Computer)
	die in gewissem Sinn Spezialfälle von gerichteten Graphen sind. Ist ein gerichteter Graph symmetrisch und schleifenlos
	weshalb man auch diese als Graphen ohne Mehrfachkanten bezeichnet. Es gibt offensichtlich eine einfache bijektive Zuordnung zwischen den beiden Varianten. In diesem Sinne sind Graphen ohne Mehrfachkanten also Spezialfälle von Graphen mit Mehrfachkanten. Ähnlich verhält es sich mit ungerichteten Graphen
	so bezeichnet man diesen auch als ungerichtet
	Ungerichtete Graphen ohne Mehrfachkanten sind offensichtlich Spezialfälle von Hypergraphen. Multigraphen in denen keine Mehrfachkanten vorkommen
	aber anschaulich äquivalent zu Graphen ohne Mehrfachkanten
	Es lassen sich natürlich auch ungerichtete Graphen mit Schleifen definieren
	wobei man diese wohl am einfachsten wie eben als (formale) Spezialfälle von gerichteten Graphen definiert und die Bedingung der Schleifenlosigkeit weg lässt. Solche Graphen sind aber nur selten Gegenstand der Betrachtungen in der Graphentheorie
	Der wohl allgemeinste Typ von Graphen sind gerichtete Hypergraphen mit Mehrfachkanten. Jeder oben definierte Graphentyp kann dann als Spezialfall von diesem betrachtet werden
	Solche Graphen sind aber so gut wie gar nicht Gegenstand der Betrachtungen in der Graphentheorie
	weshalb sie hier auch nicht näher erläutert werden
	die für das Graphzeichnen benötigt werden
	werden Algorithmen benötigt
	Sollen Graphen als Darstellung eines Sachverhaltes herhalten
	Diese Disziplin der Informatik hat sich in den letzten Jahren stets fortentwickelt und liefert Lösungen für unterschiedliche Visualisierungen
	die auf Graphen beruhen. [Bearbeiten]
Erweiterungen
	E) zu einem Tripel (V
	wobei f eine Abbildung von V in die Menge der natürlichen Zahlen ist. Anschaulich gibt man jedem Knoten damit eine Farbe
	Oft erweitert man Graphen G=(V
	f) ergänzt
	indem man das Tupel (V
	E) zu knotengefärbten Graphen
	E
	Statt der Knoten kann man in Graphen ohne Mehrfachkanten und in Hypergraphen auch die Kanten färben und spricht dann von einem kantengefärbten Graph
	f)
	wobei f aber eine Abbildung von E (statt von V) in die Menge der natürlichen Zahlen ist. Anschaulich gibt man jeder Kante damit eine Farbe
	E
	Dazu erweitert man ebenfalls das Tupel (V
	E) zu einem Tripel (V
	insbesondere
	In Graphen mit Mehrfachkanten ist dies zwar prinzipiell auch möglich
	wenn Mehrfachkanten entsprechend ihrer Vielfachheit mehrere verschiedene Farben zugeordnet werden sollen
	aber schwieriger zu definieren
	Statt von knoten- bzw. kantengefärbten Graphen spricht man von knoten- bzw. kantengewichteten Graphen
	falls f statt in die natürlichen Zahlen in die reellen Zahlen abbildet
	Knoten- bzw. kantengefärbte Graphen sind also 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
	f
	g)
	Analog gibt es auch benannte Graphen (V
	und die Abbildungen f bzw. g den Knoten bzw
	bei denen Knoten und/oder Kanten einen Namen tragen
	E
	Kanten einen Namen zuorden
	Die zuvor abgebildeten Beispiele sind benannte Graphen
	bei denen die Knoten mit Buchstaben benannt wurden
	so dass man besser über den Graphen diskutieren kann
	Dies wird oft bei Visualisierungen gemacht
	Man kann auch gleichzeitig oder mehrfach Knoten und Kanten färben
	wichten oder benennen
	Die genaue Definition wird dann normalerweise beim speziellen Anwendungsfall erläutert
	lässt das Attribut "gültig" aber meist weg. [Bearbeiten]
	Man beachte
	dass die Begriffe "Färbung" und "färben" in der Graphentheorie auch eine speziellere Bedeutung besitzen. Exakt spricht man dann zwar von gültiger Färbung
Wichtige spezielle Graphen
	Es gibt einige spezielle Typen von Graphen
	die bei vielen Fragestellungen der Graphentheorie immer wieder auftauchen
	bei dem die Menge der Knoten aus zwei disjunkten Teilmengen besteht und es keine Kanten zwischen Knoten derselben Teilmenge gibt. Ein k-partiter Graph stellt eine Verallgemeinerung des bipartiten Graphen (2-partiter Graph) dar
	bei dem die Menge der Knoten eine k-Partition bildet
	in dem jeder Knoten mit jedem anderen Knoten durch eine Kante verbunden ist. Ein bipartiter Graph ist ein ungerichteter Graph ohne Mehrfachkanten
	Einige dieser wichtigen Graphen werden im Folgenden kurz vorgestellt. Ein vollständiger Graph ist ein ungerichteter Graph ohne Mehrfachkanten
	also aus k disjunkten Teilmengen besteht
	Analog zum bipartiten Graph liegen die Knoten jeder Kante in verschiedenen Teilmengen. Ein vollständig k-partiter Graph ist ein k-partiter Graph
	bei dem alle möglichen Kanten zwischen den Knoten der Teilmengen existieren. Ein Hyperwürfel Qn ist ein ungerichteter Graph ohne Mehrfachkanten mit n Knoten und 2n Kanten
	azyklischer Graph ohne Mehrfachkanten
	Die Knoten werden dabei mit 0
	ungerichteter
	1-Folgen der Länge n (Zahlen in Binär-Darstellung) beschriftet. Ein Baum ist ein zusammenhängender
	dass sich keine Kanten überkreuzen. Ein weiterer wichtiger Graph ist der so genannte Petersen-Graph. Ein gerichteter Graph mit genau einer Kante zwischen zwei Knoten heißt Turniergraph. Siehe auch: Zufallsgraph
	der so in einer Ebene eingebettet werden kann
	Small world-Netzwerk
	Ein in disjunkte Bäume zerlegbarer Graph heißt Wald. (siehe auch Wälder und Bäume in der Graphentheorie) Ein Netzwerk ist ein gerichteter Graph ohne Mehrfachkanten mit Senke und Quelle als ausgezeichnete Knoten und einer Kapazitätsfunktion. (siehe auch Flüsse und Schnitte in Netzwerken) Ein planarer Graph ist ein Graph
	Skalenfreies Netzwerk en:Graph (mathematics) hu:Gráf (halmazelmélet)

[X] Schliessen

Dieser Artikel basiert auf dem Artikel Typen von Graphen in der Graphentheorie aus der freien Enzyklopädie wikipedia und steht unter der GNU Lizenz für freie Dokumentation. In der wikipedia ist eine Liste der Autoren verfügbar.