PLANARITAS-1 HASIL KALI LEKSIKOGRAFIK GRAF

Abstract

Graf planar-1 pertama kali diperkenalkan pada tahun 1965 oleh Ringel membahas masalah pewarnaan titik danmuka pada graf bidang. Sebuah graf 𝐺 disebut planar-1 jika 𝐺 dapat digambar pada bidang datar sehingga setiap sisiyang terpotong paling banyak dipotong oleh satu sisi lainnya. Hasil kali leksikografik merupakan salah satu operasiyang digunakan dalam graf planar-1. Hasil kali leksikografik dua graf 𝐺 dan 𝐻, dilambangkan dengan 𝐺 ○ 𝐻 adalahsebuah graf yang himpunan titiknya adalah hasil kali kartesian 𝑉(𝐺) × 𝑉(𝐻) dan dua titik (𝑢, 𝑣) dan (𝑥, 𝑦)berhubungan langsung di 𝐺 ○ 𝐻 jika dan hanya jika 𝑢 berhubungan langsung dengan 𝑥 di 𝐺 atau 𝑢 = 𝑥 dan 𝑣berhubungan langsung dengan 𝑦 di 𝐻. Diungkap beberapa kelas graf 𝐺 dan 𝐻 sedemikian hingga 𝐺 ○ 𝐻 planar-1 atau𝐺 ○ 𝐻 bukan planar-1.

Kata Kunci : graf planar-1, hasil kali leksikografik.