Graphentheorie

Ein Teilbereich der mathemati­schen - Topologie, der eine formalisierte Theo­rie der Darstellung von Strukturen durch Netz­werke aus Punkten (sog. Knoten) und Verbin­dungsstrecken (den Kanten) darstellt. Kanten, die in eine bestimmte Richtung weisen, heißen Pfeile, die entsprechenden Graphen sind gerich­tete Graphen im Gegensatz zu den ungerichte­ten Graphen deren Kanten keine Pfeile sind. In jedem Graph stellen die Knoten (bzw. die überhaupt nicht verbundenen Punkte) die Ele­mente der Struktur dar, die Kanten drücken Funktionen oder Beziehungen zwischen den Ele­menten aus. Ungerichtete Graphen stellen z.B. symmetrische Beziehungen dar, gerichtete Gra­phen asymmetrische Beziehungen. Die mathematische Graphentheorie befaßt sich mit endlichen Mengen von Knoten (Punkten) und Kanten zwischen den Knoten, wobei im Mittel­punkt die Verknüpfungsproblematik von Teil­strecken steht. Unterschieden wird dabei ferner zwischen vollständigen Graphen, bei denen jeder Knoten durch Kanten verbunden ist, und unvoll­ständigen Graphen, bei denen nicht alle Knoten durch Kanten verbunden sind. Die Zahl der Kan­ten in einem vollständigen Graph mit n Knoten beträgt:

Ein Graph, in dem von jedem Knoten zu einem anderen Knoten jeweils nur eine einzige Kante führt, wird als Baumgraph bezeichnet. Als Schlei­fe wird derjenige Teil eines gerichteten Graphen bezeichnet, in dem alle Kanten gleichgerichtet sind und kein Element doppelt vorkommt. Methoden der Graphentheorie ermöglichen über­sichtliche Darstellungen komplexer Strukturen und erleichtern damit die Formulierung von Hy­pothesen. Wichtige Anwendungsgebiete sind ne­ben der Kommunikationsforschung, der Orga­nisationssoziologie und der Soziometrie das - Operations Research, die Netzplantechnik und andere betriebliche Planungstechniken.