Qual é a definição correta de

13

Como o título diz, qual é a definição correta de -tree? Existem vários artigos que falam sobre árvores- e árvores- parciais como definições alternativas para gráficos com largura de árvore limitada, e eu já vi muitas definições aparentemente incorretas. Por exemplo, pelo menos um local define árvores da seguinte maneira:k k kkkkk

Um gráfico é chamado de -tree se e somente se é o gráfico completo com vértices ou possui um vértice com grau modo que seja um -tree. Uma árvore parcial é qualquer subgrafo de uma árvore .G k G v k - 1 G v k k kkGkGvk1Gvkkk

De acordo com esta definição, pode-se criar o seguinte gráfico:

  1. Comece com uma aresta , uma 2 .(v1,v2)2
  2. Para , criar um vértice v i e torná-lo ao lado de v i - 1 e v i - 2 .i=1nvivi1vi2

Fazer isso criaria uma faixa de quadrados com diagonais. Da mesma forma, podemos começar a criar uma banda a partir do primeiro quadrado em uma direção ortogonal à faixa acima. Então, teríamos a primeira linha e primeira coluna de um n × n grid. É fácil preencher a grade criando vértices e unindo-os aos vértices acima e à esquerda.nn×n

O resultado final é um gráfico que contém uma grade, o que, com efeito, é conhecido por ser de treewidth n .n×nn


Uma definição correta de árvores deve ser a seguinte:k

Um gráfico é chamado de -tree se e somente se G for um gráfico completo com k vértices ou G tiver um vértice v com grau k - 1, de modo que o vizinho de v forme uma k -clique, e G v seja um k- árvore.kGkGvk-1vkG vk

Então, o gráfico em forma de grade descrito acima não pode ser criado.

Estou correcto?

ethkim
fonte
6
Você poderia questionar sua pergunta por látex - facilita a leitura. Veja meta.cstheory.stackexchange.com/questions/225/… para obter mais detalhes
Suresh Venkat
Com esta definição, não consigo desenhar uma 2_tree, você pode desenhar e enviar para mim?

Respostas:

15

Eu basicamente concordo com você, com apenas uma pequena modificação:

Um gráfico G é uma árvore- k se, e somente se, G for um gráfico completo com k+1 vértices, ou G tiver um vértice v modo que a vizinhança (aberta) de v forme uma k -clique, e G-v seja uma árvore k .

Em outras palavras, v deve ter o grau k , em vez de k-1 em sua definição.

Pessoalmente, prefiro a definição de baixo para cima, mas isso é apenas uma questão de gosto:

  • O gráfico completo dos vértices k+1 é uma árvore k .
  • Um k -trees G com n+1 vértices ( nk+1 ) pode ser construído a partir de um k -trees H com n vértices adicionando um vértice adjacente a exatamente k vértices que formam um k -clique em H .
  • Nenhum outro gráfico é k árvores.

Esta definição é uma versão ligeiramente modificada da definição das notas de aula de Pinar Heggernes .

Serge Gaspers
fonte
Sim, meu erro foi cometido no grau . (E obrigado pela demonstração latexing!)k-1
ethkim
A outra diferença é a exigência de que o bairro seja uma camarilha.
András Salamon
@ Andras: Por "eu basicamente concordo com você", eu realmente quis dizer que concordo que a primeira definição da pergunta está incorreta (pois não requer que o bairro de seja um clique) e que a segunda definição no A pergunta está quase correta, pois "grau k - 1 " deve ser substituído por "grau k ". vk-1k
Serge Gaspers
Ah, isso faz mais sentido - obrigado por esclarecer.
András Salamon
De acordo com sua definição, um gráfico completo em vértices é uma árvore- k , cuja largura da árvore é k - 1 . No entanto, para o melhor de meu conhecimento, um k -tree é o gráfico máxima com a árvore de largura k , o que implica que um k -clique seria uma ( k - 1 ) -treekkk1kkk(k1)
John