Un graphe a-t-il toujours un arbre couvrant minimum binaire?

J'ai un graphique et j'ai besoin de trouver un arbre couvrant minimum pour un graphique donné. Que faire pour que la sortie obtenue soit un arbre binaire?

graph-theory binary-trees spanning-trees minimum-spanning-tree Aditya.M
la source

J'ai juste besoin de savoir si c'est possible ou non. J'ai cependant creusé un peu. Je veux juste savoir s'il existe un moyen de générer un arbre couvrant qui est également binaire.

Aditya.M

Réponses:

Il n'y a rien à faire: par exemple, $S_k$ dénoter le graphique en étoile avec $k$ feuilles. Le graphique $S_k$ a un arbre couvrant unique (qui est $S_k$ lui-même), et il a un sommet avec degré exactement $k$ .

En fait, le problème général de la recherche d'un arbre couvrant minimal contraint en degrés est NP-complet.

Juho
la source