Um gráfico sempre tem uma árvore de abrangência mínima que é binária?

Eu tenho um gráfico e preciso encontrar uma árvore de abrangência mínima para um determinado gráfico. O que deve ser feito para que a saída obtida seja uma árvore binária?

graph-theory binary-trees spanning-trees minimum-spanning-tree Aditya.M
fonte

Eu só preciso saber se é possível ou não. Eu fiz algumas escavações embora. Eu só quero saber se existe alguma maneira de gerar uma árvore de abrangência que também é binária.

Aditya.M

Respostas:

Não há nada a ser feito: por exemplo, deixe denotar o gráfico em estrela com folhas. O gráfico tem uma árvore de abrangência exclusiva (que é o próprio ) e possui um vértice com grau exatamente . $S_k$ $k$ $S_k$ $S_k$ $k$

De fato, o problema geral de encontrar uma árvore de abrangência mínima com restrição de grau é NP-completo.

Juho
fonte