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.
Copyrights © 2017