1987 | OriginalPaper | Buchkapitel
Kohäsion von Graphen
verfasst von : Prof. Dr. phil. Jürg Kohlas
Erschienen in: Zuverlässigkeit und Verfügbarkeit
Verlag: Vieweg+Teubner Verlag
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Das Thema dieses Kapitels ist die konkrete Berechnung der Kohäsion Ce(G) von ungerichteten Graphen G = (V, E). Diese Größe ist gemäß ihrer Definition (2.1.2) das Minimum aller Bogen-Zusammenhänge Ce(vi, vj) aller Knotenpaare vi und vj des Graphen G. Es scheint demnach auf den ersten Blick, als ob |V|(|V| − 1)/2 Bogen-Zusammenhänge zu berechnen sind, um die Kohäsion zu bestimmen. Eine genauere Betrachtung der Situation zeigt aber rasch, daß enge Beziehungen zwischen den Bogen-Zusammenhängen oder eigentlich genauer gesagt, unter den maximalen Flüssen zwischen verschiedenen Knotenpaaren in einem Graphen G bestehen. Diese haben zur Folge, daß es genügt, |V| − 1-Bogen-Zusammenhänge zu berechnen, um die Kohäsion bestimmen zu können.