Como dice el título, ¿cuál es la definición correcta de -tree? Hay varios documentos que hablan de k -Los árboles y parcial k -Árboles como definiciones alternativas para gráficos con treewidth acotada, y he visto muchas definiciones aparentemente incorrectas. Por ejemplo, al menos un lugar define k- árboles de la siguiente manera:
Un gráfico se llama -tree si y solo si G es el gráfico completo con k vértices, o G tiene un vértice v con grado k - 1, de modo que G ∖ v es un k -tree. Un k -tree parcial es cualquier subgrafo de un k -tree.
Según esta definición, se puede crear el siguiente gráfico:
- Comience con un borde , un árbol de 2 .
- Para , cree un vértice v i y hágalo adyacente a v i - 1 y v i - 2 .
Hacer esto crearía una tira de cuadrados con diagonales. Del mismo modo, podemos comenzar a crear una banda desde el primer cuadrado en una dirección ortogonal a la tira de arriba. Entonces, tendríamos la primera fila y la primera columna de una cuadrícula n × n . Rellenar la cuadrícula es fácil creando vértices y uniéndolos a los vértices que están arriba y a la izquierda.
El resultado final es un gráfico que contiene una cuadrícula , que, en efecto, se sabe que tiene un ancho de árbol n .
Una definición correcta de árboles tiene que ser la siguiente:
Un gráfico se llama -tree si y solo si G es un gráfico completo con k vértices, o G tiene un vértice v con grado k - 1, de modo que el vecino de v forma una k -clique, y G v es un k -tree.
Luego, no se puede crear el gráfico en forma de cuadrícula descrito anteriormente.
¿Estoy en lo correcto?
fuente
Respuestas:
Básicamente estoy de acuerdo contigo, con solo una pequeña modificación:
En otras palabras,v debe tener un grado k , en lugar de k−1 en su definición.
Personalmente prefiero la definición de abajo hacia arriba, pero esto es solo una cuestión de gustos:
Esta definición es una versión ligeramente modificada de la definición de las notas de clase de Pinar Heggernes .
fuente