Benutzer:Tcs4flt/Zwillingsmodell

Dieser Artikel ist im Entstehen und noch nicht Bestandteil der freien Enzyklopädie Wikipedia.

Solltest du über eine Suchmaschine darauf gestoßen sein, bedenke, dass der Text noch unvollständig sein und Fehler oder ungeprüfte Aussagen enthalten kann. Wenn du Fragen zum Thema hast, nimm Kontakt mit dem Autor Tcs4flt auf.

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

Für eine gegebene relationale Struktur $\Sigma =(R_{1},\dots ,R_{k})$, ist ein Zwillingsmodell ein Tupel $(Y,Z_{R_{1}},\dots ,Z_{R_{k}})$ wobei $Y$ ein Baum mit einer Wurzel ist und jedes $Z_{R_{i}}$ eine binäre Relation darstellt, die folgenden Bedingungen zu Transversalität, Minimalität und Konsistenz erfüllt:

• (Transversalität) falls $(u,v)\in Z_{R_{i}}$, dann sind $u$ und $v$ in der Baumordnung $\preceq _{Y}$ nicht vergleichbar;
• (Minimalität) falls $(u,v)\in Z_{R_{i}}$, dann existiert kein $(u',v')\neq (u,v)$ mit $u'\preceq _{Y}u$, $v'\preceq _{Y}v$ und $(u',v')\in Z_{R_{i}}$;
• (Konsistenz) falls ein Traversal eines Zyklus $\gamma$ in $Y\cup \bigcup _{i}Z_{R_{i}}$ die natürliche Orientatierung der $Y$-Kanten (d.h.: die Orientatierung von $Y$ von der Wurzel wegweisend) respektiert, dann $\gamma$ beinhaltet zwei aufeinanderfolgende Kanten in $\bigcup _{i}Z_{R_{i}}$.

Literatur

• É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