Graphentheorie

Die Graphentheorie (seltener auch Grafentheorie) ist ein Teilgebiet der Mathematik, das die Eigenschaften von Graphen und ihre Beziehungen zueinander untersucht.

Dadurch, dass einerseits viele algorithmische Probleme auf Graphen zurückgeführt werden können und andererseits die Lösung graphentheoretischer Probleme oft auf Algorithmen basiert, ist die Graphentheorie auch in der Informatik, insbesondere der Komplexitätstheorie, von großer Bedeutung. Die Untersuchung von Graphen ist auch Inhalt der Netzwerktheorie. Zudem lassen sich zahlreiche Alltagsprobleme mit Hilfe von Graphen modellieren.

Ungerichteter Graph mit sechs Knoten.

Betrachteter Gegenstand

Hauptartikel: Graph (Graphentheorie)

In der Graphentheorie bezeichnet ein Graph eine Menge von Knoten (auch Ecken genannt) zusammen mit einer Menge von Kanten. Eine Kante ist hierbei eine Menge von genau zwei Knoten. Ist die Menge der Knoten endlich, spricht man von endlichen Graphen, ansonsten von unendlichen Graphen. Wenn die Kanten statt durch Mengen durch Paare von Knoten angegeben sind, spricht man von gerichteten Graphen. In diesem Falle unterscheidet man zwischen der Kante (a,b) – als Kante von Knoten a zu Knoten b – und der Kante (b,a) – als Kante von Knoten b zu Knoten a.

Komplexere Graphentypen sind:

  • Multigraphen, bei denen die Kantenmenge eine Multimenge ist;
  • Hypergraphen, bei denen eine Kante eine beliebig große Menge von Knoten darstellt (man spricht in diesem Falle auch von Hyperkanten);
  • Petri-Netze mit zwei Arten von Knoten.

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

In anderen Sprachen
አማርኛ: ሥነ ግራፍ
беларуская: Тэорыя графаў
čeština: Teorie grafů
dansk: Grafteori
Ελληνικά: Θεωρία γράφων
English: Graph theory
Esperanto: Grafeteorio
euskara: Grafo teoria
Bahasa Indonesia: Teori graf
íslenska: Netafræði
日本語: グラフ理論
한국어: 그래프 이론
lietuvių: Grafų teorija
latviešu: Grafu teorija
монгол: Графын онол
Bahasa Melayu: Teori graf
Nederlands: Grafentheorie
norsk nynorsk: Grafteori
norsk: Grafteori
português: Teoria dos grafos
sicilianu: Tiuria dî grafi
srpskohrvatski / српскохрватски: Teorija grafova
Simple English: Graph theory
slovenčina: Teória grafov
slovenščina: Teorija grafov
српски / srpski: Теорија графова
svenska: Grafteori
Türkçe: Çizge teorisi
українська: Теорія графів
Tiếng Việt: Lý thuyết đồ thị
中文: 图论
粵語: 圖論