ABSTRAK: Sebuah graf
adalah pasangan himpunan
tak kosong simpul
dan himpunan sisi.
Graf dapat digambar pada
bidang dengan atau
tanpa perpotongan. Angka
perpotongan adalah jumlah perpotongan terkecil
di antara semua
gambar graf pada
bidang. Graf dengan
angka perpotongan nol disebut
planar. Graf memiliki penerapan penting pada desain Very Large Scale of
Integration (VLSI). Sebuah graf
dinamakan perpotongan kritis
jika penghapusan sebuah
sisi manapun menurunkan angka
perpotongannya, sedangkan sebuah
graf dinamakan hampir
planar jika menghapus salah
satu sisinya membuat
graf yang sisa
menjadi planar. Banyak
famili graf perpotongan kritis
yang dapat dibentuk
dari bagian-bagian kecil
yang disebut ubin
yang diperkenalkan oleh Pinontoan
dan Richter (2003).
Pada tahun 2010,
Bokal memperkenalkan operasi perkalian
zip untuk graf.
Dalam artikel ini ditunjukkan
sebuah konstruksi dengan menggunakan ubin dan perkalian zip
yang jika diberikan bilangan bulat k 1,
dapat menghasilkan famili tak hingga graf hampir planar dengan angka
perpotongan k.
Kata kunci:
angka perpotongan, ubin graf, graf hampir planar
Penulis: Benny
Pinontoan
Kode Jurnal: jpmatematikadd110001
Artikel Terkait :
