Pohon Perentang Geometrik Bidang Yang Kompatibel
Abstract
Dua graf geometrik bidang pada himpunan titik π dikatakan kompatibel jika gabungan kedua graf
tersebut juga merupakan sebuah graf geometrik bidang pada π . Diberikan sebuah pohon perentang
geometrik bidang π pada himpunan π. Fokus permasalahan dalam artikel ini adalah mencari sebuah
pohon perentang geometrik bidang π1 pada π sedemikian hingga π1 kompatibel-π dan banyak sisi
π1 dan π yang bersekutu minimum. Minimum banyaknya sisi π dan π1 yang bersekutu dilambangkan
dengan π(π). 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 sebuah
graf 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.
Copyright (c) 2021 Mathunesa : Jurnal Ilmiah Matematika
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
PDF Downloads: 96