Äquivalenz zwischen zwei Definitionen der Baumbreite

Baumbreite :

1) Durch Triangulierter Graph : Größe der größten Clique - 1 in einer chordal Beendigung des Graphen .$(\omega (G))$$G$

2) Durch Baumzerlegung :

Eine Baumzerlegung von besteht aus einem Baum (auf einem anderen ) und einer Teilmenge die jedem Knoten von . (Wir werden diese Teilmengen die "Teile" der nennen .) Wir werden dies manchmal als geordnetes Paar schreiben . Der Baum T und die Sammlung von Stücken müssen die folgenden drei Eigenschaften erfüllen$G = (V , E)$$T$$G$$V_t ⊆ V$$t$$T$$V_t$$(T , {V_t : t ∈ T })$$\{V_t : t ∈ T \}$

( Knotenabdeckung ) Jeder Knoten von gehört zu mindestens einem Stück .$G$$V_t$

(Kantenabdeckung) Für jede Kante von gibt es ein Stück das beide Enden von .$e$$G$$V_t$$e$

(Kohärenz) Sei und drei Knoten von so dass auf dem Weg von nach . Wenn dann ein Knoten von sowohl zu als auch zu gehört, gehört er auch zu$t_1, t_2,$$t_3$$T$$t_2$$t_1$$t_3$$v$$G$$V_{t_{1}}$$V_{t_{3}}$$V_{t_2}$

Wir definieren also die Breite einer als eins weniger als die maximale Größe eines Stücks (über alles ): $(T , {V_t })$$V_t$$t$

Anspruch 1: Wenn die Größe der größten Clique in einer Akkordzerlegung des Graphen ist, erhalten wir durch Baumzerlegung die Baumbreite$k$$k$

Beweis: Nehmen wir an, dass die größte Cliquengröße im Akkordvervollständigungsdiagramm , sodass eine Tasche (Teilmenge der Scheitelpunkte des Diagramms) vorhanden ist, die die Clique enthält (aufgrund der Kantenabdeckung). Also sind wir fertig.$k$

Anspruch 2 : Wenn die Baumbreite nach der Baumzerlegungsmethode ist , dann ist nach der Akkordvervollständigungsmethode auch$k$$k$

Frage: Wie kann der Anspruch 2 nachgewiesen werden? Ein hochrangiger Beweis wird begrüßt.

Lassen Sie mich zunächst feststellen, dass die in der Frage angegebene Behauptung falsch ist: Betrachten Sie die folgende Grafik:

$\begin{matrix} & & 2& - & 3\\ & \diagup\\ 1 & & | & & |\\ & \diagdown \\ & &4 &-& 5 \end{matrix}$

Das vollständige Diagramm auf Eckpunkten ist eine akkordische Vervollständigung dieses Diagramms. Dieses Diagramm hat jedoch die Baumbreite . (Eine Zerlegung ist , , )$5$$2$$\{1,2,4\}$$\{2,3,4\}$$\{3,4,5\}$

Der richtige Anspruch ist

Das Baumweite von von der Größe der größten Clique in einem Akkord-Abschluss mit der minimalen größten Clique des Graphen .$G$$\omega(G) - 1$$G$

Ein Beweis ist nun wie folgt: Wenn die Baumbreite von durch Baumzerlegung , dann hat jede Baumzerlegung einen Beutel mit einer Größe von mindestens . Wir verwenden das Konzept eines Separatorgraphen aus einer Arbeit von Parra und Scheffler , insbesondere die Tatsache, dass jede maximale Clique im Separatorgraphen von eine Baumzerlegung von (Dies kann durch Vergleichen der Definition von Baumzerlegungen mit denen gesehen werden in der Zeitung)$G$$k$$k$$G$$G$

Dann hat nach Satz 4.7 aus demselben Papier jede minimale Akkordvervollständigung von alle Beutel einer Baumzersetzung als Clique. Dies bedeutet, dass jede minimale Akkordvervollständigung von eine Clique der Größe , so dass die Akkordvervollständigungsmethode auch eine Baumbreite von ergibt . $^*$$G$$G$$k$$k$$\square$

*: In unserer Notation umschrieben heißt es in Satz 4.7:

Ein Graph ist genau dann eine minimale Akkordvervollständigung von wenn der Graph mit genau den hinzugefügten Kanten ist, so dass alle Scheitelpunktmengen in Cliquen sind. Hier ist eine maximale Clique im Separatorgraphen, die aus minimalen Separatoren von .$H$$G$$H$$G$$\mathcal{S}$$\mathcal{S}$$G$

Ich habe versucht, einen Beweis nur mit elementaren Techniken zu finden, aber ich denke nicht, dass ein einfacher Beweis ohne eine tiefere Theorie leicht zu finden wäre.