¿Cuál es la definición correcta de

13

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:kkkk

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.kGkGvk1Gvkkk

Según esta definición, se puede crear el siguiente gráfico:

  1. Comience con un borde , un árbol de 2 .(v1,v2)2
  2. Para , cree un vértice v i y hágalo adyacente a v i - 1 y v i - 2 .i=1nvivi1vi2

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.nn×n

El resultado final es un gráfico que contiene una cuadrícula , que, en efecto, se sabe que tiene un ancho de árbol n .n×nn


Una definición correcta de árboles tiene que ser la siguiente:k

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.kGkGvk1vkG vk

Luego, no se puede crear el gráfico en forma de cuadrícula descrito anteriormente.

¿Estoy en lo correcto?

ethkim
fuente
66
¿Podría hacer una pregunta sobre el látex? Ver meta.cstheory.stackexchange.com/questions/225/… para más detalles
Suresh Venkat
Con esta definición, no puedo dibujar un 2_tree, ¿podría dibujarlo y enviarlo por mí?

Respuestas:

15

Básicamente estoy de acuerdo contigo, con solo una pequeña modificación:

Un gráfico G es un árbol k si y solo si G es un gráfico completo con k+1 vértices, o G tiene un vértice v tal que la vecindad (abierta) de v forma una k -clique, y Gv es unárbolk .

En otras palabras, v debe tener un grado k , en lugar de k1 en su definición.

Personalmente prefiero la definición de abajo hacia arriba, pero esto es solo una cuestión de gustos:

  • El gráfico completo en k+1 vértices es un k -tree.
  • A k -tree G con n+1 vértices ( nk+1 ) puede ser construido a partir de un k -tree H con n vértices mediante la adición de un vértice adyacente a exactamente k vértices que forman una k -clique en H .
  • Ningún otro gráfico es k árboles.

Esta definición es una versión ligeramente modificada de la definición de las notas de clase de Pinar Heggernes .

Serge Gaspers
fuente
Sí, mi mal por el error en grado. (¡Y gracias por la demostración de látex!)k1
ethkim
La otra diferencia es el requisito de que el vecindario sea una camarilla.
András Salamon
@Andras: Por "básicamente estoy de acuerdo contigo", en realidad quería decir que estoy de acuerdo en que la primera definición de la pregunta es incorrecta (ya que no requiere que la vecindad de sea ​​una camarilla), y que la segunda definición en el la pregunta es casi correcta, ya que "grado k - 1 " debe reemplazarse por "grado k ". vk1k
Serge Gaspers
Ah, eso tiene más sentido, gracias por aclarar.
András Salamon
kkk1kkk(k1)