MATHunesa | Vol 3, No 6, (2017)

PLANARITAS-1 HASIL KALI LEKSIKOGRAFIK GRAF

NOVI DWI PRATIWI, I Ketut Budayasa,

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.,


Full TEXT