KARAKTERISASI ALJABAR PADA GRAF BIPARTIT
Soleha, Dian W. Setyawati Institut Teknologi Sepuluh Nopember, Surabaya ABSTRAK. Pada artikel ini dibahas penggunaan teknik aljabar linier untuk mempelajari graf khususnya graf Bipartit. Dari suatu graf Bipartit dapat dibentuk matriks ketetanggaan dan matriks keterkaitan . Dari matriks dan tersebut dapat diperoleh karakterisasi graf bipartite khususnya vector eigen, nilai eigen, multiplisitas dan similaritas. Selanjutnya, akan dberikan proses pembuktian dari sifat-sifat tersebut terhadap beberapa contoh graf bipartite menggunakan Sage. Keywords: Matriks ketetanggaan, Matriks keterkaitan, Graf bipartit, Sage
1. PENDAHULUAN Suatu graf didefinisikan sebagai tiga himpunan berurutan ( ( ) ( ) ) dengan ( ) himpunan tak kosong dari , ( ) adalah himpunan sisi dari (boleh kosong) dan adalah pengaitan setiap sisi di ( ) dengan dua simpul di ( ). Jika ( ) , dikatakan berkaitan dengan dan dan dan dikatakan bertetangga. Banyaknya tetangga dari suatu simpul dikatakan derajat dari simpul Graf sederhana adalah suatu graf dimana ( ) untuk setiap ( ) dan untuk setiap ( ) berlaku ( ) ( ) Salvatore [1]. Dengan kata lain, graf sederhana adalah graf dengan yang tidak memuat sisi yang menghubungkan suatu simpul dengan dirinya sendiri dan tidak memuat sisi yang menghubungkan dua simpul yang tepat sama. Graf teratur adalah graf dengan setiap simpulnya mempunyai derajat yang sama. Suatu graf sederhana disebut sebagai graf bipartit jika himpunan simpulnya dapat dipartisi menjadi dua bagian dan sedemikian setiap sisi mempunyai satu ujung di dan satu ujung di . Graf bipartit lengkap adalah graf bipartit dengan setiap simpul di bertetangga dengan setiap simpul di . Dengan sifatnya yang khusus, graf bipartit mempunyai banyak keistimewaan. Graf bipartit dapat diaplikasikan di berbagai kasus seperti dalam permainan catur, pengenalan wajah, pengenalan musik, pencocokkan himpunan, dsb. Banyak hal tak terduga dan berguna yang dihasilkan dengan munghubungkan dua bagian dari matematika yang tampak tidak berelasi yaitu graf teori dan aljabar. Sifat aljabar linier dan metode serta hasil yang diperoleh dapat diterjemahkan ke sifat-sifat graf sehingga diperoleh kesimpulan mengenai teorema graf. Terdapat beberapa matriks yang berasosiasi dengan suatu graf yaitu matriks ketetanggaan, matriks keterkaitan dan matriks Laplacian. Dalam artikel ini akan dibahas sifat-sifat aljabar linier khususnya nilai eigen, spektrum, interlacing dan similaritas yang dihasilkan pada graf bipartit, graf garis bipartit dan pewarnaan graf bipartit. Penulis menyertakan hasil dari teorema terhadap beberapa contoh graf menggunakan Sage.
18
Karakterisasi aljabar pada graf bipartit
2. TINJAUAN PUSTAKA 2.1 Spektrum dari Graf Dari hubungan ketetanggaan antar simpul pada graf dapat digambarkan dalam bentuk matriks ketetanggaan, seperti yang didefinisikan berikut: Definisi 2.1 [2] Matriks ketetanggaan dari berukuran n x n dengan didapatkan dari
graf
adalah matriks
( )
{ Dari definisi di atas dapat disimpulkan bahwa matriks merupakan matriks simetris real dan nilai diagonal utama dari matriks adalah nol. Misalkan adalah nilai eigen dari . Karena merupakan matriks simetris real diperoleh bahwa bernilai real dan multiplisitas sebagai akar dari persamaan det ( ) , sama dengan dimensi dari vektor eigen yang bersesuaian dengan Sedangkan hubungan keterkaitan antara simpul dan sisi pada graf dapat digambarkan dalam bentuk matriks ketetanggaan, seperti yang didefinisikan berikut: Definisi 2.2 [2] Matriks keterkaitan dari berukuran n x m dengan didapatkan dari
graf
adalah matriks
( )
{ Dalam graf berarah, Definisi di atas daat diperluas sebagai berikut Definisi 2.3 [2] Matriks keterkaitan dari graf x m dengan didapatkan dari
adalah matriks
( ) berukuran n
{
Dari matriks ketetanggaan dapat didefinisikan spektrum dari graf. Berikut ini merupakan definisi spektrum dari graf. Dua buah matriks dapat ditelusuri keterkaitannya yaitu ada sifat similaritas. Berikut diberikan definisi similaritas dua buah matriks Definisi 2.4 [2] Matriks
dikatakan similar jika terdapat matriks
Selanjutnya diberikan teotema terkait matriks simetri Teorema 2.1[3] Misalkan matriks simetri yang dipartisi menjadi blok sedemikian hingga matriks persegi untuk setiap . Misalkan ( ) matriks dengan adalah rata-rata jumlahan baris dari . Misalkan dan masing-masing nilai eigen dari dan . Maka
2.2 Graf Bipartit Jika kita tinjau matriks ketetanggan dari graf bipartit, dapat dihasilkan lemma berikut Seminar Nasional Matematika 2014
19
Prosiding
Karakterisasi aljabar pada graf bipartit
Lemma 2.1 [4] Graf bipartit mempunyai matriks ketetanggaan [
]
Contoh: Berikut diberikan plot gambar Graf Lengkap Bipartit [5]
menggunakan SAGE
Gambar 1. Graf Lengkap Bipartit
Dari graf bipartit di atas, diperoleh matriks ketetanggaannya
[
]
Pewarnaan pada suatu graf adalah pemetaan dari ( ) ke himpunan berhingga warna sedemikian hingga tidak ada simpul bertetangga yang dipetakan ke warna yang sama. Nilai terkecil dari sedemikian dapat diwarnai sebanyak warna, disebut bilangan kromatik dari dan dinotasikan dengan . Berikut diberikan Lemma mengenai bilangan kromatik graf bipartit. Lemma 2.2 [6] Graf bipartit adalah graf dengan Suatu graf bipartit semiteratur adalah graf bipartit dengan . Dengan kata lain, graf bipartit semiteratur adalah graf bipartit dengan seluruh simpul dengan warna yang sama mempunyai derajat yang sama. Contoh yang paling mudah adalah graf bipartit lengkap .
Gambar 2. Graf Lengkap Bipartit
Seminar Nasional Matematika 2014
20
Prosiding
Karakterisasi aljabar pada graf bipartit
Dari contoh di atas dapat dilihat bahwa derajat dari setiap simpul adalah tiga. Dengan kata lain, seluruh simpul dengan warna yang sama mempunyai derajat yang sama yaitu tiga. Pada artikel ini akan banyak bekerja pada graf bipartit semi teratur sehingga diperlukan Lemma yang mengkaitkan derajat dengan nilai eigen dari graf teratur seperti yang termuat dalam proposisi berikut Proposisi 2.1 [2] Misalkan graf teratur berderajat k. Maka: 1. k merupakan salah satu nilai eigen dari . 2. Jika terhubung, maka multiplisitas dari k adalah 1 3. Untuk setiap nilai eigen dari graf , didapatkan 3. PEMBAHASAN Dari Proposisi 2.1, dapat dikembangkan pada graf bipartit semiteratur seperti dalam Teorema berikut Teorema 3.1 [4] Misalkan graf bipartit semiteratur dengan partisi ( ) dan misalkan berderajat dan berderajat l. Maka terdapat nilai eigen dan vektor eigen sedemikian hingga ( ) ( ) ( ) ( ) Dari Teorema 3.1 di atas, karena vektor eigen adalah vektor tak nol, dengan mengalikan kedua persamaan, diperoleh Sehingga jika √ Dapat didefinisikan sebagai berikut ( )
{
Contoh { } dan { }. Tinjau Gambar 1 di atas. Jika ( ) dengan Maka dapat dilihat Graf adalah graf semiteratur. Derajat dari adalah tiga dan derajat dari adalah dua. Menggunakan SAGE [5], dapat diperoleh matriks ketetanggaan dan ruang eigen dari graf sebagai berikut
Gambar 3. Matriks ketetanggaan dan ruang eigen graf
Dari Gambar 3 di atas, diperoleh salah satu nilai eigen [
]=[
Seminar Nasional Matematika 2014
√
√
√
adalah √
=√
dengan vektor
].
21
Prosiding
Karakterisasi aljabar pada graf bipartit
Jika kita tinjau kembali Lemma 2.1, dan memisalkan ( eigen dari dengan nilai eigen , dapat dilihat bahwa ( dengan nilai eigen . Dengan kata lain, jika [ ]
[
] [ ]
[
][
[
) menjadi salah satu vektor ) adalah vektor eigen dari
][ ]
[
[
]
]
maka [
]
[
]
]
[
]
Sehingga dapat disimpulkan dan mempunyai multiplisitas yang sama. Kalimat di atas dapat digunakan untuk membuktikan Teorema berikut Teorema 3.2 [4] Misalkan matriks ketetanggaan dari graf Maka persamaan berikut ekivalen 1. adalah graf bipartit 2. dan nilai eigen dari mempunyai multiplisitas yang sama. Teorema 3.2 memberikan akibat seperti di bawah ini Akibat 3.1 adalah graf bipartit dengan banyaknya simpul bilangan gasal. Maka nol adalah salah satu nilai eigennya. Bukti. Banyaknya simpul dapat dinyatakan dalam . Nilai didapatkan dari dua nilai eigen tak nol dan negatifnya dan yang lain adalah nilai eigen nol. Sekarang akan diberikan sifat graf bipartit terkait matriks keterkaitan. Proposisi 3.1 Misalkan dan masing-masing matriks keterkaitan dan matriks ketetrkaitan berarah dari graf bipartit . Maka terdapat matriks diagonal dengan entri 1 atau -1 sedemikian hingga . Bukti. Matriks keterkaitan yang dimaksud berarah pada graf sederhana mempunyai jumlah entri di tiap kolom adalah nol. Pada graf bipartit, matriks keterkaitan dapat dibentuk sedemikian hingga satu simpul merupakan ujung positif atau negatif dari semua sisi. Hal ini mengakibatkan jumlah entri di baris sama dengan derajat dari simpul ke , jika simpul merupakan ujung positif. Jika jika simpul merupakan ujung negatif, maka jumlah entri di baris sama dengan – . Sehingga dapat dibentuk matriks diagonal ( ) jika simpul ke pada matriks merupakan ujung positif (negatif) dengan yang mengakibatkan . Contoh Tinjau kembali Gambar 1 di atas. Dengan menggunakan SAGE [5], ditunjukkan bahwa untuk Graf Lengkap Bipartit berlaku
Seminar Nasional Matematika 2014
22
dapat .
Prosiding
Karakterisasi aljabar pada graf bipartit
Gambar 4. Contoh Proposisi 3.1 Proposisi selanjutnya membahas sifat lain dari graf bipartit. Sebelumnya penulis memperkenalkan matriks ( ) yaitu matriks diagonal dengan baris menandakan simpul dan entri diagonalnya adalah derajat dari simpul. Proposisi 3.2 ( ) - A( ).
graf bipartit jika dan hanya jika
( ) + A( ) similar dengan matriks
Bukti. Berdasarkan Definisi 2.4, matriks ( ) + A( ) similar dengan matriks ( ) A( ) jika dan hanya jika terdapat matriks invertibel sedemikian hingga ( ( ) ( )) ( ) ( ). Pada graf bipartit, Matriks dapat ditelusuri dari matriks pada Proposisi 3.1 dengan . Contoh Tinjau kembali Gambar 1 di atas. Dengan menggunakan SAGE, dapat ( )) bahwa untuk Graf Lengkap Bipartit berlaku ( ( ) ( ) dengan .
ditunjukkan ( )
Gambar 5. Contoh Proposisi 3.2 Seminar Nasional Matematika 2014
23
Prosiding
Karakterisasi aljabar pada graf bipartit
Tinjau graf bipartit ( ̅ adalah rata-rata derajat dari bipartit semi teratur maka ̅ Contoh: Graf ̅ .
( ( )
) didefinisikan ̅ adalah rata-rata derajat dari dan ∑ ∑ yaitu ̅ dan ̅ . Pada graf dan ̅ .
( ) ) dengan
{0,2,4} dan
{
}. Maka
̅
dan
Gambar 6. Graf Bipartit Menggunakan Definisi di atas dan Teorema 2.1 serta Lemma 2.1, daat dibuktikan Proposisi di bawah ini Proposisi 3.3[3] Misalkan ( ) graf bipartit dengan simpul ̅ ̅ dan dan adalah rata-rata derajat dengan nilai eigen maksimal . Maka √ ̅ ̅ Bukti. Misalkan
matriks ketetanggan dari graf
Dari Lemma 2.1 diperoleh
[
]
Dari Teorema 2.1, dapat dibentuk matriks
dengan [
̅ ̅
Dapat dicek bahwa nilai eigen dari matriks Teorema 2.1, didapatkan
sebagai berikut
]
adalah √ ̅ ̅ dan
√ ̅ ̅ . Menggunakan
√ ̅ ̅ 4. KESIMPULAN Dari pembahasan di atas, terdapat beberapa sifat dari graf bipartit terkait vector eigen, nilai eigen, multiplisitas dan similaritas yaitu: 1. Jika nilai eigen dari graf bipartit, maka juga nilai eigen dari dengan multiplisitas yang sama. 2. Terdapat matriks diagonal dengan entri 1 atau -1 sedemikian hingga . 3. graf bipartit jika dan hanya jika jika ( ) + A( ) similar dengan matriks ( ) A( ). Seminar Nasional Matematika 2014
24
Prosiding
Karakterisasi aljabar pada graf bipartit
4.
( ) graf bipartit dengan simpul rata derajat dengan nilai eigen maksimal . Maka
dan ̅ dan ̅ adalah rata-
√ ̅ ̅ DAFTAR PUSTAKA [1] Salvatore, J., Bipartite Graphs and Problem Solving, University of Chicago, 2007. [2] Biggs, N., Algebraic Graf Theory. Cambridge: Cambridge University Press, 1974. [3] Abiad, A., Dalfo C., Fiol, M.G., Algebraic Characterizations of Regularity Properties in Bipartite Graphs, European Journal Of Combinatorics, 2013 [4] Godsil, C. Royle, G. Algebraic Graph Theory, Springer, 2001. [5] Sage, http://sagemath.org, Free, public notebook server at http://sagenb.org. [6] Hartsfield, N., Ringel G., Pearls in Graph Theory, Academic Press San Diego and London, 1994. [7] Beezer, R, An Introduction to Algebraic Graph Theory, Mathematics Department Seminar Pasicic University, 2009.
[email protected]
Seminar Nasional Matematika 2014
25
Prosiding
