Apakah grafik selalu memiliki pohon spanning minimum yang biner?

Saya memiliki grafik dan saya perlu menemukan pohon spanning minimum untuk grafik yang diberikan. Apa yang harus dilakukan agar output yang diperoleh adalah pohon biner?

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

Saya hanya perlu tahu apakah itu mungkin atau tidak. Saya telah melakukan beberapa penggalian. Saya hanya ingin tahu apakah ada cara untuk menghasilkan spanning tree yang juga biner.

Aditya.M

Jawaban:

Tidak ada yang harus dilakukan: misalnya, mari $S_k$ menunjukkan grafik bintang dengan $k$ Daun-daun. Grafik $S_k$ memiliki pohon spanning unik (yaitu $S_k$ sendiri), dan memiliki simpul dengan derajat tepat $k$ .

Faktanya, masalah umum untuk menemukan pohon rentang minimum yang dibatasi derajat adalah NP-complete.

Juho
sumber