Apakah ada algoritma waktu polinomial untuk menemukan — jika ada — laba-laba spanning dari suatu graf ? Laba-laba adalah pohon dengan paling banyak satu simpul dengan derajat lebih besar dari 2:
Saya tahu bahwa berbagai kondisi derajat pada G (pada dasarnya, derajat simpul cukup besar) menjamin keberadaan laba-laba yang merentang. Tapi saya bertanya-tanya apakah ada algoritma untuk G sewenang-wenang . Terima kasih!
ds.algorithms
reference-request
graph-theory
graph-algorithms
Joseph O'Rourke
sumber
sumber
Jawaban:
Pertanyaan telah dijawab dalam komentar oleh Tsuyoshi & Chandra! Saya menambahkan jawaban CW ini sehingga saya dapat menerimanya untuk menunjukkan bahwa pertanyaan sudah ditutup. Terimakasih semuanya!
sumber