## KARAKTERISTIK NILAI EIGEN DARI MATRIKS LAPLACIAN
Siti Rahmah Nurshiami, Mutia Nur Estri, Noor Sofiyati Program Studi Matematika, Fakultas Sains dan Teknik Universitas Jenderal soedirman, Purwokerto E-mail : nurshiami@yahoo.co.id
ABSTRAK. Matriks  Laplacian  dari  suatu  graf  G  adalah  matriks  diagonal dikurangi  dengan  matriks  ketetanggaan.  Paper  ini  membahas  karakteristik  nilai eigen dari matriks Laplacian dan hubungan nilai eigen matriks Laplacian dengan nilai eigen matriks ketetanggaan dari graf reguler.
Kata kunci : Matriks Laplacian , Nilai Eigen, Nilai Eigen Laplacian , Graf Reguler
ABSTRACT . The Laplacian matrix of a graph G is a diagonal matrix minus the neighborhood  matrix.  This  paper  discusses    about  the  characteristics  of  the Laplacian  matrix  eigenvalues  and  the  relationships  of  Laplacian  matrix eigenvalues with neighborhood matrix eigenvalues of regular graphs.
Keywords: Laplacian matrix, Eigen Values, Eigen Value Laplacian, Regular Graph

## 1. Pendahuluan
Sebuah  graf  dapat  direpresentasikan  ke  dalam  matriks Laplacian .  Jika D(G) merupakan  matriks  diagonal  dengan  entri  pada  diagonal  utamanya merupakan  derajat  dari  titik v i pada  graf G, dan A(G) merupakan  matriks ketetanggaan  dari  graf G, maka  matriks Laplacian 𝐿 ( G )    merupakan      matriks bujur  sangkar    yang    diperoleh    dari    matriks  diagonal  dikurangi  matriks ketetanggaan.  Nilai  eigen  dari  matriks Laplacian dapat  diperoleh  dengan menggunakan  polinomial  karakteristik.  Pada  tahun  1973,  Fiedler  mempelajari salah  satu  karakteristik  nilai  eigen  dari  matriks Laplacian ,  yaitu  nilai  eigen terkecil  kedua.  Sementara  itu,  Juhasz(1982)  mempelajari  nilai  eigen  dari  graf reguler  beserta  multiplisitasnya,  yang  dikenal  dengan  spektrum  graf.  Paper  ini mengkaji karakteristik lain nilai eigen dari matriks Laplacian.

## JMP : Volume 3 Nomor 1, Juni 2011

## 2. Matriks Laplacian
Suatu  graf  dikatakan  reguler  berderajat r ( r -reguler)  jika  untuk  setiap titiknya mempunyai derajat r. Misalkan G = ( V , E ) adalah graf sederhana dengan n titik dan m sisi. Matriks ketetanggaan dari graf G adalah matriks 𝐴 𝑛×𝑛 = 𝐴(𝐺) dengan entri
𝑎 𝑖𝑗 =   { 1, jika (𝑣 𝑖 , 𝑣 𝑗 ) ∈ 𝐸(𝐺) 0, jika (𝑣 𝑖 , 𝑣 𝑗 ) ∉ 𝐸(𝐺).
Matriks insidensi N dari graf berarah G adalah matriks berukuran n × m dengan entri :
N= [ n ij ] = { +1, jika titik 𝑣 𝑖 merupakan titik awal dari sisi 𝑒 𝑗 = (𝑣 𝑖 , 𝑣 𝑘 ) −1, jika titik 𝑣 𝑘 merupakan titik akhir dari sisi 𝑒 𝑗 = (𝑣 𝑖 , 𝑣 𝑘 ) 0, lainnya.
Matriks Laplacian dari  graf  berarah  atau  tak  berarah G adalah ℒ ( G )  = D(G)  –  A(G) dengan D(G) matriks  diagonal  dari  graf G dan A(G) matriks ketetanggaan dari  graf G. Matriks D n×  n = [𝑑 𝑖𝑗 ] merupakan matriks diagonal dari graf G dengan entri
𝑑 𝑖𝑗 =   { 𝑑𝑒𝑟 (𝑣 𝑖 ),  jika 𝑣 𝑖 = 𝑣 𝑗 0 , jika 𝑣 𝑖 ≠   𝑣 𝑗
Dengan demikian, entri matriks Laplacian ℒ ( G ) adalah
ℒ 𝑛×𝑛 = [𝑙 𝑖𝑗 ] = { −1, jika (𝑣 𝑖 , 𝑣 𝑗 ) ∈ 𝐸(𝐺) 𝑑𝑒𝑟(𝑣 𝑖 ), jika 𝑣 𝑖 = 𝑣 𝑗 0, jika (𝑣 𝑖 , 𝑣 𝑗 ) ∉ 𝐸(𝐺).
Karakteristik  dari  matriks Laplacian untuk  sembarang  graf  G  diberikan oleh proposisi berikut;
Proposisi 1 [9]
Karakteristik matriks Laplacian dari graf G, ℒ(𝐺) adalah sebagai berikut :
1. Jumlah entri setiap baris pada matriks Laplacian ℒ ( G ) sama dengan nol.
2. Matriks ℒ ( G )  adalah  matriks  berukuran n × n dimana n menyatakan banyaknya titik dari graf G.
3. Misalkan N merupakan  matriks  insidensi  dari  graf  berarah G dengan n titik. Maka matriks Laplacian ℒ(𝐺) dapat dinyatakan dengan ℒ = NN t
S. Rahmah Nurshiami, dkk.                                                                                                  34
4. Perubahan  pelabelan  sisi  pada  graf G tidak  berpengaruh  pada  matriks Laplacian ℒ ( G ).
5. Matriks ℒ ( G ) merupakan matriks singular.
6. Matriks Laplacian ℒ ( G )  merupakan  matriks  simetris  dan  semidefinit positif.

## 3. Nilai Eigen Matriks Laplacian
Misalkan G adalah  graf  sederhana  dengan n titik  dan  matriks ketetanggaan dari G adalah A ( G ). Polinomial karakteristik dari graf G dinotasikan dengan 𝜒(𝐺;  ) ,  dinyatakan sebagai
𝜒(𝐺;  ) = det (  𝐼 𝑛  A(G)) =  𝑛 + 𝐶 1  𝑛−1 + 𝐶 2  𝑛−2 + ⋯ + 𝐶 𝑛
dengan  adalah nilai eigen dari matriks ketetanggaan A ( G ). Karena A ( G ) = [ 𝑎 𝑖𝑗 ] =  [ 𝑎 𝑗𝑖 ] ,  sehingga  matriks A ( G )  adalah  matriks  riil  dan  simetri.  Akibatnya  nilai eigen  adalah  bilangan  riil,  dan  multiplisitas  dari  adalah  dimensi  dari  ruang eigen yang bersesuaian dengan nilai eigen  .
Karakteristik  dari  suatu  graf G reguler  berderajat r ,  diberikan  dalam proposisi 2 berikut;
Proposisi 2[2]
Misalkan G adalah graf r -reguler dengan n titik. Maka:
i. r adalah nilai eigen dari G ;
ii. Jika G adalah graf terhubung, maka multiplisitas r adalah 1;
iii. Untuk setiap nilai eigen  dari G , berlaku |𝜆| ≤ 𝑟 .
Selanjutnya,  karakteristik  dari  nilai  eigen  matriks Laplacian ℒ ( G ) diberikan dalam proposisi 3 berikut;
Proposisi 3
Jika 0 1 1 n        merupakan nilai eigen dari matriks Laplacian ℒ ( G ), maka i. 0  = 0, dengan vektor eigen [1,1,…,1];
ii. Jika G graf terhubung, 1  > 0;
iii. Jika G graf regular berderajat k , maka p p k     , dengan p = 0, 1,2,…,n-
1 dengan p  adalah  nilai  eigen  dari  matriks  ketetanggaan  graf G dengan
0 1 1 ... n        .
Bukti :
i. Misalkan ℒ 𝑛×𝑛 = [𝑙 𝑖𝑗 ] adalah  matriks Laplacian dari G. Karena 𝜇 0 nilai eigen  dari  matriks Laplacian ℒ(𝐺) maka, ℒ x  = 𝝁 𝟎 x, dengan 𝑥 = [𝑥 1 𝑥 2 … 𝑥 𝑛 ] 𝑡 = [1 1 … 1] 𝑡 vektor  eigen  yang  bersesuaian dengan 𝝁 𝟎 .
Perhatikan bahwa
ℒ x = 𝝁 𝟎 x ⟺ 11 12 1 21 22 2 1 2 1 1 1 n n n n nn l l l l l l l l l    
                    = 0 1 1 1             
⟺ 1 1 2 1 1 n j j n j j n nj j l l l       
                     = 0 0 0 .               
Karena  jumlah  entri  dari  setiap  baris  pada  matriks Laplacian sama  dengan nol,  maka
1 n ij j l   = 0, dengan i = 1, 2, ..., n .  Akibatnya 0  = 0.
ii. Misalkan p  dengan p =  0,  1,  …, n- 1  merupakan  nilai  eigen  dari ℒ .
Karena  matriks Laplacian ℒ ( G )  merupakan  matriks  semidefinit  positif, maka 0 p   .  Dari (i) vektor eigen yang bersesuaian dengan 0  = 0 adalah vektor 𝑥 = [1 1 … 1] 𝑡 . Sehingga ruang eigen dari ℒ yang bersesuaian
S. Rahmah Nurshiami, dkk.                                                                                                  36
dengan nilai eigen 0  = 0 dapat ditulis 𝑅𝐸 (0)
= {𝛼[1 1 … 1] 𝑡 |𝛼 ≠ 0, 𝛼 ∈ 𝑅}.
Selanjutnya  dapat  dibuktikan  bahwa     1,1,...,1 t basis  dari 𝑅𝐸 (0).  Jadi,
multiplisitas  dari    nilai    eigen 0 0   adalah  1.  Karena 0 p   untuk p = 0,1,…, n- 1 dan 0  = 0  maka 1 0.  
iii. Misalkan 𝜆 merupakan nilai eigen dari matriks ketetanggaan A ( G ), sehingga
p p p A   x x dengan 𝐱 𝑝 ∈ ℝ 𝑛 , 𝐱 𝑝 ≠ 0, 𝑝 = 0,1,2, … . , 𝑛 − 1 .
Karena 𝜇 merupakan  nilai eigen dari  matriks Laplacian ℒ(𝐺) sehingga ℒ p p p   x x
dimana 𝐱 𝑝 adalah vektor eigen yang bersesuaian dengan nilai eigen ke p dan 𝐱 𝑝 ≠ 0.
Karena 𝐷 ( G ) merupakan matriks diagonal dari graf G reguler berderajat k sehingga menurut proposisi 1(i), nilai eigennya adalah k . Akibatnya
p p D k  x x .
Dari  definisi  matriks Laplacian diperoleh ℒ𝐱 𝑝 = D 𝐱 𝑝 –  A 𝐱 𝑝 untuk  suatu 𝐱 𝑝 ∈ ℝ 𝑛 . Akibatnya 𝜇 𝑝 𝐱 𝑝 = 𝑘𝐱 𝑝 − λ 𝑝 𝐱 𝑝.
Sehingga
𝜇 𝑝 [ 𝑥 1 𝑥 2 ⋮ 𝑥 𝑛 ] = 𝑘 [ 𝑥 1 𝑥 2 ⋮ 𝑥 𝑛 ] − λ 𝑝 [ 𝑥 1 𝑥 2 ⋮ 𝑥 𝑛 ] ⟺         [ 𝜇 𝑝 𝑥 1 𝜇 𝑝 𝑥 2 ⋮ 𝜇 𝑝 𝑥 𝑛 ]   = [ 𝑘𝑥 1 − 𝜆 𝑝 𝑥 1 𝑘𝑥 1 − 𝜆 𝑝 𝑥 2 ⋮ 𝑘𝑥 1 − 𝜆 𝑝 𝑥 𝑛 ] ⟺         [ 𝜇 𝑝 𝑥 1 𝜇 𝑝 𝑥 2 ⋮ 𝜇 𝑝 𝑥 𝑛 ] =   (𝑘 − 𝜆 𝑝 ) [ 𝑥 1 𝑥 2 ⋮ 𝑥 𝑛 ] ⟺           𝜇 𝑝 𝐱 𝑝 =    (𝑘 − 𝜆 𝑝 )𝐱 𝑝.
Sehingga 𝜇 𝑝 = 𝑘 − λ 𝑝 , 𝑝 = 0,1,2, … . , 𝑛 − 1.

## 4. Kesimpulan
Berdasarkan  pembahasan  mengenai  matriks Laplacian ,  dapat  disimpulkan bahwa  jika 0 1 1 n        merupakan  nilai  eigen  dari  matriks Laplacian ℒ ( G ), maka nilai eigen yang pertama adalah nol dengan multiplisitasnya 1. Lebih dari  itu,  jika G graf  terhubung  maka  nilai  eigen  kedua  lebih  besar  dari  0. Sementara  jika G graf reguler berderajat k , maka  jumlah dari nilai  eigen  matriks Laplacian dan nilai eigen matriks ketetanggaan sama dengan k .

## DAFTAR PUSTAKA
[1]    Anton,  Howard.  2000. Dasar-dasar  Aljabar  Linear .  Edisi  7,  Jilid  1. Interaksara,
[2]  Biggs, Norman. 1993. Algebraic Graph Theory . Second Edition. Cambridge University Press, New York.
[3]    Fiedler,  Miroslav.  1973. Algebraic  Connectivity  of  Graphs .  Czechoslovak Mathematical Journal vol. 23. Praha.
[4]    Jacob,  Bill.  1990. Linear  Algebra .  W.  H.  Freeman  and  Company,  New York.
[5]    Juhasz,  F.  1982.  On  The  Spectrum  of  a  Random  Graph. Colloq.Math.Soc.J.Bolyai 25. North-Holland,Amsterdam.
[6]    Kolman,  Bernard.  2004. Elemetary  Linear  Algebra .  8 th Edition.  Pearson Education, New Jersey.
[7]    Leon,  Steven.  2001. Aljabar  Linier  dan  Aplikasinya  Edisi  ke- 5.  Erlangga, Jakarta.
[8]    Wilson,  Robin  J.,  and  John  J.  Watkins.  1990. Graph    An  Introductory Approach:  A First Course in Discrete Mathematics. John Willey & Sons, Inc, New York.
[9]    Yacoub,  Wafa.2004. A  Thesis  :  Eigenvalues  of  Graphs  :Algebraic Connectivity  and  Acyclic  Matrices. The  faculty  of  The  Department  of Mathematics. San Jose State University, San Jose States.
S. Rahmah Nurshiami, dkk.                                                                                                  38