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 k
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 k
De acordo com esta definição, pode-se criar o seguinte gráfico:
- Comece com uma aresta , uma 2 .
- Para , criar um vértice v i e torná-lo ao lado de v i - 1 e v i - 2 .
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.
O resultado final é um gráfico que contém uma grade, o que, com efeito, é conhecido por ser de treewidth n .
Uma definição correta de árvores deve ser a seguinte:
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.
Então, o gráfico em forma de grade descrito acima não pode ser criado.
Estou correcto?
fonte
Respostas:
Eu basicamente concordo com você, com apenas uma pequena modificação:
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:
Esta definição é uma versão ligeiramente modificada da definição das notas de aula de Pinar Heggernes .
fonte