Pohon Perentang Geometrik Bidang Yang Kompatibel

  • Agis Sagita Widyaningrum Program Studi Matematika, FMIPA, Universitas Negeri Surabaya
  • I Ketut Budayasa Program Studi Matematika, FMIPA, Universitas Negeri Surabaya

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.

Published
2021-01-26
Section
Articles
Abstract Views: 87
PDF Downloads: 96