Das Konzept des Zwillingsmodells wurde 2021 von von Édouard Bonnet, Jaroslav Nešetřil, Patrice Ossona de Mendez, Sebastian Siebertz, und Stéphan Thomassé eingeführt. Es ist eine Charakterisierung, d.h. eine alternative Definition, des Graphparameters Twin Width.
Das Zwillingsmodell einer relationale Struktur ist ein Baum mit traversalen Kanten, die die drei Bedingungen Transversalität, Minimalität und Konsistenz erfüllt. Für jedes Paar in einem Tupel der relationalen Struktur gibt es eine traversale Kante im Zwillingsmodell. Per Transversalität wird sichergestellt, dass ein solches Paar nur zwischen Baumknoten vorkommt, die nur erreicht werden, können indem im Baum auch nach oben gegangen werde darf. Diese Knoten sind in der Baumordnung dann also unvergleichbar. Die Minimalitätsbedingung fordert, dass eine traversale Kante so weit unten wie möglich im Baum hängt. Die Konsistenz gibt an, wie sich Zyklen im Baum mit der Richtung der Baumkanten vertragen.
Formale Definition
BearbeitenFür eine gegebene relationale Struktur , ist ein Zwillingsmodell ein Tupel wobei ein Baum mit einer Wurzel ist und jedes eine binäre Relation darstellt, die folgenden Bedingungen zu Transversalität, Minimalität und Konsistenz erfüllt:
- (Transversalität) falls , dann sind und in der Baumordnung nicht vergleichbar;
- (Minimalität) falls , dann existiert kein mit , und ;
- (Konsistenz) falls ein Traversal eines Zyklus in die natürliche Orientatierung der -Kanten (d.h.: die Orientatierung von von der Wurzel wegweisend) respektiert, dann beinhaltet zwei aufeinanderfolgende Kanten in .
Literatur
Bearbeiten- Édouard Bonnet, Jaroslav Nešetřil, Patrice Nešetřil, Sebastian Siebertz, Stéphan Thomassé: Twin-width and permutations. arXiv. 2021, arxiv:2102.06880 (englisch).