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:
- Die gewöhnliche "<" Beziehung auf der Menge der natürlichen
Zahlen.
- 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