¿Se permiten o no los nodos repetidos en la descomposición en árbol de un grafo?

Question

Como sabemos, un descomposición del árbol de un gráfico debe tener las siguientes características:

1. Todos los vértices están cubiertos
2. Todos los bordes están cubiertos
3. La condición de conectividad

Creo que el uso de nodos repetidos en descomposición del árbol debe permitirse por definición. ¿Es cierto?

Answer 1

La definición básica de la descomposición del árbol lo permite. Si tratamos de minimizar el diámetro del grafo o el recuento de nodos, obviamente son redundantes, y para los cálculos algorítmicos se pueden eliminar.

De la definición de Wikipedia en su enlace es la definición de suave :

Una descomposición en árbol $(X, T = (I, F))$ de la anchura del árbol $k$ es suave, si:

• $\forall i \in I : |X_i| = k + 1$ ,
• $\forall (i, j) \in F : |X_i \cap X_j| = k$

Esto impide que se repitan los nodos, ya que $|X_i \cap X_j| = k+1$ si $X_i=X_j$ .