## SPEKTRUM PADA GRAF REGULER KUAT

## Rizki Mulyani, Triyani dan Niken Larasati
Program Studi Matematika, Fakultas Sains dan Teknik Universitas Jenderal Soedirman
Email : rizky90@gmail.com
ABSTRACT. This  article  studied  spectrum  of  strongly  regular  graph.    This  spectrum can  be  determined  by  the  number  of  walk  with  lenght  l  on  connected  simple  graph, equation of square adjacency matrix and eigen value of strongly regular graph.
Key words: graph spectrum, strongly regular graph, eigen value
ABSTRAK. Artikel ini mengkaji spektrum pada graf reguler kuat.    Spektrum ini dapat ditentukan dengan mengetahui  banyaknya jalan dengan panjang l pada graf sederhana terhubung,  persamaan  dari  kuadrat  matriks  ketetanggaan  graf  reguler  kuat  dan  nilai eigen pada graf reguler kuat.
Kata kunci : spektrum graf, graf reguler kuat, nilai eigen

## 1. PENDAHULUAN
Teori spektral graf mulai dipelajari pada tahun 1950 an. Teori spektral graf ini merupakan salah satu kajian dalam teori graf yang mempelajari sifat-sifat graf dalam  hubungannya  dengan  polinom  karakteristik,  nilai  eigen  dan  vektor  eigen dari  matriks  yang  merepresentasikan  graf.    Salah  satu  matriks  representasi  dari graf  adalah  matriks  ketetanggaan.    Matriks  ketetanggaan  dari  sebuah  graf sederhana dengan n titik adalah matriks berukuran n x n yang elemen baris ke -i dan  kolom  ke -j bernilai  0  atau  1.    Elemen  baris  ke -i kolom  ke -j pada  matriks ketetangaan  akan  bernilai  0  jika  titik v i tidak  bertetangga  dengan  titik v j ,  dan bernilai  1  jika  titik v i bertetangga  dengan  titik v j . Matriks  ketetanggaan  dari sebuah  graf  bersifat  simetri,  sehingga  nilai  eigen  dari  matriks  ini  semuanya bernilai riil (Kolman, 2007).
JMP : Volume 5 Nomor 1, Juni 2013, hal. 13 - 21
Salah  satu  kajian  dalam  teori  spekral  graf  adalah  menentukan  spektrum pada graf.  Spektrum pada graf merupakan pasangan terurut dari nilai-nilai eigen matriks  ketetanggaan  beserta  multiplisitasnya.    Jika  adalah  nilai  eigen  dari matriks  A,  maka  multiplisitas  aljabar    didefinisikan  sebagai  multiplisitas  dari  sebagai  akar  polinom  karakteristik  dari  A.  Sementara  itu  multiplisitas  geometri didefinisikan  sebagai  dimensi  dari  ruang  eigen  E  .  Pada  matriks  simetri, multiplisitas geometri sama dengan multiplisitas aljabarnya (Kolman, 2007).
Graf  reguler  kuat  dengan  parameter  ( n,k,a,b )  didefinisikan  sebagai  graf reguler berderajat k yang mempunyai n titik dengan jumlah ketetanggaan bersama untuk  setiap  pasang  titik  yang  bertetangga  adalah  a  dan  jumlah  ketetanggaan bersama untuk setiap pasang titik yang tidak bertetangga adalah b (Biggs,1993). Spektrum  pada  graf  reguler  kuat  dengan  parameter (n,k,a,b) dapat  diturunkan dari  lemma  dan  teorema  tentang  banyaknya  jalan  berbeda  dari  titik u ke  titik v pada  graf  terhubung,    persamaan  dari  kuadrat  matriks  ketetanggaan  graf  reguler kuat,  dan nilai eigen dari matriks ketetanggaan graf reguler kuat.
Pada artikel ini, lemma dan teorema tersebut diberikan oleh Biggs (1993), Chaudhary et. al (1986) dan Bapat (2010). Namun bukti dari lemma dan teorema tersebut  belum  tertulis  secara  rinci.  Oleh  karena  itu,  penulis  memberikan  bukti- buktinya  lebih  rinci.  Selanjutnya  lemma  dan  teorema  tersebut  digunakan  oleh penulis untuk memperoleh bentuk spektrum pada graf reguler kuat.

## 2. SPEKTRUM GRAF REGULER KUAT
Misalkan ( ) A G adalah  matriks  ketetanggaan  dari  graf G dengan  nilai eigen  berbeda 0 1 1 . s        Misal i m adalah  multiplisitas  dari  nilai  eigen
ke –i,   0,1, 2,..., 1 . i s   Spektrum  graf G yang  dinotasikan  dengan spec ( G ) didefinisikan sebagai
0 1 1 0 1 1 ... ( ) ... s s spec G m m m          
 
(Biggs, 1993).
14                                                                                                       Mulyani, dkk.
Ada  beberapa  lemma  dan  teorema  yang  dapat  digunakan  sebagai  acuan untuk menentukan spektrum pada graf reguler kuat (n, k, a, b). Berikut ini adalah lemma yang ditulis oleh Biggs (1993).

## Lemma 2.1 (Biggs, 1993).
Jika A adalah matriks ketetanggaan dari graf G, maka elemen  baris  ke- i kolom    ke- j   pada    matriks  A   menyatakan  jumlah  jalan  yang  berbeda dari i v ke j v dengan panjang   pada graf  G.
Bukti. Lemma ini akan dibuktikan dengan induksi matematika.
i) Untuk 1,  diperoleh 1 . A A  Elemen-elemen  ke ( , ) i j pada  matriks ketetanggaan graf G adalah
  1, jika ( ) ( ) 0, jika ( ) ( ). i j ij i j v v E G A v v E G      
Jika i v bertetangga dengan j v maka terdapat sisi yang menghubungkan langsung dari i v ke . j v Hal  ini  berarti  terdapat  jalan  dengan  panjang  satu  dari i v ke j v .
Sebaliknya  jika i v tidak  bertetangga  dengan , j v maka  tidak  terdapat  sisi  yang menghubungkan langsung dari titik i v ke . j v Hal ini berarti tidak terdapat jalan dengan panjang satu dari i v ke j v . Akibatnya elemen baris ke- i kolom ke- j pada matriks ketetanggaan  menyatakan jumlah jalan dengan panjang 1 dari i v ke . j v
ii) Asumsikan  benar  untuk k  ,  artinya ( ) k ij A menyatakan  jumlah  jalan  yang berbeda dari i v ke j v dengan panjang . k
iii) Akan ditunjukkan 1 ) ( ij k A  menyatakan jumlah jalan yang berbeda dari i v ke
j v dengan panjang 1 k  .
Jumlah  jalan  yang  berbeda  dari v i ke j v dengan  panjang 1 k  sama  dengan jumlah jalan yang berbeda dari i v ke h v dengan panjang k dengan h v adalah titik yang  bertetangga  dengan . j v Hal  ini  berarti  jumlah  jalan  dengan  panjang 1 k  dari i v ke j v adalah ( ) ( ) ( ) h j k ij v v E G A   ,  karena  elemen  ( ) hj A bernilai  satu  jika h v
bertetangga  dengan j v dan  bernilai  0  jika h v tidak  bertetangga  dengan j v . Akibatnya diperoleh
               
    1 2 1 2 1 1 ... . n k k k k hj j j nj ih i i in h k k ij ij A A A A A A A A
A A A         
Hasil ini menyimpulkan  bahwa elemen baris ke- i kolom ke- j pada matriks 1 k A  . menyatakan jumlah jalan dari i v ke j v dengan panjang 1 k  .
Teorema 2.2 (Chaudhary et.al. , 1986).
Jika G adalah graf reguler kuat dengan parameter (n,k,a,b), maka kuadrat matriks ketetanggaan dari graf G adalah 2 ( ) ( ) . A a b A k b I bJ     
Bukti : Untuk membuktikan teorema ini akan dicari elemen baris ke -i kolom ke -j pada  kuadrat  matriks  ketetanggaan 2 ( ) ij A .    Untuk i  =  j, elemen  diagonal  dari kuadarat  matriks  ketetanggaan  suatu  graf  merepresentasikan  derajat  titik v i .
Karena  G  adalah  graf  reguler  kuat  berderajat k ,  maka 2 ( ) ii A k  .  Dari  lemma  1 dan  definisi  graf  reguler  kuat,  elemen  baris  ke- i kolom  ke- j untuk i j  dan ( ) ( ) i j v v E G  pada kuadrat matriks ketetanggaan graf reguler kuat
merepresentasikan  juga  banyaknya  ketetanggaan  bersama  untuk  setiap  dua  titik yang bertetangga yaitu a . Sedangkan untuk elemen baris ke- i kolom ke- j dengan
i j  dan  ( ) ( ) i j v v E G  pada  kuadrat  matriks  ketetanggaan  graf  reguler  kuat merepresentasikan  juga  banyaknya  ketetanggaan  bersama  untuk  setiap  dua  titik
16                                                                                                       Mulyani, dkk.
yang  tidak  bertetangga  yaitu  b.  Oleh  karena  itu, 2 ( ) ij A dapat  ditulis  sebagai berikut
  2 , untuk
, untuk ( ) ( ) , untuk ( ) ( ). i j i ij j k i j A a i j dengan v v E G b i j dengan v v E G              1
Persamaan (1) dapat juga ditulis sebagai berikut
2 . c A kI aA bA    (2)
Karena G adalah  graf  reguler  maka c A A J I    (Biggs,  1993),  apabila
c A J I A    disubstitusikan ke persamaan (2) diperoleh
2 ( ) 2 ( ) ( ) . A kI aA c J I A
A a b A k b I bJ          
Teorema 2.3 (Bapat, 2010).
Jika  G  adalah graf  reguler  kuat  dengan  parameter  (n,k,a,b)  dan
    2 4 t a b k b     ,  maka  setiap  nilai  eigen  dari  A  adalah  k  atau
  1 2 a b t   .
Bukti. Nilai eigen  o = k diperoleh dari proposisi graf reguler G yang menyatakan k adalah nilai eigen dari matriks ketetanggaan G (Biggs, 1993 ). Selanjutnya akan dibuktikan   * 1 2 a b t     juga  nilai  eigen dari matriks  ketetanggaan  graf reguler  kuat  dengan  parameter (n,  k,  a,  b). Misal  diambil  nilai  eigen k   ,  dan vektor  eigen  yang  bersesuaian  dengan  nilai  eigen  adalah y .  Dari  teorema  2 diperoleh persamaan
2 ( ) ( ) A a b A k b I bJ      2 ( ) ( ) . A b a A b k I bJ      ( 3)
Dengan  mengalikan  ruas  kiri  dan  ruas  kanan  pada  persamaan  (3)  dengan y diperoleh
2 ( ) ( ) . b a A b k I bJ A      y y y y (4)
Vektor  eigen  yang  bersesuaian  dengan  nilai  eigen  adalah u =  [1  1….1] T
(Kolman,  2007).  Karena y adalah  vektor  eigen  yang  bersesuaian  dengan  ,
akibatnya u ortogonal dengan y . Sehingga
1 1 1 1 ... 1 0. 1 n n y y y y    
                      u y = Persamaan (4) dapat ditulis sebagai 1 1 1 1 1 0 . 0 n y bJ b y b  
                                       y = = 0 Karena A   y y , persamaan (4) menjadi
  2 ( ) ( ) = 0 . b a b k
      y y (5)
Persamaan (5) mengakibatkan
2 ( ) ( ) 0. b a b k        (6)
Persamaan  (6)  merupakan  persamaan  kuadrat  dengan  variabel µ ,  persamaan kuadrat ini dapat difaktorkan menggunakan rumus sebagai berikut :
2 ( ) ( ) 4( ) . 2 a b b a k b          Karena     2 4 t b a k b     sehingga 1 (( ) ). 2 a b t      
Selanjutnya teorema 3 digunakan untuk memperoleh bentuk spektrum pada graf  reguler  kuat  dengan  parameter (n,  k,  a,  b) .  Hasil  sebelumnya  diperoleh  tiga persamaan untuk nilai eigen dari matriks ketetanggaan graf reguler kuat yaitu
18                                                                                                       Mulyani, dkk.
0 k   (7)
( ) 2 a b t  
   (8)
( ) 2 a b t  
   (9)
dengan 2 ( ) 4( ). t b a k b    
Misalkan 0 m adalah multiplisitas dari nilai  eigen k , 1 m adalah multiplisitas dari nilai eigen   dan 2 m adalah multiplisitas dari nilai eigen   , maka multiplisitas dari  matriks  ketetanggaan  graf  reguler  kuat  adalah 0 1 2 m m m n    .  Karena multiplisitas 0 m k  adalah 1 (Biggs, 1993), maka 1 2 1. m m n    Salah satu sifat
matriks  ketetanggaan  adalah   0 ii A  ,  akibatnya ( ) 0. tr A  Menurut  Biggs
(1993),
1 ( ) n i i tr A     sehingga diperoleh 1 2 0. n i i k m m     
    
(10)
Substitusi persamaan (8) dan (9) ke persamaan (10), diperoleh
1 2 ( ) ( ) 0. (11)
2 2 a b t a b t k m m                        Kalikan  persamaan (11) dengan 2, diperoleh
    1 2 1 2 1 2 2 ( ) ( ) 0
( )( ) 2 . (12)
k m a b t m a b t m m a b k m m t              
Tambahkan ruas kiri dari persamaan (12)  dengan 1 1 m m  diperoleh 1 2 1 2 1 1 1 2 1 1 2 ( )( ) 2 ( )( ) 2 2 ( ) m m b a k m m m m t m m b a k m m m t              
1 2 1 1 2 ( )( ) 2 1 ( ) . (13) 2 m m b a k m m m t             
Sebelumnya diketahui bahwa 1 2 1. m m n    Substitusi 1 2 1 m m n    ke
persamaan (13) diperoleh
1 1 ( 1)( ) 2 ( 1) , (14) 2 n b a k m n t             sehingga
2 1 2 1 1 ( 1)( ) 2 ( 1) .
(15)
2 m n m n b a k m n t                      Substitusi 2 ( ) 4( ) t b a k b     ke persamaan (14) dan (15), diperoleh 1 2 2 2 1 ( 1)( ) 2 ( 1) 2 ( ) 4( ) 1 ( 1)( ) 2 ( 1) . 2 ( ) 4( ) n b a k m n b a k b
n b a k m n b a k b                   
         
    
Oleh karena itu, diperoleh spektrum graf reguler kuat
dengan 0 0 1 2 ( ) , spec G m m m       
       0 2 ( ) ( ) 4( ) 2 k a b b a k b    
      2 0 1 2 2 2 ( ) ( ) 4( ) 2
1
1 ( 1)( ) 2 ( 1) 2 ( ) 4( )
1 ( 1)( ) 2 ( 1) . 2 ( ) 4( )
a b b a k b m
n b a k m n b a k b n b a k m n b a k b                     
     
          
    

## 3.  KESIMPULAN DAN SARAN
Bentuk spektrum pada graf reguler kuat dengan parameter ( n , k , a , b ) adalah
20                                                                                                       Mulyani, dkk.
                              2 2 2 2 4 4 2 2
( ) , 1 2 1 2 1 1 1 1 2 2 4 4 1 a b b a k b a b b a k b
spec G n b a k n b a k n n b a k b b a k b k                                           
dengan n menyatakan banyak titik di G , k menyatakan derajat setiap titik di G, a menyatakan  banyaknya  ketetanggaan  bersama  untuk  setiap  dua  titik  yang bertetangga dan b menyatakan banyaknya ketetanggaan bersama untuk setiap dua titik yang tidak bertetangga di G .
Pada  artikel  ini  hanya  dibahas  mengenai  bentuk  spektrum  pada  graf reguler kuat.  Kajian  lanjutan  dari  spektrum  pada  graf reguler kuat  adalah menentukan  banyaknya spanning  tree atau  yang  disebut tree  number dari  graf regular kuat.

## DAFTAR PUSTAKA
Bapat, R B. (2010). Graphs Matrices . Hindustan Book , India.
Biggs  N.  (1993). Algebraic  Graph  Theory .  Second  Edition,  Cambridge Mathematical Library.
Chaudhary, N.S, Sada, N.L., and Phatak, B.D. (1986). A Note on The Property of an  Adjoint  of  the  Adjacency  Matrix  of  Strongly  Regular  Graph ,  Indian Journal. Pure Appl.Math. pp. 871-874.
Kolman  B.(2007). Elementary  Linear  Algebra  and  Its  Applications .  Ninth Edition. Published by Pearson.
Spektrum pada Graf Reguler Kuat                                                                    21