DEKOMPOSISI GRAF PRISMA

Abstract

Dekomposisi graf adalah kumpulan subgraf tak kosong  dari graf  sedemikian  sehingga  adalah subgraf yang dibangun oleh himpunan bagian sisi (  untuk suatu  himpunan bagian dari ) dan  adalah partisi dari . Subgraf  untuk  pada dekomposisi graf  tidak memuat simpul terpencil. Jika  adalah sebuah dekomposisi dari graf , maka  dapat dinotasikan dengan . Jika  merupakan dekomposisi dari graf ðº sehingga  isomorfis dengan graf , maka graf  dikatakan dekomposisi. Pada penelitian ini dikaji dekomposisi pada graf prisma. Graf prisma merupakan graf yang diperoleh dari hasil kali Kartesius antara graf sikel dengan graf lintasan. Berdasarkan penelitian, diperoleh bentuk dekomposisi graf prisma  dengan  antara lain dekomposisi yaitu partisi graf berbentuk subgraf yang terdiri dari 3 graf lengkap  dan dekomposisi yaitu partisi graf berbentuk subgraf yang terdiri dari graf lintasan . Lebih khusus ketika  adalah bilangan genap, maka berlaku dekomposisi yaitu partisi graf berbentuk subgraf yang terdiri dari 2 graf lintasan.

Kata kunci: Partisi, subgraf,graf lengkap, graf lintasan