Was ist die korrekte Definition von

13

Wie der Titel sagt, was ist die korrekte Definition von Baum? Es gibt mehrere Artikel, die sich mit k- Bäumen und partiellen k- Bäumen als alternative Definitionen für Diagramme mit begrenzter Baumbreite befassen, und ich habe viele scheinbar inkorrekte Definitionen gesehen. Zum Beispiel definiert mindestens eine Stelle k- Bäume wie folgt:kkkk

Ein Graph wird nur dann als Baum bezeichnet, wenn entweder G der vollständige Graph mit k Eckpunkten ist oder G einen Eckpunkt v mit dem Grad k - 1 hat, so dass G v ein k- Baum ist. Ein partieller k- Baum ist ein beliebiger Untergraph eines k- Baums.kGkGvk1Gvkkk

Nach dieser Definition kann man folgendes Diagramm erstellen:

  1. Beginnen Sie mit einer Kante , einem 2- Baum.(v1,v2)2
  2. Erstellen Sie für einen Scheitelpunkt v i und fügen Sie ihn neben v i - 1 und v i - 2 ein .i=1nvivi1vi2

Dies würde einen Streifen von Quadraten mit Diagonalen erzeugen . In ähnlicher Weise können wir vom ersten Quadrat aus in einer Richtung senkrecht zum darüber liegenden Streifen ein Band erstellen. Dann hätten wir die erste Zeile und erste Spalte eines n × n- Gitters. Das Ausfüllen des Gitters ist einfach, indem Sie Scheitelpunkte erstellen und mit den Scheitelpunkten oben und links verbinden.nn×n

Das Endergebnis ist ein Graph, der ein Gitter enthält, von dem bekannt ist, dass es die Baumbreite n hat .n×nn


Eine korrekte Definition von Bäumen muss wie folgt lauten:k

Ein Graph ist ein sogenannter -Baum , wenn und nur wenn entweder G ist ein vollständiger Graph mit k Ecken oder G einen Scheitelpunkt hat v mit dem Grad k - 1 , so dass der Nachbar von v bildet eine k -clique, und G v ein k- Baum.kGkGvk1vkG vk

In diesem Fall kann das oben beschriebene gitterartige Diagramm nicht erstellt werden.

Hab ich recht?

Ethkim
quelle
6
Könnten Sie Ihre Frage latex-ify - macht es einfacher zu lesen. Siehe meta.cstheory.stackexchange.com/questions/225/… für weitere Details
Suresh Venkat
Mit dieser Definition kann ich keinen 2_-Baum zeichnen. Bitte zeichnen und für mich senden.

Antworten:

15

Grundsätzlich stimme ich Ihnen zu, mit nur einer kleinen Änderung:

Ein Graph G ist genau dann ein k Baum, wenn entweder G ein vollständiger Graph mit k+1 Eckpunkten ist oder G einen Eckpunkt v so dass die (offene) Nachbarschaft von v eine k Klasse bildet, und Gv ist ein k Baum.

Mit anderen Worten, v sollte den Grad k , stattdessen k1 in Ihrer Definition.

Ich persönlich bevorzuge die Bottom-up-Definition, aber das ist nur Geschmackssache:

  • Der vollständige Graph auf k+1 Eckpunkten ist ein k Baum.
  • Ein k Baum G mit n+1 Eckpunkten ( nk+1 ) kann aus einem k Baum H mit n Eckpunkten konstruiert werden, indem ein Eckpunkt benachbart zu genau k Eckpunkten hinzugefügt wird , die eine k Klasse in H .
  • Keine anderen Graphen sind k Bäume.

Diese Definition ist eine leicht abgewandelte Version der Definition aus den Vorlesungsunterlagen von Pinar Heggernes .

Serge Gaspers
quelle
Ja, mein schlechtes für den Fehler in Grad. (Und danke für die Latex-Demonstration!)k1
Ethkim
Der andere Unterschied ist das Erfordernis, dass die Nachbarschaft eine Clique ist.
András Salamon
@Andras: Mit "Ich stimme Ihnen im Grunde zu" meine ich eigentlich, dass ich zustimme, dass die erste Definition in der Frage falsch ist (da es nicht erforderlich ist, dass die Nachbarschaft von eine Clique ist), und dass die zweite Definition in der Frage ist fast richtig, da "Grad k - 1 " durch "Grad k " ersetzt werden sollte. vk1k
Serge Gaspers
Ah, das macht mehr Sinn - danke für die Klarstellung.
András Salamon
Nach Ihrer Definition ist ein vollständiger Graph auf Ecken ein k- Baum, dessen Baumbreite k - 1 ist . Nach meinem besten Wissen ist ein k- Baum der maximale Graph mit der Baumbreite k , was impliziert, dass eine k- Klasse ein ( k - 1 ) -Baum wärekkk1kkk(k1)
John