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

Bearbeiten

Fü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).

Kategorie:Graphentheorie