Die Dozenten der Informatik-Institute der Technischen Universität Braunschweig laden im Rahmen des Informatik-Kolloquiums zu folgendem Vortrag ein:

Prof. Dr. Günther Stiege, Universität Oldenburg: Höherer Zusammenhang in allgemeinen Graphen

Beginn: 14.12.2009, 17:00 Uhr Ort: TU Braunschweig, Informatikzentrum, Mühlenpfordtstraße 23, Galeriegeschoss, Raum G04 Webseite: http://www.ibr.cs.tu-bs.de/cal/kolloq/2009-12-14-stiege.html Kontakt: Prof. Dr.-Ing. F. M. Wahl

Allgemeine Graphen enthalten ungerichtete Kanten und gerichtete Bögen in beliebiger Mischung. Sie eignen sich gut für eine einheitliche Darstellung der Graphentheorie. In a-Wegen in gemeinen Graphen dürfen Bögen in beliebiger Richtung durchlaufen werden. Bei f-Graphen ist der Durchlauf nur vom Anfangsknoten zum Endknoten gestattet. k-facher Zusammenhang wird definiert durch gegenseitige Erreichbarkeit auf mindestens k unabhängigen Wegen. Maximale k-zusammenhängende Untergraphen heißen k-Komponenten, wenn die Wege keine gemeinsamen inneren Knoten haben, und k-Linienkomponenten, wenn sie keine gemeinsamen Kanten/Bögen haben.

Gesucht ist die Zerlegung eines allgemeinen Graphen in k-Komponenten und k-Linienkomponenten für k=1,2,... sowohl für a-Wege als auch für f-Wege. Für k>3 ist der Satz von Menger die Basis der Zerlegungsalgorithmen. k-Linienkomponenten lassen sich in polynomieller Zeit finden. Bei k-Komponenten ist offen, ob sie in polynomieller Zeit gefunden werden können.