graphentheorie

Die Anfänge der Graphentheorie



Die Graphentheorie ist ein Teilgebiet der Mathematik, die sich mit Graphen und ihren Beziehungen zueinander beschäftigt. Zu der Entwicklung dieses Teilgebietes kam es unteranderem durch das Königsberger Brückenproblem 1736 und das Vierfarbenproblem um 1850. Ein Graph ist dabei eine Menge aus Punkten, die man als Ecken oder Knoten bezeichnet. Diese Knoten können auch durch Linien, sogenannte Kanten bzw. Bögen miteinander verbunden sein. Die Graphentheorie findet Anwendung beispielsweise im Berechnen von Netzwerken, zum Ermitteln von kürzesten Wegen oder in der Chemie bei der Abzählung von Isomeren. So könnte man in einem Netzwerk die Computer mit den Knoten vergleichen und die Überlandkabel zum Verbinden der ganzen Computer mit den Kanten eines Graphen gleichsetzen. In der Chemie würde man dann die einzelnen Moleküle mit den Knoten vergleichen und die zwischen diesen Molekülen herrschende Bindung als Kanten bezeichnen.

Beispiel:

Grob kann man folgende Graphen unterscheiden:

Außerdem benötigt man die Begriffserklärungen folgender Begriffe:

Graphen können auch verschieden eingefärbt werden. Dabei gibt es die Knotenfärbung - diese Färbung der Knoten von G geschieht so, daß keine zwei adjazenten Knoten die gleiche Farbe haben und die Kantenfärbung - diese Färbung der Kanten von G geschieht so, daß keine zwei adjazenten Kanten gleich gefärbt sind. Bei der Knotenfärbung wird die kleinste Anzahl von Farben, die zum Einfärben der Knoten von G nötig ist, als chromatische Zahl X(G) bezeichnet und bei der Kantenfärbung wird die kleinste Anzahl von Farben, die für das Einfärben der Kanten nötig war als chromatischer Index X'(G) bezeichnet. Graphenfärbung verwendet man zum Beispiel bei Mobilfunknetzen oder bei der Stundenplanung.