J. Math. and Its Appl. ISSN: 1829-605X Vol. 8, No. 2, November 2011, 33–42

## SIFAT-SIFAT GRAF DALAM ALJABAR LINIER DAN PENGGUNAANNYA DALAM SAGE

## Soleha
Jurusan Matematika, FMIPA ITS Surabaya seha 07@matematika.its.ac.id

## Abstrak
Pada paper ini dibahas penggunaan teknik aljabar linier untuk mempe- lajari graf. Sehingga dapat membentuk teorema mengenai graf. Dari suatu graf sederhana berhingga G dapat dibentuk matriks ketetanggaan A yang mencerminkan hubungan antar simpul dari graf tersebut. Selain itu, juga dapat dibentuk matriks ketetanggaan antara sisi-sisi dari graf yaitu A L , ma- triks keterkaitan atara simpul dan sisi yaitu X . Dari matriks ketetanggaan tersebut, dilakukan analisis terhadap sifat-sifat yang ada pada graf. Pada paper ini dikaji sifat graf terkait nilai eigen dari graf teratur, graf Petersen dan graf garis beserta sifat-sifat yang lain. Selain itu, dalam paper ini akan dikaji keterkaitan antara nilai eigen matriks Laplacian (matriks Kirchhoff) dan matriks ketetanggaan dalam suatu graf G . Selanjutnya, akan dberikan proses pembuktian dari sifat-sifat tersebut terhadap beberapa contoh graf menggunakan Sage. Katakunci: Matriks ketetanggaan, Graf teratur, Graf Petersen, Graf ga- ris, Matriks laplacian, Sage.

## 1. Pendahuluan
Teori graf merupakan salah satu bagian dalam ilmu matematika. Sebuah graf G terdiri atas dua himpunan yaitu himpunan berhingga tak kosong V ( G ) yang elemen-elemennya disebut simpul dan himpunan berhingga (mungkin kosong)
E ( G ) yang elemen-elemennnya disebut sisi. Apabila sisi v i , v j ada di E ( G ), ma- ka dapat dikatakan bahwa v i dan v j saling bertetangga. Simpul v i dan v j dapat dikatakan bertetangga apabila terdapat sisi yang menghubungkan v i dan v j serta sisi tersebut terkait dengan v i dan v j [1]. Aplikasi cabang ilmu lain dari ma- tematika dalam Teori Graf antara lain Aljabar Linear. Dari teori aljabar linier tersebut dapat dibentuk suatu matriks ketetanggaan A dari suatu graf. Matriks ketetanggaan A merupakan matriks yang merepresentasikan ketetanggaan dari simpul-simpul yang terdapat pada suatu graf. Selain itu, dapat juga dibentuk matriks ketetanggaan antara sisi-sisi dari graf yaitu A L , matriks keterkaitan atara simpul dan sisi yaitu X . Jika pada graf diberikan suatu orientasi, dapat diben- tuk matriks keterkaitan antara simpul dan sisi dengan orientasi yang dikatakan sebagai matriks D . Lebih dari itu, dapat dibentuk matriks Laplacian (Kirchhoff) Q yang dibentuk dari A dan D . Salah satu permasalahan utama dari teori graf aljabar adalah menentukan sifat-sifat graf yang direfleksikan dari teknik aljabar linier menggunakan matriks-matriks di atas.
Pada paper ini akan dikaji beberapa lemma, proposisi dan teorema dalam [2] terkait sifat-sifat tersebut dan dalama paper ini penulis menyertakan pembuktian dari teorema terhadap beberapa contoh graf menggunakan Sage.

## 2. Sage
System for Algebra and Geometry Experimentation atau yang umumnya disingkat Sage adalah perangkat lunak dengan keunggulan dalam menyelesaikan permasa- lahan berbagai aspek dalam matematika, termasuk aljabar linier, kalkulus, teori graf, teori bilangan dan analisis numerik [3]. Sage juga dapat disebut sagemath. Sage versi pertama dipublikasikan pada 24 Februari 2005 sebagai perangkat lunak bebas di bawah lisensi GNU General Public dengan tujuan awal untuk menyaingi beberapa perangkat lunak berbayar sejenis yang sudah ada yaitu Mathematica, Maple dan Matlab. Pencipta dari Sage adalah William Stein, seorang akademisi matematika dari University of Washington, Amerika Serikat. Sage menggunakan bahasa pemrograman Phyton. Pada tahun 2007, Sage memenangkan pengharga- an terbaik dalam Les Trophess du Libra, suatu ajang penghargaan internasional untuk perangkat lunak bebas [4]. Saat ini, Sage digunakan oleh para akademisi di banyak negara yang bekerja di bidang aljabar dan graf, baik aljabar abstrak ma- upun aljabar linear, misalnya dalam [5], [6] dan [7]. Sebagai perangkat lunak ma- tematika, Sage mempunyai banyak keunggulan yaitu dapat diunduh secara bebas, menyediakan banyak paket matematika, dan Sage dapat digunakan menyelesaikan suatu persoalan dalam aljabar linier dan persoalan matematika lainnya. Selain itu, Sage juga dapat menjadi wadah untuk menuliskan teks modul perkuliahan yang terintegrasi dengan LaTeX. Teks modul tersebut selanjutnya dapat diung-
gah ke dalam suatu jejaring. Beberapa paket matematika yang termuat dalam Sage antara lain:
Aljabar : GAP, M axima, Singular
Aljabar Geometri : Singular Geometri Aritmatika : P ARI/GP, N T L, mwrank, ecm
Kalkulus : M axima, SymP y, GiN aCKombinatorikSymmetrica,
AljabarLinear : AT LAS, BLAS, LAP ACK, N umP y, LinBox, IM L, GSL
T eori Graf : N etworkX
Komputasi N umerik : GSL, SciP y, N umP y, AT LAS

## 3. Graf Garis dan Matriks keterkaitan
Misalkan G suatu graf sederhana yaitu graf yang tidak memuat loop dan sisi ganda, dengan label dari sisi nya EG = ( e 1 , e 2 , . . . e m ) dan simpulnya V G = ( v 1 , v 2 , . . . v n ). Matriks ketetanggaan suatu graf G adalah suatu matriks A = A ( G ) n × n dimana
a ij = 1 , jika v i bertetangga dengan v j ; 0 , yang lain .
Berdasarkan definisi di atas, A adalah suatu matriks simetri dan setiap unsur pada diagonal utama adalah 0. Nilai eigen graf G adalah nilai eigen dari matriks A . Jika graf G dengan n simpul memiliki s simpul yang memiliki himpunan simpul ketetanggaan yang sama, maka terdapat s baris dalam matriks A yang memiliki elemen yang sama. Akibatnya, matriks tersebut singular sehingga dapat dikatakan A memiliki nilai eigen 0. Pernyataan di atas dapat dirangkum dalam proposisi berikut ini.
Proposisi 3.1 Jika graf G dengan n simpul memiliki s simpul yang memiliki himpunan simpul ketetanggaan yang sama, maka G memiliki nilai eigen 0.
Selanjutnya, pandang suatu graf teratur. Untuk mencari nilai eigen dari graf teratur berderajat k dapat digunakan proposisi berikut:
Proposisi 3.2 Misalkan G graf teratur berderajat k . Maka:
1. k merupakan salah satu nilai eigen dari G .
2. Jika G terhubung, maka multiplisitas aljabar dari k adalah 1
3. Untuk setiap nilai eigen λ dari graf G , didapatkan | λ | ≤ k
Pengembangan dari Proposisi 3.2 di atas, didapatkan jika G tidak terhubung, maka multiplisitas aljabar dari k adalah banyaknya komponen terhubung dari G [8].
Sebagai contoh, diberikan graf lengkap dengan empat simpul G = K 4 . Graf K 4 adalah graf terhubung teratur berderajat tiga.
Gambar 1: Graf K 4
Dari Proposisi 3.2 di atas, didapat salah satu nilai eigen dari K 4 adalah 3, dan nilai mutlak dari nilai eigen yang lain ≤ 3. Berikut diberikan pembuktiannya menggunakan Sage.
Gambar 2: Nilai eigen dari K 4
Terlihat bahwa nilai eigen dari K 4 adalah 3 dan -1, dimana | − 1 | = 1 ≤ 3, dan multiplisitas aljabar dari k = 3 adalah satu.
Selain dapat dibentuk matriks ketetanggaan, dari suatu graf sederhana G dapat juga dibentuk graf garis L ( G ) dengan pengaturan setiap sisi di G adalah simpul di L ( G ), dan untuk setiap 2 simpul yang terkait di sisi e a dan sisi yang lain misal e b , maka e a dan e b bertetangga di L ( G ). Dari L ( G ) dapat juga dibentuk matriks ketetanggaannya yaitu A L berukuran m × m dimana
( A L ) ij = 1 , jika e i bertetangga dengan e j ; 0 , yang lain .
Berikut diberikan gambar graf garis dari K 4 .
Gambar 3: Graf garis dari K 4
Selanjutnya, didefinisikan matriks X n × m yang merepresentasikan keterkaitan antara v i dan e i yaitu
X ij = 1 , jika v i dan e i terkait 0 , jika v i dan e i tidak terkait .
Dari beberapa definisi di atas, dapat digunakan untuk membuktikan lemma berikut
Lemma 3.3 Didefinisikan G , A , L ( G ) , A L dan X seperti di atas. Maka:
1. X T X = A L + 2 I m
2. Jika G teratur berderajat k , maka XX T = A + kI n .
Berikut diberikan pembuktian Lemma 3.3 di atas untuk graf K 4 dengan meng- gunakan Sage, dengan k = 3.
Gambar 4: X T X = A L + 2 I 6
Gambar 5: XX T = A + 3 I 4
Lemma 3.4 Jika λ adalah nilai eigen dari A L , maka λ ≥ − 2 .
Bukti Misal µ nilai eigen dari X T X , maka
X T X.z = µ.z (1)
dengan z vektor eigen yang bersesuaian dengan µ . Kalikan persamaan (1) dengan z T dari kiri, didapat
z T X T X.z = µ.z T z (2)
Di sisi lain, k Xz k 2 = < Xz, Xz > = ( Xz ) T Xz = z T X T Xz . Karena k Xz k 2 ≥ 0, dan z T z ≥ 0, maka µ ≥ 0. Pandang persamaan berikut
X T X.z = µ.z ( A L + 2 I m ) .z = µ.z
A L .z + 2 I m .z = µ.z A L .z = − 2 I m .z + µ.z A L .z = ( µ − 2) I m .z A L .z = ( µ − 2) .z A L .z = λ.z
Karena µ ≥ 0, maka nilai eigen dari A L yaitu λ = µ − 2 ≥ − 2.
Berikut diberikan pembuktian Lemma 3.4 di atas untuk graf Petersen meng- gunakan Sage beserta gambarnya.
Gambar 6: Nilai eigen dari graf garis dari graf
Petersen
Gambar 7: Graf Petersen
Terlihat bahwa nilai eigen dari L ( G 2) dengan G 2 adalah graf Petersen adalah lebih besar sama dengan -2.
Berikut ini diberikan suatu teorema terkait polinomial karakteristik graf garis.
Teorema 3.5 Jika G graf k teratur dengan n simpul dan m = 1 2 nk sisi, maka
C A L ( λ ) = ( λ + 2) m − n C A ( λ + 2 − k ) .
Bukti Didefinisikan matriks blok sebagai berikut :
R = λI n − X 0 I m , S = I n X X t λI m . maka RS = λI n − XX t 0 X t λI m , SR = λI n 0 λX t I m − X t X .
Karena det( RS ) = det( SR ), maka
λ m det( λI n − XX t ) = λ n det( λI m − X t X ) .
Menggunakan Lemma 3.3 dan persamaan di atas diperoleh
C A L ( λ ) = det( λI m − A L ) = det(( λ + 2) I m − X t X ) = ( λ + 2) m − n det(( λ + 2) I n − XX t ) = ( λ + 2) m − n det(( λ + 2 − k ) I n − A ) = ( λ + 2) m − n C A ( λ + 2 − k ) .

## 4. Matriks Laplacian
Diperkenalkan untuk setiap e α = { v γ , v τ } dari G , kemudian dipilih salah satu dari v γ , v τ menjadi ujung positif dari e α dan yang lain ujung negatif. Prosedur ini dapat dikatakan sebuah orientasi terhadap G . Matriks keterkaitan D dari graf G dengan orientasi adalah matriks berukuran n × m ( d ij ) yang didefinisikan dengan
d ij =    1 , jika v i adalah ujung positif dari e j − 1 , jika v j adalah ujung negatif dari e j ; 0 , yang lain .
Teorema 4.1 Jika D matriks keterkaitan dari graf G dengan orientasi maka Q = DD t = ∆ − A , dengan A matriks ketetanggaan dan ∆ matriks diagonal yang elemen diagonalnya adalah derajat dari v i (1 ≤ i ≤ n ).
Dari Teorema 4.1 di atas, dapat didefinisikan Q = ( Q i,j ) n × n dalam bentuk yang baru, yaitu:
q ij =    derajat v i , untuk i = j − 1 , untuk i 6 = j dan v i bertetangga dengan v j ; 0 , yang lain .
Teorema 4.2 Diberikan graf G dan matriks Laplacian Q dengan nilai eigen µ 0 ≤ µ 1 ≤ · · · ≤ µ n − 1 :
1. µ 0 = 0 dengan vektor eigen x = [1 , 1 , ...., 1]
2. Jika G terhubung, maka µ 1 > 0
3. Jika G graf teratur berderajat k , maka µ i = k − λ i , dengan λ i adalah nilai eigen dari G .
Bukti 1. Dari definisi Q = DD t , maka Q adalah matriks semi definite positif ( ∀ i, µ i ≥ 0). Akan dibuktikan bahwa Q memuat 0 sebagai nilai eigen, sehingga µ 0 = 0.
Misal Q =      q 11 q 12 · · · q 1 n q 21 q 22 · · · q 2 n .. . .. . .. . .. . q n 1 q n 2 · · · q nn      dengan Σ n j =1 Σ n i =1 q ij = 0.
Pandang ¯ x =
     x 1 x 2 .. . x n      yang memenuhi Q × ¯ x = µ × ¯ x , dengan ¯ x vektor eigen
dari Q yang bersesuaian dengan µ . Akan dibuktikan terdapat ¯ x sehingga µ = 0.
Pilih ¯ x =      1 1 .. . 1      . Karena Σ n j =1 Σ n i =1 q ij = 0, maka
Q × ¯ x =      q 11 q 12 · · · q 1 n q 21 q 22 · · · q 2 n .. . .. . .. . .. . q n 1 q n 2 · · · q nn      ×      1 1 .. . 1      =      0 0 .. . 0      = 0 ×      1 1 .. . 1      = µ × ¯ x .
Sehingga µ = 0 adalah nilai eigen dari Q dan µ = 0 = µ 0
2. Akan dibuktikan jika G terhubung, maka µ 1 > 0. Karena dimensi kernel Q = dim ( V G ) = n - dim rank = n − ( n − 1) = 1, dan dim kernel = multiplisitas aljabar dari ( µ = 0). Maka multiplisitas aljabar dari ( µ = 0) adalah 1. Oleh karena multiplisitas aljabar dari ( µ = 0) adalah 1 dan karena µ 0 = 0, maka µ 1 > 0.
3. Pandang
DD t .z = µ i .z ( kI − A ) .z = µ i .z kI.z − A.z = µ i .z A.z = kI.z − µ i .z A.z = ( k − µ i ) .I.z A.z = ( k − µ i ) .z A.z = λ i .z.
Berikut diberikan pembuktian Teorema 4.2 di atas untuk graf Petersen mengguna- kan Sage .
Gambar 8: Ruang eigen dari matriks Laplacian dari graf Petersen
Dari hasil di atas diperoleh bahwa nlai eigen minimal dari matriks Laplacian Q dari graf Petersen ( G 2) adalah µ 0 = 0 dengan vektor eigen x = [1 , 1 , ...., 1]. Selanjutnya, µ 1 = 1 > 0. Faktanya, graf Petersen adalah graf teratur berderajat tiga sehingga didapat: µ 0 = 3 − 3 = 0, µ 1 = 3 − 1 = − 2, dan µ 2 = 3 − ( − 2) = 5 dengan 3 = λ 0 , 1 = λ 1 , − 2 = λ 2 , λ 0 , λ 1 dan λ 2 adalah nilai eigen dari G 2.

## 5. Kesimpulan
Teknik aljabar linier dapat digunakan untuk menyelidiki teorema mengenai graf. Teorema-teorema tersebut menyatakan bahwa salah satu nilai eigen dari sebarang graf teratur berderajat k adalah k , dan batas bawah dari nilai eigen sebarang graf garis adalah -2. Teorema yang lain menyatakan bahwa polinomial karakteristik graf garis dari graf G , dapat dibentuk dari polinomial karakteristik graf G . Teore- ma terakhir menentukan nilai eigen dari mtriks Laplacian Q dari sebarang graf G . Pembuktian dari teorema-teorema tersebut djuga dapat ditunjukkan mengguna- kan Sage, untuk beberapa contoh graf tertentu

## Pustaka
[1] Budayasa , Teori Graph dan Aplikasinya , Surabaya: Unesa University Press, 2007.
[2] Godsil, C. Royle, G. Algebraic Graph Theory , Springer, 2001.
[3] Sage , http://sagemath.org, Free, public notebook server at ht- tp://sagenb.org.
[4] Science Daily , Free Software Brings Affordability, Transparency To Mathe- matics , Desember 7 2007.
[5] Beezer, A. R. , Sage for Linear Algebra: A Supplement to A First Course in Linear Algebra , GNU Free Documentation License, 2011.
[6] Whieldon, Gwyn , Math 440: Laboratory 1, Introduction to Abstract Alge- bra with SAGE , A lecturer note:Hood College.
[7] Stein, W. , Exact Linear Algebra for SAGE , MSRI Workshop, 2006.
[8] Beezer, R , An Introduction to Algebraic Graph Theory , Mathematics De- partment Seminar Pasicic University, 2009.