Graphentheorie

Betrachteter Gegenstand

In der Graphentheorie ist ein Graph eine Menge von Punkten (man nennt diese dann Knoten oder auch Ecken), die eventuell durch Linien (sog. Kanten bzw. Bögen) miteinander verbunden sind. Die Form der Punkte und Linien spielt in der Graphentheorie keine Rolle.

Man unterscheidet dabei zwischen:

• endlichen Graphen, bei denen die Menge der Knoten und Kanten endlich ist, und unendlichen Graphen, auf die dies nicht zutrifft, sowie
• gerichteten Graphen, bei denen die Kanten gerichtet sein können (dargestellt durch Pfeile statt Linien) und ungerichteten Graphen.

Komplexere Graphentypen sind:

• Multigraphen, bei denen im Gegensatz zu einfachen Graphen Kanten zwischen den Knoten mehrfach vorkommen dürfen sowie auch Schlingen zugelassen sind, d. h. Kanten, die einen Knoten mit sich selbst verbinden und
• Hypergraphen, bei denen im Gegensatz zu einfachen Graphen Kanten mehr als nur zwei Knoten verbinden können.

Je nach Problemstellung können Knoten und Kanten auch mit Farben (formal mit natürlichen Zahlen) oder Gewichten (d. h. rationalen oder reellen Zahlen) versehen werden. Man spricht dann von knoten- bzw. kantengefärbten oder -gewichteten Graphen.

Copyright- und Lizenzinformationen: Diese Seite basiert auf dem Artikel Graphentheorie aus der freien Enzyklοpädιe Wιkιpedιa und steht unter der Lizenz Creative Commons CC-BY-SA 3.0 Unported (Kurzfassung). Liste der Autoren

Anbieterkennzeichnung