Pokok rentang minimum atau pokok rentang berat minimum ialah subset bagi tepi graf tidak berarah bersambung, berwajaran tepi yang menghubungkan semua bucu bersama-sama, tanpa sebarang kitaran dan dengan jumlah berat tepi minimum yang mungkin. Iaitu, pokok rentang yang jumlah pemberat tepinya sekecil mungkin.
Apakah pokok rentang minimum dengan contoh?
Pokok rentang minimum ialah sejenis pokok khas yang meminimumkan panjang (atau “berat”) tepi pokok itu. Contohnya ialah syarikat kabel yang ingin meletakkan talian ke beberapa kejiranan; dengan meminimumkan jumlah kabel yang diletakkan, syarikat kabel akan menjimatkan wang. Sebatang pokok mempunyai satu laluan bercantum mana-mana dua bucu.
Bagaimanakah anda mencari pokok rentang minimum?
Cari jiran tidak berwarna terdekat dengan subgraf merah (iaitu, bucu paling hampir dengan mana-mana bucu merah). Tandakannya dan tepi yang menyambungkan bucu ke subgraf merah berwarna merah. Ulangi Langkah 2 sehingga semua bucu ditanda merah. Subgraf merah ialah pokok rentang minimum.
Apakah yang anda maksudkan dengan pokok rentang dan pokok rentang minimum?
Pokok rentang graf ialah himpunan tepi bersambung yang merangkumi setiap bucu dalam graf, tetapi tidak membentuk kitaran. … Pokok Rentang Minimum ialah pokok yang berat tepi terkumpulnya mempunyai nilai terkecil, namun.
Apakah perbezaan antara pokok rentang dan pokok rentang minimum?
Jika graf ialahberwajaran tepi, kita boleh mentakrifkan berat pokok merentang sebagai jumlah berat semua tepinya. Pokok rentang minimum ialah pokok rentang yang beratnya paling kecil antara semua pokok rentang yang mungkin.
