Ordnungstheorie")?> Manchen Fragestellungen der kombinatorischen Optimierung wie etwa Sequencing - oder Schedulingproblemen liegen Reihefolgebedingungen zu Grunde, die als Halbordnungen modelliert werden können.

Eine Halbordnung <= (bzw. <) ist eine binäre Relation auf einer Menge P, die reflexiv (bzw. irreflexiv), transitiv und antisymmetrisch (bzw. asymmetrisch) ist. Das Paar (P,<) heißt halbgeordnete Menge, kurz poset (engl.: partially ordered set). Beispiele für Posets sind:
  1. Die gewöhnliche "<" Beziehung auf der Menge der natürlichen Zahlen.
  2. Die durch Inklusion auf einem Mengensystem induzierte Relation.
Posets werden graphisch mittels Hasse - Diagrammen oder Komparabilitätsgraphen dargestellt. Hasse-Diagramme sind Graphen, in denen für jedes Element des Posets ein Knoten gezeichnet wird und zwei Knoten genau dann inzident sind, wenn sie unmittelbare Nachbarn im Poset sind. Gilt j > i, zeichnet man konventionell j oberhalb von i. Ein Hasse-Diagramm ist somit implizit orientiert. Ein Komparabilitätsgraph ist ein ungerichteter Graph, der eine Kante zwischen zwei Knoten genau dann enthält, wenn die dazugehörigen Elemente im Poset in Relation zueinanderstehen. Im Komparabilitätsgraph beschränkt man sich also auf die strukturellen Eigenschaften eines Posets.
Einen der ordnungstheoretischen Forschungsschwerpunkte unserer Arbeitsgruppe bilden Komparabilitätsinvarianten, d.h die Beantwortung der Frage: was haben alle Posets, die isomorphe Komparabilitätsgraphen besitzen, gemeinsam? Ein weiteres Ziel liegt in der Beschreibung effizient lösbarer Subklassen von Scheduling Problemen.
Kontakt:")?> Tel.: 0221/470-6030
Fax: 0221/470-5160
contact@zpr.uni-koeln.de