PLANARITAS-1 GRAF KOMPLIT DAN GRAF MULTIPARTISI KOMPLIT

Abstract

Misalkan G sebuah graf. Graf G disebut graf planar jika G dapat Digambar pada bidang datar sedemikian hinga tidak ada sisi-sisinya yang saling berpotongan (bersilangan) kecuali mungkin pada titik-titik akhir  sisi-sisi tersebut.

Graf G disebut graf planar-1 jika G dapat digambarkan pada sebuah bidang datar sedemikian hingga setiap sisi G  berpotongan (bersilangan) dengan paling banyak satu sisi yang lain. Setiap graf planar pasti planar-1. Tetapi sebaliknya graf planar-1 belum tentu graf planar. Skripsi ini membahas planaritas-1 dari graf komplit maupun graf multipartisi komplit. Skripsi ini diawali dengan pembuktikan bahwa jika G graf planar-1  dengan n titik dan m sisi maka m ≤ 4n-8. Selanjutnya dibuktikan bahwa graf komplit  bukan graf planar-1 jika dan hanya jika  . Akhirnya ditunjukakan graf t-partisi komplit  dengan  bukan planar-1.