\( \newcommand{\data}{\textnormal{data}} \newcommand{\lower}{\textnormal{lower}} \newcommand{\upper}{\textnormal{upper}} \newcommand{\array}{\textnormal{array}} \newcommand{\depth}{\textnormal{depth}} \newcommand{\height}{\textnormal{height}} \newcommand{\BST}{\textnormal{BST}} \newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor} \newcommand{\ceil}[1]{\left\lceil #1 \right\rceil} \newcommand{\lognpone}{\ceil{\log_2(n+1)}} \newcommand{\bitsize}{\textnormal{bitSize}} \newcommand{\mult}{\textnormal{mult}} \newcommand{\inneighbors}{\textnormal{inNeighbors}} \newcommand{\outneighbors}{\textnormal{outNeighbors}} \newcommand{\neighbors}{\textnormal{neighbors}} \newcommand{\indeg}{\textnormal{indeg}} \newcommand{\outdeg}{\textnormal{outdeg}} \newcommand{\scc}{\textnormal{scc}} \newcommand{\R}{\mathbb{R}} \newcommand{\val}{\textnormal{val}} \newcommand{\dist}{\textnormal{dist}} \newcommand{\flows}{\textnormal{flows}} \)

Hier ist ein Graph.
Er besteht aus den fünf Knoten \(a,b,c,d,e\) und hat sechs Kanten. Graphen sind ein sehr allgemeines Konzept, um Objekte und die Beziehung zwischen diesen darzustellen. Straßennetze, Rohrennetze, Schienennetze, Datennetze, Moleküle, Verwandtschaften, Bekanntschafen lassen sich (teilweise) als Graphen darstellen. Ein weiteres Beispiel wäre der "Wer-folgt-wem"-Graph eines sozialen Netzwerks wie X. Hier müssen wir jedoch den Kanten eine Richtung geben, weil die "$A$ folgt $B$ auf X"-Relation nicht symmetrisch ist:
(Fiktiver Twitter-Graph. Kein Bezug zur Realität)

Man nennt dies einen gerichteten Graphen.