<![CDATA[Dua graf geometrik bidang pada himpunan titik ???? dikatakan kompatibel jika gabungan kedua graf tersebut juga merupakan sebuah graf geometrik bidang pada ???? . Diberikan sebuah pohon perentanggeometrik bidang ???? pada himpunan ????. Fokus permasalahan dalam artikel ini adalah mencari sebuahpohon perentang geometrik bidang ????1 pada ???? sedemikian hingga ????1 kompatibel-???? dan banyak sisi ????1 dan ???? yang bersekutu minimum. Minimum banyaknya sisi ???? dan ????1 yang bersekutu dilambangkandengan ????(????). Secara umum menentukan nilai ????(????) merupakan masalah menarik tetapi sulit, karena ????(????)tergantung pada dua hal yaitu kelas pohon ???? itu sendiri, dan letak titik-titik ???? pada bidang datar. Jika ???? pohon khusus seperti bintang diperoleh ????(????) = 1. Sebuah triangulasi dari pohon ???? adalah sebuahgraf diperoleh dari ???? dengan menambahkan sebanyak mungkin sisi-sisi baru, namakan sisi-sisi merah, ke ???? sedemikian hingga graf baru tetap geometrik bidang dengan setiap internal muka berbentuk segitiga. Pada umumnya, triangulasi dari ???? tidak tunggal, minimum banyaknya komponen graf − ???? , dilambangkan dengan ????(????). Dibuktikan bahwa untuk pohon geometrik bidang ???? berlaku ????(????) =????(????) − 1. Jika ???? sebuah pohon geometrik bidang merentang semua titik poligon konveks, ditunjukkan????(????) = 2 atau ????(????) = 1. Akhirnya, jika ???? pohon geometrik bidang merentang semua titik poligon sederhana ???? dan paling sedikit satu di interior ???? dan ???? bukan bintang maka ????(????) = 1 atau ????(????) = 0.]]>
Copyrights © 2021
