Diskrete Mathematik kompakt, 2nd Edition

6 Graphen

In der Graphentheorie untersucht man, salopp gesagt, Gebilde, in denen Punkte, meist Knoten genannt, durch Linien mit oder ohne Pfeilspitzen, meist Kanten genannt, verbunden sind. Viele nicht unmittelbar auf Graphen bezogene Probleme lassen sich graphentheoretisch formulieren:

• Eine Relation R auf einer Menge A – wie in Abb. 6.1 links – entspricht einem (sogenannten gerichteten) Graphen mit den Elementen von A als Punkten und je einem Pfeil von x nach y für jedes Paar $($x, y$)$ ∈ R – wie in Abb. 6.1 rechts:

Abb. 6.1: Mengentheoretische und bildliche Darstellung einer Relation auf einer Menge.

In diesem Sinne ist Relationentheorie ...