KONSTRUKSI FAMILI GRAF HAMPIR PLANAR DENGAN ANGKA PERPOTONGAN TERTENTU

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 :

Jp Matematika dd 2011

• SIFAT-SIFAT GRAF DALAM ALJABAR LINIER DAN PENGGUNAANNYA DALAM SAGE
• KESTABILAN MODEL MANGSA PEMANGSA DENGAN MANGSA RENTAN DAN TERINFEKSI
• DIMENSI METRIK PENGEMBANGAN GRAF KINCIR POLA K 1 + mK 3
• SOLUSI NUMERIK DARI PERSAMAAN NAVIER-STOKES
• PENGHITUNGAN VEKTOR-KHARAKTERISTIK SECARA ITERATIF MENGGUNAKAN TITIK TETAP BROUWER
• PEMANFAATAN LABORATORIUM VIRTUAL DAN E-REFERENCE DALAM PROSES PEMBELAJARAN DAN PENELITIAN ILMU KIMIA
• ANALISIS PENGARUH VARIASI FRAKSI VOLUME TERHADAP KEKUATAN TARIK BAHAN KOMPOSIT POLIESTER DENGAN FILLER ALAMI SERABUT KELAPA MERAH
• PENGEMBANGAN PERANGKAT PEMBELAJARAN BERBASIS PRAKTIKUM INKUIRI TERBIMBING UNTUK MEWUJUDKAN HASIL BELAJAR BERKARAKTER
• ORIENTASI LIFE SKIL DALAM KURIKULUM TINGKAT SATUAN PENDIDIKAN DENGAN PENDEKATAN SETS (SCIENCE ENVIRONMENT TECHNOLOGY & SOCIETY) PADA JENJANG PENDIDIKAN DASAR & MENENGAH
• MEMBANGUN KECERDASAN FINANSIAL DENGAN MATEMATIKA KEUANGAN
• MODEL PEMBELAJARAN CREATIVE PROBLEM SOLVING DENGAN VIDEO COMPACT DISK UNTUK MENCAPAI KOMPETENSI DASAR DALAM PEMBELAJARAN MATEMATIKA DI MTS
• SISTEM PRIOTEKSI RADIASI : ANALISIS TERHADAP BIDANG RADIOLOGI RUMAH SAKIT
• STRATEGI PENGEMBANGAN SCIENCE GENERIC SKILLS (SGS) CALON GURU FISIKA MELALUI MODEL PEMBELAJARAN GROUP INVESTIGATION PADA MATA KULIAH PRAKTIKUM
• KANDUNGAN BUAH-BUAHAN DALAM ALQUR’AN: BUAH TIN (FICUS CARICA L), ZAITUN (OLEA EUROPEA L), DELIMA (PUNICA GRANATUM L), ANGGUR (VITIS VINIVERA L), DAN KURMA (PHOENIX DACTYLIFERA L) UNTUK KESEHATAN
• MODEL PEMBELAJARAN KONFLIK KOGNITIF UNTUK MENGATASI MISKONSEPSI PADA MAHASISWA TADRIS FISIKA PROGRAM KUALIFIKASI S.1 GURU MADRASAH
• ISOLASI DAN KARAKTERISASI ASAM HUMAT DARI TANAH GAMBUT
• UPAYA MENINGKATKAN AKTIVITAS BELAJAR DAN HASIL BELAJAR FISIKA PADA KOMPETENSI KINEMATIKA GERAK LURUS MELALUI PEMBELAJARAN INTERPRETATIF BERBASIS ICT DI MAN KENDAL
• KEMATANGAN MOLEKULER FRAKSI HIDROKARBON AROMATIK CORE BADAK 1/208 MUARA BADAK, KUTAI KARTANEGARA, KALIMANTAN TIMUR: SUATU TINJAUAN KUALITATIF
• PENGEMBANGAN PERANGKAT PERKULIAHAN FISIKA DASAR 1 DINAMIKA GERAK DENGAN PENDEKATAN DEMOCRATIC APPROACH
• EFEKTIVITAS PEMANFAATAN PUPUK BOKASI, CASTING DAN PUPUK GENDONING (LARVA KUMBANG KELAPA/ORCYCTES RHINOCEROS)
• ANALISIS BAHAN PENGAWET BENZOAT PADA SAOS TOMAT YANG BEREDAR DI WILAYAH KOTA SURABAYA
• KAJIAN TEOREMA TITIK TETAP PEMETAAN KONTRAKTIF PADA RUANG METRIK CONE LENGKAP DENGAN JARAK-W
• ANALISIS CRITICAL ROOT VALUE PADA DATA NONSTASIONER
• FILTER HALAMAN WEB PORNOGRAFI MENGGUNAKAN KECOCOKAN KATA DAN DETEKSI WARNA KULIT
• PENJADWALAN JALUR BUS DALAM KOTA DENGAN MODEL PETRINET DAN ALJABAR MAX-PLUS (STUDI KASUS BUSWAY TRANSJAKARTA)