Vol. 10, No. 1,  14-25,  Juli  2013
Dekomposisi Graf Hasil Kali Tiga Lintasan ke Dalam Sub Graf Perentang Reguler
Hasmawati 1

## Abstrak
Dekomposisi  graf  G  adalah  himpunan * + dengan merupakan  subgraf  dari G yang  memenuhi ( )   ⋃ ( )   ( )       ( )    ( ) dan ( )    ( ) untuk  setiap .  Jika merupakan  subgraf  perentang  reguler,  maka  himpunan * + disebut  faktorisasi  dari G .  Dalam  tulisan  ini,  disajikan  dekomposisi  dan faktorisasi graf hasil kali tiga lintasan untuk .
Kata Kunci :Dekomposisi, graf, sub graf, faktorisasi.

## 1. Pendahuluan
Graf G(V, E) adalah suatu sistem yang terdiri dari himpunan berhingga tak kosong V = V ( G )dan  himpunan E  =  E ( G )  dengan E  V  2. Himpunan V disebut himpunan  titik dari G dan himpunan E disebut himpunan sisi dari G . Setiap atau di V ( G ) disebut titik dan setiap = di E ( G )  disebut sisi .  Selanjutnya,  sisi ditulis .  Titik disebut  tetangga (neighbor)  dari  titik jika .  Lebih  lanjut,  titik dan dikatakan titik-titik bertetangga ( adjacent ),  sedangkan  sisi dikatakan  terkait  (incident)  dengan  titik dan .  Dua sisi 1 dan 2 pada G disebut sisi-sisi bertetangga jika 1 dan 2 terkait pada satu titik yang sama. Dua graf G dan H disebut isomorf jika terdapat pemetaaan satu-satu dan pada  : V (G)  V (H) sedemikian  sehingga  untuk  setiap
V ( G )  berlaku V ( G )  jika  hanya  jika  ( )  ( ) E ( H ) .
Kardinalitashimpunan S dinotasikan  dengan | | ,  adalah  banyaknya  anggota  dari S. Ordegraf G adalah | ( )| , dan ukurangraf G adalah | ( )| . Graf G berorde dinotasikan dengan .Derajattitik , dinotasikan dengan ( ) , adalah | ( )| . Derajat maksimum dari G adalah ( )        * ( ) ( )+ , dan derajat minimum dari G adalah ( ) min * ( ) ( )+ .  Graf G disebut  graf *           + jika * ( )     ( )    + .  Graf  F  disebut komplemendari  graf G, jika V(F) = V ( G )  dan  E ( F )  jika  dan  hanya  jika  E ( G ). Komplemen dari graf G dinotasikan dengan ̅ . Dua graf G dan H disebut isomorfik jika terdapat pemetaaan  satu-satu  dan  pada  : V ( G )  V ( H )sedemikian  sehingga  untuk  setiap V ( G )
berlaku V ( G ) jika hanya jika  ( )  ( ) E ( H ) . Graf H(V’, E’) disebut subgraf dari G jika  ( ) dan E’  E(G). selanjutnya, subgraf H dari G ditulis H  G. Sufgraf H dikatakan subgraf maksimal dari G jika H memuat semua sisi ( ) untuk semua Misalkan H  G, H disebut subgraf perentang dari G jika V ( H ) = V ( G ).    Subgraf  perentang  yang  setiap  titiknya  berderajat  sama  katakanlah r disebut  subgraf perentang  reguler- r atau  faktor- r .  Jadi  subgraf  perentang  reguler  berderajat  1  disebut  faktor-1, derajat 2 disebut faktor-2, dan seterusnya.
1 Jurusan Matematika FMIPA Universitas Hasanuddin

## 2. Amalgamasi Graf
Amalgamasi graf  adalah suatu operasi pada graf. Beberapa operasi pada graf yang telah dikenal sebelumnya diantaranya: operasi jumlah, gabung, kali dan corona.

## 2.1. Operasi Gabung, Jumlah, dan Kali
Misalkan adalah  graf  dengan  himpunan  titik dan  himpunan  sisi , . Graf gabung adalah suatu graf dengan himpunan titik dan himpunan sisi
Definisi graf jumlah secara umum belum ada. Namun untuk jumlah dua graf, Zykov
telah mendefinisikannya pada tahun 1952 seperti berikut : Graf jumlah ( join ) adalah
suatu  graf  dengan ( ) dan ( ) * + .  Contoh grafjumlah ̅̅̅ dapat dilihat pada Gambar 1b.
̅̅̅̅ :
:
Gambar 1. (a) Graf ̅̅̅ dan (b) Graf ̅̅̅ .
Di  sini  disajikan  Graf  kali  dua  graf  dan  tiga  graf.  Graf  kali G = G 1 x G 2 adalah  graf  dengan himpunan titik V ( G ) = V 1 x V 2 dan himpunan sisi E ( G ) = { uv : u= ( u 1 ,u 2 ), v= ( v 1 ,v 2 ) ( ) dengan u 1 =v 1 dan u 2 v 2 ( ) atau u 2 =v 2 dan u 1 v 1 ( )+ Definisi  graf  kali  dari  dua  graf  dapat dikembangkan menjadi graf kali dari tiga graf atau empat graf dan seterusnya. Graf kali dari tiga graf  ditulis G = G 1 x G 2 x G 3 adalah  graf  dengan  himpunan  titik V ( G )  = V 1 x V 2 x V 3 dan himpunan  sisi E ( G )  =  { uv :  jika u= ( u 1 ,u 2 , u 3 ), v= ( v 1 ,v 2 , v 3 ) ( ) dengan u 1 =v 1 ,u 2 = v 2 dan u 3 v 3 ( ) atau u 1 = v 1 , u 3 =v 3 dan u 2 v 2 ( ) atau u 2 = v 2 , u 3 =v 3 dan u 1 v 1 ( )+
Sebagai  contoh,  misalkan  himpunan  titik  3  lintasan  berorde  2  berturut-turut  : V ( )={ x 1 , x 2 }, V( )  ={ y 1 ,y 2 }    dan V ( )={ z 1 ,z 2 }  dengan  himpunan  sisi  berturut-turut: E ( )={ e 11 = x 1 x 2 }, E( ) ={ e 21 = y 1 y 2 }  dan E ( )={ e 31 = z 1 z 2 }. Graf hasil kali dari tiga lintasan berode 2: x x adalah graf dengan himpunan titik
V ( x x )={( x 1 ,y 1 , z 1 ), ),( x 1 ,y 1 , z 2 ), ( x 1 ,y 2 , z 1 ), ( x 1 ,y 2 , z 2 ), ( x 2 y 1 ,z 1 ) , ( x 2 , y 1 ,z 2 ), ( x 2 , y 2 , z 1 ), ( x 2 , y 2 , z 2 } dan himpunan  sisi E ( x x )={( x 1 ,y 1 ,  z 1 )( x 1 ,y 1 , z 2 ),    ( x 1 ,y 1 ,  z 1 )  ( x 1 ,y 2 , z 1 ),    ( x 1 ,y 1 , z 1 )( x 2 y 1 ,z 1 ) , ( x 1 ,y 1 , z 2 )( x 1 y 2 ,z 2 ) , ( x 1 ,y 1 , z 2 )( x 2 , y 1 ,z 2 ),  ( x 1 ,y 2 , z 1 )( x 1 ,y 2 , z 2 ),  ( x 1 ,y 2 , z 1 )( x 2 , y 2 , z 1 ), ( x 1 ,y 2 , z 1 )( x 1 , y 2 , z 2 ),    ( x 1 ,y 2 , z 2 )( x 2 , y 2 , z 2 ),  ( x 2 y 1 ,z 1 )( x 2 , y 2 , z 1 ),      ( x 2 , y 1 ,z 1 )( x 2 , y 1 , z 2 ),    ( x 2 , y 2 , z 1 ) ( x 2 , y 2 , z 2 )}.
(1)

## Hasmawati

## 2.2. Operasi Amalgamasi Graf
Penggunaan  induksi  matematika  dalam  pembuktian  faktor  pada  graf  hasil  kali  linasan diperlukan  operasi  amalgamasi.  Olehnya  itu,  penyajian  berikut  lebih  rinci  menguraikan pengertian amalgamasi graf, khususnya untuk amalgamasi sisi. Amalgamasi graf terdiri atas dua yakni amalgamasi titik dan amalgamasi sisi.
Misalkan G i , i= 1,2,..., n adalah  graf  dengan  titik  tetap dan  sisi  tetap Amalgamasi titik graf G i pada titik untuk suatu j dinotasikan ( ) adalah graf  yang  terdiri  atas  semua  graf dengan
.  Sebagai  contoh,  himpunan titik  dan  sisi  graf G 1 = adalah  graf  lintasan  berorde  3  dengan  himpunan  titik V ( )= * + dan  himpunan  sisi E ( )= * + .  Secara umum  dapat  ditulis G i = adalah  lintasan  ke- i berorde n dengan  himpunan  titik V ( )= * + dan  himpunan  sisi E ( )= { } .  Lihat Gambar 3.
x 1 x 2 y 1 y 2 z 1 z 2 ( x 1, y 2, z 1 ) x x ( x 2, y 2, z 1 ) ( x 2, y 2, z 2 )
( x 2, y 1, z 2 ) ( x 1, y 1, z 2 ) ( x 2, y 1, z 1 ) ( x 1, y 2, z 2 ) ( x 1, y 1, z 1 )
Gambar 2. Graf x x .

## Hasmawati
Menurut definisi di atas, Amalgamasi titik dari dua graf lintasan berorde dua dinotasikan ( )   ( ) adalah graf dengan himpunan titik { v 11 =v 21 , v 12 , v 22 } dan himpunan  sisi  { e 11 =v 11 v 12 = v 21 v 12 ,e 21 =v 21 v 22 }  atau  { e 11 =v 11 v 12 ,e 21 =v 11 v 22 },  karena v 11 =v 21 .  Jadi amalgamasi  titik  graf-graf  adalah  penggabungan  graf-graf  tersebut  dengan  mennyatukan  setiap titiknya menjadi hanya satu titik.  Dapat dilihat dengan jelas pada amalgamasi ( ) yakni penggabungan graf dengan mennyatukan titik dan .  Lebih jelasnya lihat Gambar 4.
v 12 v 22 : :
v 11 v 21
v 22 v 12 v 11 = v 21
( ) Gambar 4.  Graf Lintasan dan Serta Graf Amalgamasinya ( ) . Lebih jauh, notasikan ( )   * + dan ( )   * + .                (2) Maka amalgamasi titik ( ) . Jelasnya perhatikan Gambar 5. Gambar 3.  Graf Lintasan.
Gambar 5. Graf Amalgamasi Titik ( ) .
Misalkan G i dengan  himpunan  sisi E ( G i )={ e i 1 , e i 2 ,  ..., e i j }  dan G r dengan  himpunan  sisi E ( G r )={ e r 1 , e r 2 ,  ..., e r j }.  Amalgamasi  sisi G i terhadap G r adalah  mengambil  semua G i dan G r dengan e i 1 = e r 1 , e i 2 = e r 2 , ..., e r j = e i j untuk suatu i dan r , dinotasikan dengan ( G i ; e i 1 , e i 2 , ..., e i j ; G r ; e r 1 , e r 2 , ..., e r j ).
Sebagai contoh akan dikontruksi amalgamasi sisi x x terhadap x x . Dengan  mengikuti  notasi  (1)  dan  (2),  maka  himpunan  titik ( x x )    ( x x ) ={( x 1 ,y 1 ,  z 1 ),  ),( x 1 ,y 1 , z 2 ),  ( x 1 ,y 2 , z 1 ),  ( x 1 ,y 2 , z 2 ),  ( x 2 y 1 ,z 1 ) , ( x 2 , y 1 ,z 2 ),  ( x 2 , y 2 , z 1 ),  ( x 2 , y 2 , z 2 },  dan himpunan  titik ( x x ) ={( x 1 ,y 1 ,  z 2 ),  ),( x 1 ,y 1 , z 3 ),  ( x 1 ,y 2 , z 2 ),  ( x 1 ,y 2 , z 3 ),  ( x 2 y 1 ,z 2 ) , ( x 2 , y 1 ,z 3 ), ( x 2 , y 2 , z 2 ), ( x 2 , y 2 , z 3 }. Notasikan e ijz =( x i ,y j ,  z r )( x i ,y j , z r+1 ), e xij =( x r ,y 1 ,  z 1 )( x r+1 ,y i , z j ),  dan e iyj =( x i ,y r z j )( x i ,y r+1 , z j ),  Maka himpunan sisi ( x x )    ( x x ) = { e 11z =( x 1 ,y 1 , z 1 )( x 1 ,y 1 , z 2 ), e 1y1 = ( x 1 ,y 1 , z 1 ) ( x 1 ,y 2 , z 1 ), e x11 =  ( x 1 ,y 1 ,  z 1 )( x 2 y 1 ,z 1 ) ,  e 1y2 =( x 1 ,y 1 , z 2 )( x 1 y 2 ,z 2 ) ,e x12 =( x 1 ,y 1 , z 2 )( x 2 , y 1 ,z 2 ), e 12z =( x 1 ,y 2 , z 1 )( x 1 ,y 2 , z 2 ), e x21 =( x 1 ,y 2 , z 1 )( x 2 , y 2 , z 1 ), e 12z =( x 1 ,y 2 , z 1 )( x 1 , y 2 , z 2 ), e x22 =( x 1 ,y 2 , z 2 )( x 2 , y 2 , z 2 ), e 2y1 =( x 2 y 1 ,z 1 )( x 2 , y 2 , z 1 ), e 21z = ( x 2 , y 1 ,z 1 )( x 2 , y 1 , z 2 ), e 22z = ( x 2 , y 2 , z 1 ) ( x 2 , y 2 , z 2 ), dan himpunan sisi titik ( x x ) ={( x 1 ,y 1 , z 2 )( x 1 ,y 1 , z 3 )= e 11z ,    ( x 1 ,y 1 ,  z 2 )  ( x 1 ,y 2 , z 2 )= e 1y2 ,  ( x 1 ,y 1 ,  z 2 )( x 2 y 1 ,z 2 )= e x12 , ( x 1 ,y 1 , z 3 )( x 1 y 2 ,z 3 )= e 1y3 , ( x 1 ,y 1 , z 3 )( x 2 , y 1 ,z 3 )= e x13 , ( x 1 ,y 2 , z 2 )( x 1 ,y 2 , z 3 )= e 12z , ( x 1 ,y 2 , z 2 )( x 2 , y 2 , z 2 )= e x22 , ( x 2 ,y 1 , z 2 )( x 2 , y 1 , z 3 )= e 21z , ( x 1 ,y 2 , z 3 )( x 2 , y 2 , z 3 )= e x23 ,( x 2 y 1 ,z 2 )( x 2 , y 2 , z 2 )= e 2y2 , ( x 2 , y 1 ,z 2 )( x 2 , y 1 , z 3 )= e 21z ,  ( x 2 , y 2 , z 2 ) ( x 2 , y 2 , z 3 )= e 22z }. Amalgamasi  sisi x x terhadap x x dinotasikan    dengan ( x x x x ) dapat  disingkat  menjadi ( x x x x ) adalah  graf  dengan  himpunan  titik    titik    {( x 1 ,y 1 ,  z 1 ), ),( x 1 ,y 1 , z 2 ), ( x 1 ,y 2 , z 1 ), ( x 1 ,y 2 , z 2 ), ( x 2 y 1 ,z 1 ) , ( x 2 , y 1 ,z 2 ), ( x 2 , y 2 , z 1 ), ( x 2 , y 2 , z 2 ) , ( x 1 ,y 1 , z 3 ), ( x 1 ,y 2 , z 3 ),( x 2 , y 1 ,z 3 ),    ( x 2 , y 2 , z 3 },  dan  himpunan  sisi  { e 11z =( x 1 ,y 1 ,  z 1 )( x 1 ,y 1 , z 2 ), e 1y1 =  ( x 1 ,y 1 ,  z 1 )  ( x 1 ,y 2 , z 1 ), e x11 = ( x 1 ,y 1 ,  z 1 )( x 2 y 1 ,z 1 ) ,  e 1y2 =( x 1 ,y 1 , z 2 )( x 1 y 2 ,z 2 ) ,e x12 =( x 1 ,y 1 , z 2 )( x 2 , y 1 ,z 2 ), e 12z =( x 1 ,y 2 , z 1 )( x 1 ,y 2 , z 2 ), e x21 =( x 1 ,y 2 , z 1 )( x 2 , y 2 , z 1 ), e 12z =( x 1 ,y 2 , z 1 )( x 1 , y 2 , z 2 ), e x22 =( x 1 ,y 2 , z 2 )( x 2 , y 2 , z 2 ), e 2y1 =( x 2 y 1 ,z 1 )( x 2 , y 2 , z 1 ), e 21z = ( x 2 , y 1 ,z 1 )( x 2 , y 1 , z 2 ), e 22z = ( x 2 , y 2 , z 1 ) ( x 2 , y 2 , z 2 ), ( x 1 ,y 1 , z 2 )( x 1 ,y 1 , z 3 )= e 11z ,  ( x 1 ,y 1 , z 3 )( x 1 y 2 ,z 3 )= e 1y3 , ( x 1 ,y 1 , z 3 )( x 2 , y 1 ,z 3 )= e x13 ,    ( x 1 ,y 2 , z 2 )( x 1 ,y 2 , z 3 )= e 12z ,    ( x 2 ,y 1 , z 2 )( x 2 , y 1 , z 3 )= e 21z ,  ( x 1 ,y 2 , z 3 )( x 2 , y 2 , z 3 )= e x23 ,  ( x 2 , y 1 ,z 2 )( x 2 , y 1 , z 3 )= e 21z ,  ( x 2 , y 2 , z 2 ) ( x 2 , y 2 , z 3 )= e 22z }.
Bentuk graf ( x x x x
) dapat dilihat pada Gambar 6. :

## Hasmawati
Dapat diperiksa bahwa amalgamasi sisi ( x x x x ) sama
dengan x x dengan ( ) . (3) Teorema 1.
Amalgamasi  sisi ( x x x x ) sama  dengan
graf kali dari tiga lintasan x x dengan ( ) .
Bukti.
x 1
x 2 y 1 y 2
z 1 z 2 Gambar 6.  Graf Amalgami Sisi x x Terhadap x x .
z 2 z 3 x x e x21 e 22z e 2y2 e x12 e 21z e 2y1 e x22 e x11 e 1y1 e 1y2 e 11z e 2y2 e x12 e 1y2 e x22 ( x 2 , y 2 , z 3 ) ( x 2 , y 1 , z 3 ) ( x 1 , y 1 , z 3 ) ( x 1 , y 2 , z 3 )
x x ( x x x x ): e x21 e 22z e 21z e 2y1 e x11 e 1y1 e 11z e 2y2 e x12 e 1y2 e x22 ( x 2 , y 2 , z 3 ) ( x 2 , y 1 , z 3 ) ( x 1 , y 1 , z 3 ) ( x 1 , y 2 , z 3 )

## Hasmawati
Akan dibuktikan dengan pembuktian induksi matematika dengan n  3. Untuk n = 3, ( x x x x ) sama dengan x x dengan ( ) . Hal ini benar sesuai dengan persamaan (3).
Asumsikan  Teorema  1  benar  untuk    setiap n  k ,  yakni ( x x x x ) sama  dengan  graf  kali  dari  tiga  lintasan x x dengan ( ) . Akan ditunjukkan bahwa ( x x x x
) sama dengan graf kali dari tiga lintasan x x dengan
( ) . Dari  (2)  diketahui  bahwa    apabila ( ) ,  maka ( ) + dan ( )   * + . Sehingga x x adalah graf dengan
himpunan titik   {( x 1 , y 1 , z 1 ), ( x 1 , y 2 , z 1 ),  ( x 2 , y 2 , z 1 ),  ), ( x 2 , y 1 , z 1 ),   ( x 1 , y 1 , z 2 ), ( x 1 y 2 ,z 2 ) , ( x 2 , y 2 ,z 2 ), ( x 2 , y 1 , z 2 ) ,   ( x 1 , y 1 , z 3 ), ( x 1 , y 2 , z 3 ),( x 2 , y 2 ,z 3 ),  ( x 2 , y 1 , z 3 ), ...,  ( x 1 , y 1 , z k-1 ), ( x 1 , y 2 , z k- 1 ),( x 2 , y 2 ,z k-1 ),  ( x 2 , y 1 , z k-1 ),  ( x 1 , y 1 , z k ), ( x 1 , y 2 , z k ),( x 2 , y 2 ,z k ),  ( x 2 , y 1 , z k )}, dan himpunan sisi { , , ....,
e 1yk , e x2k , e 2yk , e x1k }.
Demikian pula dengan x x adalah  graf dengan himpunan titik {( x 1 , y 1 , z k ), ( x 1 , y 2 , z k ),( x 2 , y 2 ,z k ),  ( x 2 , y 1 , z k ),  ( x 1 , y 1 , z k+1 ), ( x 1 , y 2 , z k+1 ),( x 2 , y 2 ,z k+1 ),  ( x 2 , y 1 , z k+1 )}
dan
himpunan sisi{ , (   ) (   ) (   ) (   ) }.
Amalgamasi  sisi ( x x x x ) adalah  graf  dengan mengambil semua x x dan x x , yakni graf dengan himpunan titik   {( x 1 , y 1 , z 1 ), ( x 1 , y 2 , z 1 ),  ( x 2 , y 2 , z 1 ),  ), ( x 2 , y 1 , z 1 ),   ( x 1 , y 1 , z 2 ), ( x 1 y 2 ,z 2 ) , ( x 2 , y 2 ,z 2 ), ( x 2 , y 1 , z 2 ) ,   ( x 1 , y 1 , z 3 ), ( x 1 , y 2 , z 3 ),( x 2 , y 2 ,z 3 ),  ( x 2 , y 1 , z 3 ), ...,  ( x 1 , y 1 , z k-1 ), ( x 1 , y 2 , z k-1 ),( x 2 , y 2 ,z k-1 ),  ( x 2 , y 1 , z k-1 ),  ( x 1 , y 1 , z k ), ( x 1 , y 2 , z k ),( x 2 , y 2 ,z k ),  ( x 2 , y 1 , z k ), ),  ( x 1 , y 1 , z k+1 ), ( x 1 , y 2 , z k+1 ),( x 2 , y 2 ,z k+1 ),  ( x 2 , y 1 , z k+1 )} dan himpunan sisi { , ,  ...., e 1yk , e x2k , e 2yk , e x1k , (   ) (   ) (   ) (   ) }.
Dapat diperiksa bahwa graf dengan himpunan titik dan himpunan sisi seperti ini adalah graf x x . Jadi x x P n = ( x x x x ) dengan ( ) . 

## 3. Dekomposisi Graf Hasil Kali Tiga Lintasan

## Hasmawati
Pada bagian pendahuluan  telah didefinisikan tentang subgraf. Himpunan subgraf dengan syarat tertentu akan dibahas pada subbab ini.

## Definisi 1.
Misalkan G adalah graf dan H i  G untuk setiap i. Dekomposisi graf G adalah himpunan {H 1 , H 2 , ...,  H k }  sedemikian  sehingga ( ) ( )   ( )       ( )     ( ) dan  V(H i )  = V(H j ) untuk setiap i  j. Dekomposisi graf biasanya ditulis ⨁   ⨁ .
Pada  Definisi  1  dapat  dilihat  bahwa V ( H i )  = V ( H j )  untuk  setiap i  j .  Ini  artinya  setiap  subgraf H i merupakan subgraf perentang dari graf G . Himpunan subgraf-subgraf perentang H i merupakan dekomposisi  graf G jika  setiap  sisi  pada  subgraf  perentang  tersebut  saling  bebas  satu  dengan lainnya.

## Contoh 1.
Diberikan  tiga  lintasan  orde  dua  dengan  himpunan  titik  berturut-turut V ( )={ x 1 , x 2 }, V( ) ={ y 1 ,y 2 }   dan V ( )={ z 1 ,z 2 }, dan  himpunan  sisi  berturut-turut: E ( )={ e 11 = x 1 x 2 }, E( ) ={ e 21 = y 1 y 2 }    dan E ( )={ e 31 = z 1 z 2 }.  Graf  hasil  kali tiga  lintasan x x dapat  digambar    pada Gambar 7.
Gambar 7. Graf Hasil Kali Tiga Lintsasan Orde Dua.
Bentuk dan label titik-titik graf G pada Gambar 7 dapat ditulis seperti pada Gambar 8.
Gambar 8. Bentuk dan Label Titik-Titik Graf.
Beberapa subgraf perentang dari graf hasil kali tiga lintasan x x dapat dilihat pada Gambar 9. Subgraf graf perentang tersebut adalah H 1 , H 2 , H 3 , ..., H 6 .Subgraf perentang reguler adalah subgraf H 3 , H 4 ,dan H 5 .
h=( x 1, y 2, z 1 ) x x u=( x 2, y 2, z 1 ) v = ( x 2, y 2, z 2 ) w=( x 2, y 1, z 2 ) s=( x 1, y 1, z 2 ) x=( x 2, y 1, z 1 ) r=( x 1, y 2, z 2 ) t=( x 1, y 1, z 1 ) h u v w s x r t
Gambar 9. Dekomposisi Graf
x x adalah { H 1 , H 2 } dan  { H 3 , H 4 , H 5 }.
Subgraf perentang lain dari graf
x x dapat dilihat pada Gambar 10.
h v w s x r t h w s x r t h u v w s x r t h u v w s x r t h s x r t h s x r t

## Hasmawati
Gambar 10. Sub Graf Perentang Reguler dari G.
Dekomposisi lain dari graf x x adalah { H 5 , H 7 }, dan  { G , H 8 }.
Definisi 3.1. Misalkan himpunan {H 1 , H 2 , ..., H k } adalah dekomposisi dari G. Jika subgraf H 1 , H 2 , ..., H k-1 dan H k adalah subgraf perentang reguler maka dekomposisi {H 1 , H 2 , ..., H k } disebut faktorisasi dari graf G .
Perhatikan  Gambar  8,  9,  dan  Gambar  10.  Pada  Gambar  8,  dapat  dilihat  bahwa  graf G juga merupakan  subgraf  perentang  dari G, yakni  subgraf  perentang  kuasa  reguler  berderajat  3  atau faktor-3.  Pada  Gambar  9,  subgraf  perentang H 3 , H 4 ,dan H 5 juga  merupakan  subgraf  perentang reguler  derajat  satu.Jadi  subgraf H 3 , H 4 ,dan H 5 ,  semuanya  adalah  faktor-1.  Selanjutnya,  pada Gambar  10,  subgraf H 7 adalah  faktor-2,  dan  subgraf H 8 adalah  faktor-0.  Dengan  demikian, terdapat tiga faktorisasi dari graf G yakni dekomposisi { H 3 , H 4 , H 5 }, { H 5 , H 7 }, dan  { G , H 8 }. Pembahasan selanjutnya, adalah melihat apakah graf hasil kali tiga lintasan orde 2 ( x x P n ) memiliki faktorisasi atau tidak.
Untuk n = 2,  graf hasilkali x x P n memiliki faktorisasi seperti yang telah diuraikan.
Untuk n =  3,  graf  hasil  kali x x P n adalah x x P 3 = ( x x x x ) dengan ( ) .  Bentuk  graf x x P 3 dapat  dilihat pada Gambar 11. Dapat diperiksa bahwa graf hasil kali x x P 3 memiliki dekomposisibanyak subgraf  perentang  sehingga  juga  memiliki  banyak  dekomposisi.  Namun  tidak  ada  dekomposisi yang merupakan faktorisasi.
(4)
Teorema 2.
Graf hasil kali x x P n tidak memiliki faktorisasi untuk n  3.
Bukti. Pembuktian dilakukan dengan induksi matematika dengan memulai pada induksi n = 3.
(a) Untuk n = 3, graf hasil kali x x P n tidak memiliki faktorisasi. Dari (4) (b) Untuk n = 4, graf hasil kali x x P n adalah seperti berikut:
u h v w s x r t u h v w s x r t

## Hasmawati
Subgraf perentang dari graf hasil kali x x P 4 adalah sebagai berikut
Dekomposisi  dari  graf  hasil  kali x x P 4 adalah  { H 1 , H 2 },  { H 2 , H 3 , H 4 },  dan  { H 4 , H 5 }. Dapat  diperiksa  bahwa  ke  tiga  dekomposisi  tersebut  tidak  ada  yang  merupakan faktorisasi.  Selanjutnya,  dari  Teorema.1  diketahui  bahwa x x merupakan amalgamasi sisi x x terhadap x x dengan ( ) . Juga telah  diketahui  bahwa x x tidak  memiliki  faktorisasi  sedangkan x x memiliki  faktorisasi.    Berarti  graf  yang  tidak  memiliki  faktorisasi  adalah  graf  yang
H 1 :
H 2 : H 3 : H 4 : H 5 : H 6 :

## Hasmawati
merupakan amalgamasi sisi dari graf yang tidak memiliki faktorisasi  terhadap graf yang memiliki faktorisasi.
(c)
Asumsikan x x = x x P r tidak memiliki faktorisasi untuk setiap  3  r  k . Akan ditunjukkan bahwa x x P k+ 1 juga tidak memiliki faktorisasi. Dari Teorema 1 diketahui bahwa x x P k+ 1 merupakan amalgamasi sisi x x terhadap x x dengan ( ) .  Menurut  asumsi x x tidak  memiliki faktorisasi, sedangkan x x memiliki faktorisasi.  Berdasarkan (2), graf hasil kali x x P k+ 1 tidak memiliki faktorisasi.
(d) Berdasarkan  (a),  (b),  dan  (c),  graf  hasil  kali x x P n = P 2 x P 2 x P n tidak  memiliki faktorisasi untuk setiap n , n  3. 

## 4. Kesimpulan
Beberapa hal yang dapat disimpulkan dalam tulisan ini antaralain:
a. Amalgamasi titik ujung dua lintasan juga merupakan lintasan,
b. Amalgamasi sisi dua graf hasil kali dari tiga lintasan juga merupakan graf hasil kali tiga lintasan.
c. Graf hasil kali tiga lintasan orde dua memiliki faktorisasi.
Graf  hasil  kali  dua  lintasan  orde  dua  terhadap  lintasan  orde  lebih  dari  dua  memiliki dekomposisi tetapi tidak memiliki faktorisasi.

## Daftar Pustaka
[1] Bariroh A., 2010. Faktorisasi Graf Beraturan dengan Orde Genap. UIN Malang.
[2] Chartrand  G.  dan  Zhang  P.,  2005. Introduction  to  Graph  Theory .  Mc  Graw  Hill International Edition.
[3] Hasmawati,  2007.Bilangan  Ramsey  untuk  Graf  yang  Memuat  Bintang. Disertasi . Departemen Matematika ITB, Bandung.