LAPORAN PENELITIAN KOMPETITIF DOSEN BERSAMA MAHASISWA
MENENTUKAN SPECTRUM SUATU GRAF BERBANTUAN MATLAB
KETUA TIM PENELITI ABDUSSAKIR, M.Pd
JURUSAN MATEMATIKA FAKULTAS SAINS DAN TEKNOLOGI UNIVERSITAS ISLAM NEGERI MAULANA MALIK IBRAHIM MALANG 2009
PENGESAHAN LAPORAN PENELITIAN KOMPETITIF DOSEN BERSAMA MAHASISWA
Judul Penelitian
: Menentukan Spectrum suatu Graf Berbantuan Matlab
Ketua Peneliti/NIP Anggota/NIP/NIM
: Abdussakir, M.Pd/19751006 200312 1 001 :Wahyu H. Irawan, M.Pd/19710420 200003 1 003 Evawati Alisah, M.Pd/10720604 199903 2 001 Imam Fachruddin/06510004 Novia Dwi Rahmawati/06510039 Iqlillah Muzayyana D.F./06510061
Malang, 29 Desember 2009 Mengetahui a.n. Dekan Pembantu Dekan Bidang Akademik
Ketua Peneliti,
ttd
ttd
Dr. H. Agus Mulyono, S.Pd, M.Kes NIP. 19750808 199903 1 003
Abdussakir, M.Pd NIP 19751006 200312 1 001
KATA PENGANTAR
Puji syukur ke hadirat Allah SWT, sehingga dengan rahmat dan hidayah-Nya laporan penelitian dengan judul “Menentukan Spectrum suatu Graf Berbantuan Matlab” dapat diselesaikan. Sholawat dan salam semoga tetap tercurahkan kepada nabi Muhammad SAW yang telah membimbing manusia menuju jalan yang lurus, yaitu agama Islam. Penelitian ini difokuskan pada pengkajian spectrum graf komplit (Kn), graf bintang (Sn), graf bipartisi komplit (Km,n), dan graf lintasan (Pn). Mengingat masih banyaknya jenis graf, maka penelitian mengenai spectrum masih dapat dilakukan. Selama penyusunan laporan ini, peneliti telah dibantu oleh banyak pihak. Pada kesempatan ini, peneliti menyampaikan terima kasih kepada. 1. Prof. Dr. H. Imam Suprayogo, selaku rektor UIN Maulana Malik Ibrahim Malang. 2. Prof. Drs. H. Sutiman B. Sumitro, SU. D.Sc selaku dekan Fakultas Sains dan Teknologi UIN Maulana Malik Ibrahim Malang beserta seluruh Pembantu Dekan di Fakultas Sains dan Teknologi. 3. Abdussakir, M.Pd, selaku ketua Jurusan Matematika Fakultas Sains dan Teknologi UIN Maulana Malik Ibrahim Malang, beserta rekan-rekan dosen Jurusan Matematika Fakultas Sains dan Teknologi UIN Maulana Malik Ibrahim Malang.
i
4. Staf Karyawan di Jurusan Matematika Fakultas Sains dan Teknologi UIN Maulana Malik Ibrahim Malang. Peneliti mendoakan semoga bantuan yang telah diberikan dicatat sebagai amal baik oleh Allah SWT. Semoga laporan penelitian ini dapat bermanfaat.
Malang, Desember 2009 Tim Peneliti
ii
DAFTAR ISI
Halaman Sampul Halaman Pengesahan Kata Pengantar ..................................................................................................... i Daftar Isi .............................................................................................................. iii BAB I: PENDAHULUAN A. Latar Belakang ................................................................................ B. Rumusan Masalah ........................................................................... C. Batasan Masalah .............................................................................. D. Tujuan Penelitian ............................................................................. E. Manfaat Penelitian ...........................................................................
1 3 3 3 3
BAB II: KAJIAN PUSTAKA A. Graf ................................................................................................. 4 B. Derajat Titik .................................................................................... 6 C. Graf Terhubung ............................................................................... 13 D. Graf dan Matriks ............................................................................. 19 E. Spectrum Graf ................................................................................. 22 BAB III: METODE PENELITIAN A. Jenis Penelitian .................................................................................. 26 B. Tahap Penelitian ................................................................................ 26 BAB IV: PEMBAHASAN A. Specturm Graf Komplit (Kn) .............................................................. B. Specturm Graf Star (Sn) ..................................................................... C. Spectrum Graf Bipartisi Komplit (Km,n) ............................................. D. Spectrum Graf Lintasan (Pn) ..............................................................
27 45 68 95
BAB V: PENUTUP A. Kesimpulan ....................................................................................... 117 B. Saran ................................................................................................. 117 DAFTAR PUSTAKA ......................................................................................... 118
iii
BAB I PENDAHULUAN
A. Latar Belakang Teori graf mempunyai banyak aplikasi praktis dalam berbagai disiplin, misalnya dalam biologi, ilmu komputer, ekonomi, teknik, informatika, linguistik, matematika, kesehatan, dan ilmu-ilmu sosial. Dalam berbagai hal, graf menjadi alat pemodelan yang sangat baik untuk menjelaskan dan menyelesaikan suatu permasalahan. Graf G adalah pasangan (V(G), E(G)) dengan V(G) adalah himpunan tidak kosong dan berhingga dari objek-objek yang disebut titik, dan E(G) adalah himpunan (mungkin kosong) pasangan takberurutan dari titik-titik berbeda di V(G) yang disebut sisi. Banyaknya unsur di V(G) disebut order dari G dan dilambangkan dengan p(G), dan banyaknya unsur di E(G) disebut ukuran dari G dan dilambangkan dengan q(G). Jika graf yang dibicarakan hanya graf G, maka order dan ukuran dari G masingmasing cukup ditulis p dan q. Graf dengan order p dan ukuran q dapat disebut graf-(p, q). Sisi e = (u, v) dikatakan menghubungkan titik u dan v. Jika e = (u, v) adalah sisi di graf G, maka u dan v disebut terhubung langsung (adjacent), v dan e serta u dan e disebut terkait langsung (incident), dan titik u dan v disebut ujung dari e. Untuk selanjutnya, sisi e = (u, v) akan ditulis e = uv. Derajat dari titik v di graf G, ditulis degG(v), adalah banyaknya sisi di G yang terkait langsung dengan v. Dalam konteks
1
2 pembicaraan hanya terdapat satu graf G, maka tulisan degG(v) disingkat menjadi deg(v). Misalkan G graf dengan order p (p 1) dan ukuran q serta himpunan titik V(G) = {v1, v2, …, vp}. Matriks keterhubungan titik (atau matriks keterhubungan) dari graf G, dinotasikan dengan A(G), adalah matriks (p p) dengan unsur pada baris ke-i dan kolom ke-j bernilai 1 jika titik vi terhubung langsung dengan titik vj serta bernilai 0 jika titik vi tidak terhubung langsung dengan titik vj. Dengan kata lain, matriks keterhubungan dapat ditulis A(G) = [aij], 1 i, j p, dengan 1 aij 0
, jika vi v j E (G ) , jika vi v j E (G )
Matriks keterhubungan suatu graf G adalah matriks simetri dengan unsur 0 dan 1 dan memuat nilai 0 pada diagonal utamanya. Matriks keterhubungan banyak digunakan untuk membahas karakteristik graf karena matriks keterhubungan merupakan matriks persegi. Bekerja dengan matriks persegi memberikan banyak kemudahan dibanding dengan matriks tidak persegi. Pembahasan matriks keterhubungan suatu graf dapat dikaitkan dengan konsep nilai eigen dan vektor eigen pada topik aljabar linier yang menghasilkan konsep spectrum suatu graf. Penelitian mengenai spectrum suatu graf merupakan hal yang relatif baru dan banyak dilakukan. Oleh sebab itu, maka peneliti merasa perlu untuk meneliti spectrum suatu graf yang lebih ditekankan pada langkah-langkah menentukan
3 spectrum dan análisis pembuktiannya dengan mengambil judul “Menentukan Spectrum suatu Graf Berbantuan Matlab”. B. Rumusan Masalah Masalah dalam penelitian ini dirumuskan sebagai berikut, yaitu bagaimana menentukan spectrum suatu graf berbantuan Matlab? C. Batasan Masalah Untuk lebih menfokuskan penelitian, maka graf yang dikaji dalam penelitian ini dibatasi pada graf komplit (Kn), graf bintang (Sn), graf bipartisi komplit (Km,n), dan graf lintasan (Pn). D. Tujuan Penelitian Sesuai rumusan masalah, maka tujuan penelitian ini adalah untuk menjelaskan proses atau langkah-langkah menentukan spectrum suatu graf berbantuan Matlab. E. Manfaat Penelitian Penelitian ini diharapkan dapat memberikan manfaat sebagai berikut. 1. Memberikan informasi mengenai langkah-langkah menentukan spectrum suatu graf sehingga dapat acuan oleh peneliti lain untuk menentukan spectrum graf-graf lain yang belum dikaji dalam penelitian ini. 2. Memberikan informasi mengenai spectrum suatu graf sehingga dapat digunakan oleh peneliti lain untuk mengkaji lebih mendalam tentang karakteristik suatu graf atau untuk aplikasi pada masalah yang berkaitan.
BAB IV PEMBAHASAN
A. Spectrum Graf Komplit (Kn) 1. Spectrum dari Graf Komplit (𝑲𝟐 ) Untuk graf komplit 𝐾2 dapat digambarkan grafnya seperti Gambar 4.1 berikut
𝐾2 :
𝑣1
𝑣2
Gambar 4.1 Graf Komplit 𝐾2 Pada graf komplit 𝐾2 menghasilkan matriks adjacency sebagai berikut 𝑣1 𝑣2 𝑣1 0 1 𝑣2 1 0
𝐴=
Setelah mendapatkan bentuk matriks adjacency maka akan dicari nilai eigen dan vektor eigen dari matriks-matriks tersebut, yaitu dengan menggunakan persamaan det 𝐴 − 𝜆𝐼 = 0 𝐴=
0 1
1 0
det 𝐴 − 𝜆𝐼 = 0 det
0 1
1 1 0 −𝜆 0 0 1
det
0 1
1 𝜆 − 0 0
0 𝜆
=0 =0
27
28 det
−𝜆 1
1 −𝜆
= 𝜆2 − 1 = (𝜆 − 1)(𝜆 + 1)
Jadi didapatkan nilai eigen bagi 𝐴 adalah 𝜆 = 1 dan 𝜆 = −1 Setelah mendapatkan nilai eigen maka selanjutnya akan dicari vektor eigen, yaitu: −𝜆 1
0 1 𝑘 = −𝜆 𝑙 0
Disubstitusikan nilai eigen 𝜆 = 1 dan 𝜆 = −1 ke dalam persamaan di atas. Untuk 𝜆 = 1 maka vektor eigennya adalah: −1 1
1 𝑘 0 = −1 𝑙 0
Maka didapatkan −𝑘 + 𝑙 = 0 𝑘−𝑙 = 0 𝑘=𝑙
Misal 𝑙 = 𝑠 diperoleh bahwa solusi umum bagi 𝐴 − (1)𝐼 𝑋 = 0 adalah 𝑠1 =
𝑠 1 𝑘 = =𝑠 𝑠 𝑙 1
Jadi basis untuk ruang vektor eigennya sebanyak 1. Untuk 𝜆 = −1 maka vektor eigennya adalah: 1 1
1 𝑘 0 = 1 𝑙 0
Maka didapatkan
29 𝑘+𝑙 =0 𝑘 = −𝑙
𝑣3
Misal 𝑙 = 𝑠 diperoleh bahwa solusi umum bagi 𝐴 − (−1)𝐼 𝑋 = 0 adalah 𝑣1
𝑠2 =
1 𝑘 𝑣2 𝑠 = =𝑠 −𝑠 𝑙 −1
Jadi basis untuk ruang vektor eigennya sebanyak 1. Jadi untuk 𝜆 = 1 terdapat satu basis ruang vektor eigen , dan untuk 𝜆 = −1 juga terdapat satu basis ruang vektor eigen , maka spectrum graf komplit 𝐾2 adalah Spect 𝑲𝟐 =
𝟏 𝟏
−𝟏 𝟏
2. Spectrum dari Graf Komplit (𝑲𝟑 ) Untuk graf komplit 𝐾3 yang dapat digambarkan grafnya seperti Gambar 4.2 berikut
𝐾3 :
Gambar 4.2 Graf Komplit 𝐾3 Pada graf komplit 𝐾3 menghasilkan matriks adjacency sebagai berikut
𝐴=
𝑣1 𝑣1 0 𝑣2 1 𝑣3 1
𝑣2 𝑣3 1 1 0 1 1 0
30 0 𝐴= 1 1
1 0 1
1 1 0
det 𝐴 − 𝜆𝐼 = 0 det
0 1 1
1 0 1
1 1 1 −𝜆 0 0 0
det
0 1 1
1 0 1
1 𝜆 1 − 0 0 0
0 0 𝜆 0 0 𝜆
det
−𝜆 1 1
1 1 −𝜆
−𝜆 = 1 1
1 −𝜆 1
0 0 1 0 0 1
=0
=0 1 −𝜆 1
1 −𝜆 1 1 −𝜆 1
1 −𝜆 1
= −𝜆3 + 1 + 1 + 𝜆 + 𝜆 + 𝜆 = −𝜆3 + 3𝜆 + 2 = 𝜆 − 2 𝜆 + 1 (𝜆 + 1) Jadi didapatkan nilai eigen bagi 𝐾3 adalah 𝜆 = 2 dan 𝜆 = −1 Setelah mendapatkan nilai eigen maka selanjutnya akan dicari vektor eigen, yaitu: −𝜆 1 1
1 −𝜆 1
1 𝑘 0 1 𝑙 = 0 0 −𝜆 𝑚
Disubstitusikan nilai eigen 𝜆 = 2 dan 𝜆 = −1 ke dalam persamaan di atas. Pada graf komplit 𝐾3 menghasilkan matriks adjacency 3 × 3 sehingga untuk menentukan vektor eigen maka matriks di atas akan direduksi menjadi bentuk eselon tereduksi baris Untuk = 2 , maka
31 −2 𝐴 − 𝜆𝐼 0 = 1 1
1 −2 1
1 1 −2
0 0 0
Dengan mereduksi matriks di atas menjadi bentuk eselon tereduksi baris, maka didapatkan i. 𝑘 − 𝑚 = 0; sehingga 𝑘 = 𝑚 ii. 𝑙 − 𝑚 = 0; sehingga 𝑙 = 𝑚 Dari (ii) maka (i) didapatkan 𝑘=𝑙=𝑚 Misal 𝑚 = 𝑠 diperoleh bahwa solusi umum bagi 𝐴 − (2)𝐼 𝑋 = 0 adalah 𝑠 𝑘 1 𝑠1 = 𝑙 = 𝑠 = 𝑠 1 𝑠 1 𝑚 Jadi basis untuk ruang vektor eigennya sebanyak 1. Untuk 𝜆 = −1, dengan menggunakan Operasi Baris Elementer (OBE) maka didapatkan 1 𝐴 − 𝜆2 𝐼 0 = 1 1
1 1 1
1 0 1 0 1 0
Dengan mereduksi matriks di atas menjadi bentuk eselon tereduksi baris, maka didapatkan 𝑘+𝑙+𝑚=0 𝑘 = −𝑙 − 𝑚 Misal 𝑙 = 𝑠 dan 𝑚 = 𝑡
32 diperoleh bahwa solusi umum bagi 𝐴 − (−1)𝐼 𝑋 = 0 adalah −𝑠 − 𝑡 𝑘 −1 −1 𝑠2 = 𝑙 = 𝑠 =𝑠 1 +𝑡 0 𝑡 0 1 𝑚 Jadi basis untuk ruang vektor eigennya sebanyak 2. Jadi untuk 𝜆 = 2 terdapat satu basis ruang vektor eigen , dan untuk 𝜆 = −1 terdapat dua basis ruang vektor eigen , jadi spectrum graf komplit 𝐾3 adalah Spect 𝑲𝟑 =
𝟐 𝟏
−𝟏 𝟐
3. Spectrum dari Graf Komplit (𝑲𝟒 ) Untuk graf komplit 𝐾4 yang dapat digambarkan grafnya seperti Gambar 4.3 berikut
𝐾4 :
𝑣4
𝑣3
𝑣1
𝑣2
Gambar 4.3: Graf Komplit 𝐾4 Pada graf komplit 𝐾4 menghasilkan matriks adjacency sebagai berikut
𝐴=
0 1 𝐴= 1 1
𝑣1 𝑣2 𝑣3 𝑣4
𝑣1 0 1 1 1 1 0 1 1
𝑣3 1 1 0 1
𝑣2 1 0 1 1 1 1 0 1
1 1 1 0
𝑣4 1 1 1 0
33 det 𝐴 − 𝜆𝐼 = λ4 − 6λ2 − 8λ − 3 = 𝜆 − 3 (𝜆 + 1)(𝜆 + 1)(𝜆 + 1) Jadi didapatkan nilai eigen bagi 𝐾4 adalah = 3 , dan 𝜆 = −1 Setelah mendapatkan nilai eigen maka akan dicari vektor eigennya, yaitu: −𝜆 1 1 1
1 −𝜆 1 1
0 1 𝑘 1 𝑙 = 0 0 1 𝑚 −𝜆 𝑛 0
1 1 −𝜆 1
Disubstitusikan nilai 𝜆 = 3 dan 𝜆 = −1 ke dalam persamaan di atas. Pada graf komplit 𝐾4 menghasilkan matriks adjacency 4 × 4 sehingga untuk menentukan vektor eigen maka matriks di atas akan direduksi menjadi bentuk eselon tereduksi baris Untuk 𝜆 = 3, maka −3 1 [𝐴 − 𝜆 𝐼│0] = 1 1
1 −3 1 1
1 1 −3 1
1 1 1 −3
0 0 0 0
Dengan mereduksi matriks di atas menjadi bentuk eselon tereduksi baris, maka didapatkan i.
𝑘 − 𝑛 = 0; sehingga 𝑘 = 𝑛
ii.
𝑙 − 𝑛 = 0 ; sehingga 𝑙 = 𝑛
iii.
𝑚 − 𝑛 = 0; sehingga 𝑚 = 𝑛
Dari (i), (ii), dan (iii) maka diperoleh 𝑘=𝑙=𝑚=𝑛 Misal 𝑛 = 𝑠, maka diperoleh bahwa solusi umum bagi 𝐴 − (3)𝐼 𝑋 = 0 adalah
34 𝑠 𝑘 𝑙 = 𝑠 =𝑠 𝑠1 = 𝑚 𝑠 𝑠 𝑛
1 1 1 1
Jadi basis untuk ruang vektor eigennya sebanyak 1 Untuk 𝜆 = −1, dengan menggunakan Operasi Baris Elementer (OBE) maka didapatkan 1 [𝐴 − 𝜆 𝐼│0] = 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
0 0 0 0
Dengan mereduksi matriks di atas menjadi bentuk eselon tereduksi baris, maka didapatkan 𝑘+𝑙+𝑚+𝑛= 0 𝑘 = −𝑙 − 𝑚 − 𝑛 Misal 𝑙 = 𝑠, 𝑚 = 𝑡 dan 𝑛 = 𝑢 , maka diperoleh bahwa solusi umum bagi 𝐴 − (−1)𝐼 𝑋 = 0 adalah −𝑠 − 𝑡 − 𝑢 𝑘 𝑠 𝑙 = 𝑠1 = 𝑚 =𝑠 𝑡 𝑛 𝑢
−1 1 +𝑡 0 0
−1 0 +𝑢 1 0
−1 0 0 1
Jadi basis untuk ruang vektor eigennya sebanyak 3 Jadi untuk 𝜆 = 3 terdapat satu basis ruang vektor eigen , dan untuk 𝜆 = −1 terdapat tiga basis ruang vektor eigen , jadi spectrum graf komplit 𝐾4 adalah Spect 𝑲𝟒 = 4. Spectrum dari Graf Komplit (𝑲𝟓 )
𝟑 𝟏
−𝟏 𝟑
35 Untuk graf komplit 𝐾5 yang dapat digambarkan grafnya seperti Gambar 4.4 berikut 𝑣5 𝑣1
𝑣4
𝐾5 : 𝑣2
𝑣3
Gambar 4.4: Graf Komplit (𝐾5 ) Pada graf komplit 𝐾5 menghasilkan matriks adjacency sebagai berikut
𝐴=
0 1 𝐴= 1 1 1
𝑣1 𝑣2 𝑣3 𝑣4 𝑣5 1 0 1 1 1
𝑣1 0 1 1 1 1
𝑣3 1 1 0 1 1
𝑣2 1 0 1 1 1 1 1 0 1 1
1 1 1 0 1
𝑣4 1 1 1 0 1
𝑣5 1 1 1 1 0
1 1 1 1 0
det 𝐴 − 𝜆𝐼 = −𝜆5 + 10𝜆3 + 20𝜆2 + 15𝜆 + 4 = (𝜆 − 4)(𝜆 + 1)(𝜆 + 1)(𝜆 + 1)(𝜆 + 1) Jadi didapatkan nilai eigen bagi 𝐾5 adalah = 4 , dan 𝜆 = −1 Setelah mendapatkan nilai eigen maka akan dicari vektor eigennya, yaitu: −𝜆 1 1 1 1
1 −𝜆 1 1 1
1 1 −𝜆 1 1
1 1 1 −𝜆 1
0 1 𝑘 1 𝑙 0 1 𝑚 = 0 0 1 𝑛 −𝜆 𝑜 0
36 Dibstitusikan nilai 𝜆 = 4 dan 𝜆 = −1 ke dalam persamaan di atas. Pada graf komplit 𝐾5 menghasilkan matriks adjacency 5 × 5 sehingga untuk menentukan vektor eigen maka matriks di atas akan direduksi menjadi bentuk eselon tereduksi baris Untuk 𝜆 = 4, maka −4 1 [𝐴 − 𝜆1 𝐼│0] = 1 1 1
1 −4 1 1 1
1 1 −4 1 1
1 1 1 −4 1
1 1 1 1 −4
0 0 0 0 0
Dengan mereduksi matriks di atas menjadi bentuk eselon tereduksi baris, maka didapatkan i.
𝑘 − 𝑜 = 0 ; sehingga 𝑘 = 𝑜
ii.
𝑙 − 𝑜 = 0 ; sehingga 𝑙 = 𝑜
iii.
𝑚 − 𝑜 = 0 ;sehingga 𝑚 = 𝑜
iv.
𝑛 − 𝑜 = 0 ; sehingga 𝑛 = 𝑜 Dari (i), (ii), (iii) dan (iv) maka diperoleh 𝑘=𝑙=𝑚=𝑛=𝑜
Misal 𝑜 = 𝑠, maka diperoleh bahwa solusi umum bagi 𝐴 − (4)𝐼 𝑋 = 0 adalah 𝑠 𝑘 𝑠 𝑙 𝑠1 = 𝑚 = 𝑠 = 𝑠 𝑠 𝑛 𝑠 𝑜
1 1 1 1 1
Jadi basis untuk ruang vektor eigennya sebanyak 1. Untuk 𝜆 = −1, dengan menggunakan Operasi Baris Elementer (OBE) maka didapatkan
37
𝐴 − 𝜆1 𝐼 0 = 𝑣6
1 1 1 1 1𝑣
5
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
0 0 0 0 0
Dengan mereduksi matriks di atas menjadi bentuk eselon tereduksi baris, maka didapatkan
𝑣+𝑤+𝑥+𝑦+𝑧 =0 𝑣 = −𝑤 − 𝑥 − 𝑦 − 𝑧
Misal 𝑤 = 𝑟, 𝑥 = 𝑠 , 𝑦 = 𝑡 dan 𝑧 = 𝑢 , maka diperoleh bahwa solusi umum bagi 𝐴 − (−1)𝐼 𝑋 = 0 adalah −𝑟 − 𝑠 − 𝑡 − 𝑢 𝑣 −𝑤 − 𝑥 − 𝑦 − 𝑧 𝑤 𝑤 𝑟 𝑠2 = 𝑥 = = 𝑥 𝑠 𝑦 𝑦 𝑡 𝑧 𝑧 𝑢 −1 1 = 𝑟 0 +𝑠 0 0
−1 0 1 +𝑡 0 0
−1 0 0 +𝑢 1 0
−1 0 0 0 1
Jadi basis untuk ruang vektor eigennya sebanyak 4. Jadi untuk 𝜆 = 3 terdapat satu basis ruang vektor eigen , dan untuk 𝜆 = −1 terdapat empat basis vektor eigen, jadi spectrum graf komplit 𝐾5 adalah Spect 𝑲𝟓 =
𝟒 𝟏
−𝟏 𝟒
5. Spectrum dari Graf Komplit (𝑲𝟔 ) Untuk graf komplit 𝐾6 yang dapat digambarkan grafnya seperti Gambar 4.5 berikut
38
𝐾6 :
𝑣4
𝑣1
𝑣2
𝑣3
Gambar 4.5. Garf Komplit (𝐾6 ) Pada graf komplit 𝐾6 menghasilkan matriks adjacency sebagai berikut
𝐴=
0 1 1 𝐴= 1 1 1
𝑣1 𝑣2 𝑣3 𝑣4 𝑣5 𝑣6 1 0 1 1 1 1
𝑣1 0 1 1 1 1 1 1 1 0 1 1 1
𝑣2 1 0 1 1 1 1
𝑣3 1 1 0 1 1 1
1 1 1 0 1 1
1 1 1 1 0 1
𝑣4 1 1 1 0 1 1
𝑣5 1 1 1 1 0 1
𝑣6 1 1 1 1 1 0
1 1 1 1 1 0
det 𝐴 − 𝜆𝐼 = 𝜆6 − 15𝜆4 − 40𝜆3 − 45𝜆2 − 24𝜆 − 5 = 𝜆 − 5 (𝜆 + 1)(𝜆 + 1)(𝜆 + 1)(𝜆 + 1)(𝜆 + 1) Jadi didapatkan nilai eigen bagi 𝐾6 adalah = 5 , dan 𝜆 = −1 Setelah mendapatkan nilai eigen maka akan dicari vektor eigennya, yaitu:
39 −𝜆 1 1 1 1 1
1 −𝜆 1 1 1 1
1 1 −𝜆 1 1 1
1 1 1 −𝜆 1 1
1 1 1 1 –𝜆 1
1 1 1 1 1 –𝜆
𝑎 0 𝑏 0 𝑐 0 𝑑 = 0 𝑒 0 𝑓 0
Disubstitusikan nilai 𝜆 = 5 dan 𝜆 = −1 ke dalam persamaan di atas. Pada graf komplit 𝐾6 menghasilkan matriks adjacency 6 × 6 sehingga untuk menentukan vektor eigen maka matriks di atas akan direduksi menjadi bentuk eselon tereduksi baris Untuk 𝜆 = 5, maka −5 1 1 𝐴 − 𝜆𝐼 0 = 1 1 1
1 1 1 1 1 1 −5 1 1 1 1 −5 1 1 1 −5 1 1 1 –5 1 1 1 1
1 1 1 1 1 1
0 0 0 0 0 0
Dengan mereduksi matriks di atas menjadi bentuk eselon tereduksi baris, maka didapatkan i.
𝑘 − 𝑝 = 0 ; sehingga 𝑘 = 𝑝
ii.
𝑙 − 𝑝 = 0 ; sehingga 𝑙 = 𝑝
iii.
𝑚 − 𝑝 = 0 ; sehingga 𝑚 = 𝑝
iv.
𝑛 − 𝑝 = 0 ; sehingga 𝑛 = 𝑝
v.
𝑜 − 𝑝 = 0 ; sehingga 𝑜 = 𝑝 Dari (i), (ii), (iii), (iv) dan (v) didapatkan 𝑘=𝑙=𝑚=𝑛=𝑜=𝑝 Misal 𝑝 = 𝑠, maka diperoleh bahwa solusi umum bagi 𝐴 − (5)𝐼 𝑋 = 0 adalah
40 𝑎 𝑠 𝑏 𝑠 𝑐 𝑠 𝑠1 = 𝑑 = =𝑠 𝑠 𝑒 𝑠 𝑓 𝑠
1 1 1 1 1 1
Jadi basis untuk ruang vektor eigennya sebanyak 1. Untuk 𝜆 = −1, dengan menggunakan Operasi Baris Elementer (OBE) maka didapatkan 1 1 1 [𝐴 − 𝜆 𝐼│0] = 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
0 0 0 0 0 0
Dengan mereduksi matriks di atas menjadi bentuk eselon tereduksi baris, maka didapatkan 𝑘+𝑙+𝑚+𝑛+𝑜+𝑝 =0 𝑘 = −𝑙 − 𝑚 − 𝑛 − 𝑜 − 𝑝 Misal 𝑙 = 𝑟, 𝑚 = 𝑠 , 𝑛 = 𝑡, 𝑜 = 𝑢, dan 𝑝 = 𝑣 , maka diperoleh bahwa solusi umum bagi 𝐴 − (−1)𝐼 𝑋 = 0 adalah −𝑙 − 𝑚 − 𝑛 − 𝑜 − 𝑝 𝑘 −𝑟 − 𝑠 − 𝑡 − 𝑢 − 𝑣 𝑙 𝑙 𝑟 𝑚 𝑚 𝑠 𝑠2 = = = 𝑛 𝑛 𝑡 𝑜 𝑜 𝑢 𝑝 𝑝 𝑣 −1 1 0 =𝑟 +𝑠 0 0 0
−1 0 1 +𝑡 0 0 0
−1 0 0 +𝑢 1 0 0
−1 0 0 +𝑣 0 1 0
−1 0 0 0 0 1
41 Jadi basis untuk ruang vektor eigennya sebanyak 5. Jadi untuk 𝜆 = 5 terdapat satu basis ruang vektor eigen , dan untuk 𝜆 = −1 terdapat lima basis ruang vektor eigen , jadi spectrum graf komplit 𝐾5 adalah Spect 𝑲𝟔 =
𝟓 𝟏
−𝟏 𝟓
Teorema: Misal 𝐾𝑛 graf komplit order n, maka spectrum graf komplit (𝐾𝑛 ) adalah Spec 𝐾𝑛 =
(𝑛 − 1) 1
−1 (𝑛 − 1)
Bukti: Misal 𝐾𝑛 adalah graf komplit order n, maka Matriks adjacency dari graf komplit (𝐾𝑛 ) 𝑣1 𝑣2 𝐴 = 𝑣3 ⋮ 𝑣𝑛
𝑣1 0 1 1 ⋮ 1
𝑣2 1 0 1 ⋮ 1
𝑣3 ⋯ 𝑣𝑛 1 ⋯ 1 1 ⋯ 1 0 ⋯ 1 ⋮ ⋱ 1 1 ⋯ 0
Dari matriks adjacency di atas, maka akan dicari nilai eigennya dengan menentukan det 𝐴 − 𝜆𝐼 = 0
det
−𝜆 1 1 ⋮ 1
1 −𝜆 1 ⋮ 1
1 1 −𝜆 ⋮ 1
⋯ ⋯ ⋯ ⋱ ⋯
1 1 1 1 −𝜆
=0
Melalui operasi baris elementer, matriks det 𝐴 − 𝜆𝐼 segitiga atas diperoleh,
direduksi menjadi matriks
42 0 0 0 0 0
1
1
1
1
1
1
2
1 2 2
0
2
1
2
1
(1)( )( 1) 2
1
1
2
3
2
2
1
0
0
0
0
0
0
0
0
0
2
2
2
1 2 4
2
3
1 2 1 2 2 2 n 2 1 2 n 2 n 1 1
det 𝐴 − 𝜆𝐼 tidak lain adalah hasil perkalian diagonal matrik segitiga atas tersebut. Jadi det 𝐴 − 𝜆𝐼 = 𝜆 − 𝑛 − 1
𝜆+1
𝑛−1
Karena, det 𝐴 = 0, maka 𝜆− 𝑛−1
𝜆+1
𝑛−1
=0
Sehingga didapatkan 𝜆 = (𝑛 − 1) atau 𝜆 = −1 Akan dibuktikan untuk 𝜆 = 𝑛 − 1 akan didapatkan banyaknya basis ruang vektor eigen adalah 1. untuk 𝜆 = 𝑛 − 1 akan didapatkan (𝑛 − 1) 1 (𝑛 − 1) 1 𝐴 − 𝜆𝐼 = 1 1 ⋮ ⋮ 1 1
1 ⋯ 1 … (𝑛 − 1) … ⋮ ⋱ ⋯ 1
1 1 1 ⋮ (𝑛 − 1)
Akan ditunjukkan vektor eigen untuk 𝜆 = 𝑛 − 1 𝐴 − 𝜆𝐼 𝑥 = 0
43 (𝑛 − 1) 1 (𝑛 − 1) 1 = 1 1 ⋮ ⋮ 1 1
1 ⋯ 1 … (𝑛 − 1) … ⋮ ⋱ ⋯ 1
𝑥1 1 0 𝑥2 1 0 ⋮ ⋮ = 1 𝑥 0 ⋮ (𝑛−1) 𝑥𝑛 0 (𝑛 − 1)
Dengan mereduksi matriks di atas menjadi bentuk eselon tereduksi baris, maka didapatkan 1 0 = 0 ⋮ 0
0 1 0 ⋮ 0
0 0 1 ⋮ 0
⋯ ⋯ ⋯ ⋱ ⋯
𝑥1 0 −1 𝑥2 −1 0 ⋮ = ⋮ −1 0 −1 𝑥(𝑛−1) 𝑥𝑛 0 0
Kemudian didapatkan i.
𝑥1 = 𝑥𝑛
ii.
𝑥2 = 𝑥𝑛
iii.
⋮ = 𝑥𝑛
iv.
𝑥(𝑛−1) = 𝑥𝑛
Sehingga dari i, ii,iii, dan iv diperoleh 𝑥1 = 𝑥2 = ⋯ = 𝑥(𝑛−1) = 𝑥𝑛 Misal 𝑥𝑛 = 𝑠 maka vektor eigennya adalah
𝑆1 =
𝑥1 𝑥2 ⋮ 𝑥(𝑛−1) 𝑥𝑛
𝑠 𝑠 = ⋮ =𝑠 𝑠 𝑠
1 1 ⋮ 1 1
Jadi didapatkan banyaknya basis ruang vektor eigen untuk 𝜆 = 𝑛 − 1 adalah 1
44 Akan dibuktikan untuk 𝜆 = −1 akan didapatkan banyaknya basis ruang vektor eigen adalah (𝑛 − 1). Untuk 𝜆 = −1 akan didapatkan 1 1 𝐴 − 𝜆𝐼 = 1 ⋮ 1
1 1 1 ⋮ 1
1 1 1 ⋮ 1
⋯ ⋯ ⋯ ⋱ ⋯
1 1 1 1 1
Untuk 𝜆 = −1 akan didapatkan 𝐴 − 𝜆𝐼 𝑥 = 0 1 1 = 1 ⋮ 1
1 1 1 ⋮ 1
1 1 1 ⋮ 1
⋯ ⋯ ⋯ ⋱ ⋯
𝑥1 0 1 𝑥2 1 0 ⋮ = ⋮ 1 0 1 𝑥(𝑛−1) 𝑥𝑛 1 0
Dengan mereduksi matriks di atas menjadi bentuk eselon tereduksi baris, maka didapatkan 1 0 = 0 ⋮ 0
1 0 0 ⋮ 0
1 0 0 ⋮ 0
⋯ ⋯ ⋯ ⋱ ⋯
𝑥1 0 1 𝑥 0 2 0 ⋮ ⋮ = 0 𝑥 0 0 (𝑛−1) 𝑥𝑛 0 0
Kemudian didapatkan 𝑥1 + 𝑥2 + ⋯ + 𝑥(𝑛−1) + 𝑥𝑛 = 0 𝑥1 = −𝑥2 − 𝑥2 − ⋯ − 𝑥(𝑛−1) − 𝑥𝑛 maka vektor eigennya adalah
45
𝑆2 =
𝑥1 𝑥2 ⋮ 𝑥(𝑛−1) 𝑥𝑛
−𝑥2 − 𝑥2 − ⋯ − 𝑥(𝑛−1) − 𝑥𝑛 𝑥2 ⋮ = 𝑥(𝑛−1) 𝑥𝑛 −1 −1 −1 −1 −1 1 0 0 0 0 0 0 1 0 0 = 𝑥2 ⋮ + 𝑥3 0 + 𝑥4 1 + ⋯ + 𝑥(𝑛−1) 0 + 𝑥𝑛 0 0 ⋮ 0 ⋮ ⋮ 0 1 0 0 ⋮ 0 0 0 0 1
Jadi didapatkan banyaknya basis ruang vektor eigen untuk 𝜆 = −1 adalah (𝑛 − 1) Jadi terbukti bahwa Spec 𝑲𝒏 =
(𝒏 − 𝟏) 𝟏
−𝟏 (𝒏 − 𝟏)
B. Spectrum Graf Star Sn 1. Spectrum S 2
S2 :
Representasi matrik adjacent dari graf star dengan n = 2 adalah:
0 1 1 A S2 1 0 0 1 0 0 Persamaan polynomial karakteristik diperoleh dengan:
0 1 1 1 0 0 1 A S2 I 1 0 0 0 1 0 1 1 0 0 0 0 1 1 0
1 0
46
det A S2 I A S 2 I 0 0
1
1
2 1 0
1
2 2
2 2
2 1
Nilai eigen diperoleh dengan:
A S 2 I 2 2 0
2
2 0
1 0 , 2 2 atau 3 2 Basis dari representasi matrik adjacent dari graf star dengan n = 2 adalah: Untuk 1 0 , maka
0 1 1 x1 A S2 1I x 1 0 0 x2 0 1 0 0 x 3 kemudian diperoleh sistem persamaan linier:
x2 x3 0 x2 x3
... 1
x1 0
... 2
Misalkan x2 s dan s 0 , dengan mencari nilai dari x3 pada persamaan (1) maka diperoleh vektor eigennya adalah:
x1 0 0 x2 s s 1 , basisnya adalah 1 dengan 1 0 . x s 1 3 Untuk 2 2 , maka
47 2 A S2 2 I x 1 1
1 2 0
1 x1 0 x2 0 2 x3
kemudian diperoleh sistem persamaan linier: 2 x1 x2 x3 0
... 1
x1 2 x2 0 x1 2 x2
... 2
x1 2 x3 0 x1 2 x3
... 3
Misalkan x1 s dan s 0 , dengan mencari nilai dari x2 dan x3 pada persamaan (1), (2) dan (3) maka diperoleh vektor eigennya adalah: s 1 x1 1 1 , basisnya adalah 1 dengan 2 . 2 x2 2 2 s s 2 2 x 1 3 1 2s 2 2 2
Untuk 3 2 , maka 2 A S2 3 I x 1 1
1 2 0
1 x1 0 x2 0 2 x3
kemudian diperoleh sistem persamaan linier: 2 x1 x2 x3 0 x1 2 x2 0 x1 2 x2 x1 2 x3 0 x1 2 x3
Misalkan x1 s dan s 0 , dengan mencari nilai dari x2 dan x3 pada persamaan diatas maka diperoleh vektor eigennya adalah:
48 1 s x1 1 s 1 2 , basisnya adalah 1 dengan 2 . x 2 s 3 2 2 2 x 1 3 1 2 s 2 2 2
2 0 2 Jadi Spec S 2 1 1 1
2. Spectrum S 3
S3 :
Representasi matrik adjacent dari graf star dengan n = 3 adalah: 0 1 A S3 1 1
1 1 1 0 0 0 0 0 0 0 0 0
Persamaan polynomial karakteristik diperoleh dengan: 0 1 A S3 I 1 1
1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 1 0 1 0 1 0 0 1 1
1
1
0
0
0
0
1 0 0
49
1
0 A S3 I
1 2
0
0
0
0
1
1
1
1
2 2
1 2
1 2 3 2
0
2 2 3
2 2
Nilai eigen diperoleh dengan:
A S3 I 2 2 3 0
2 3
3 0
1 0 , 2 3 atau 3 3 Basis dari representasi matrik adjacent dari graf star dengan n = 3 adalah: Untuk 1 0 , maka
0 1 A S3 1I x 1 1
1 1 1 x1 0 0 0 x2 0 0 0 0 x3 0 0 0 x4
kemudian diperoleh sistem persamaan linier:
x2 x3 x4 0 x4 x2 x3
... 1
x1 0
... 2
Misalkan x2 s , x3 t dan s, t 0 , dengan mencari nilai dari x4 pada persamaan (1) maka diperoleh vektor eigennya adalah:
x1 0 0 0 x2 s s 1 t 0 , basisnya adalah 2 dengan 0 . 1 x3 t 0 1 1 1 x4 s t
50 Untuk 2 3 , maka 3 1 1 1 x1 3 0 0 x2 1 A S3 2 I x 0 1 0 3 0 x3 0 0 3 x4 1
kemudian diperoleh sistem persamaan linier: 3x1 x2 x3 x4 0
x1 3 x2 0 x1 3 x2 x1 3 x3 0 x1 3 x3 x1 3 x4 0 x1 3 x4
Misalkan x1 s dan s 0 , dengan mencari nilai dari x2 dan x3 pada persamaan diatas maka diperoleh vektor eigennya adalah:
x1 1 3 x2 1 x3 x 3 4 1 3
s
1 1 3s 3 3 s 1 , basisnya adalah 1 dengan 2 3 . 3s 3 3 1 3s 3 3
Untuk 3 3 , maka A S3 3 I x
3 1
1 3
1
0
1
0
1 0 3 0
1 x1 0 x2 0 0 x3 3 x4
kemudian diperoleh sistem persamaan linier:
51 3x1 x2 x3 x4 0 x1 3x2 0 x1 3 x2 x1 3x3 0 x1 3x3 x1 3x4 0 x1 3 x4
Misalkan x1 s dan s 0 , dengan mencari nilai dari x2 dan x3 pada persamaan diatas, maka diperoleh vektor eigennya adalah:
s 1 x1 1 3s 1 3 3 3 x2 1 s 1 , basisnya adalah 1 dengan 3 3 . x3 3s 3 3 3 x4 1 1 3s 3 3 3
3 0 3 Jadi Spec S3 1 2 1
3. Spectrum S 4
S4 :
Representasi matrik adjacent dari graf star dengan n = 4 adalah:
0 1 A S4 1 1 1
1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
52 Persamaan polynomial karakteristik diperoleh dengan:
1 A S4 I 1 1 1
1 0 0 0 0 0 0 0 0 0 0 0 0 1
1
1
1
0 A S4 I
2 1
1
1
1
1
1
1
2 2
0
0
0
0
0
0
0
0
3 2 4
1 2
1 2 3
1
2
2 2 4
2
2
2
0
2
Nilai eigen diperoleh dengan:
A S 4 I 3 2 4 0
3 4
4 0
1 0 , 2 4 atau 3 4 Basis dari representasi matrik adjacent dari graf star dengan n = 4 adalah: Untuk 1 0 , maka 0 1 A S4 1I x 1 1 1
1 1 1 1 x1 0 0 0 0 x2 0 0 0 0 x3 0 0 0 0 0 x4 0 0 0 0 x5
kemudian diperoleh sistem persamaan linier:
x2 x3 x4 x5 0 x5 x2 x3 x4
... 1
2 3
53 ... 2
x1 0
Misalkan x2 s , x3 t , x4 u dan s, t , u 0 , dengan mencari nilai dari x5 pada persamaan (1) maka diperoleh vektor eigennya adalah: 0 x1 0 0 0 s x2 1 0 0 x3 s 0 t 1 u 0 t , basisnya adalah 3 dengan 1 0 . u x4 0 0 1 1 1 1 x s t u 5
Untuk 2 4 , maka 4 1 A S4 2 I x 1 1 1
1
1
1
4
0
0
0
4
0
0
0
4
0
0
0
1 x 1 0 x2 0 x3 0 0 x4 x 4 5
kemudian diperoleh sistem persamaan linier: 4 x1 x2 x3 x4 x5 0 x1 4 x2 0 x1 4 x2 x1 4 x3 0 x1 4 x3 x1 4 x4 0 x1 4 x4
x1 4 x5 0 x1 4 x5
Misalkan x1 s dan s 0 , maka diperoleh vektor eigennya adalah:
54 1 x1 4 x2 1 x3 4 x4 1 x 4 5 1 4
s
1 1 4s 4 4 1 4s 4 , basisnya adalah 1 dengan 2 4 . s 4 1 4s 4 4 1 4s 4 4
Untuk 3 4 , maka A S4 3 I x
4 1
1 4
1
1
0
0
1
0
4
1
0
0
1
0
0
0 4 0
1 x 1 0 x2 0 x3 0 0 x4 x 4 5
kemudian diperoleh sistem persamaan linier: 4 x1 x2 x3 x4 x5 0 x1 4 x2 0 x1 4 x2 x1 4 x3 0 x1 4 x3 x1 4 x4 0 x1 4 x4
x1 4 x5 0 x1 4 x5
Misalkan x1 s dan s 0 , maka vektor eigennya adalah: s 1 x1 4 x2 1 x3 4 x4 1 x 4 5 1 4
1 1 4s 4 1 4s s 4 1 4s 4 1 4s 4
4 , 4 4 4
basisnya adalah 1 dengan 3 4 .
4 0 4 Jadi Spec S 4 1 3 1
55 4. Spectrum S 5
S5 :
Representasi matrik adjacent dari graf star dengan n = 5 adalah: 0 1 1 A S5 1 1 1
1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Persamaan polynomial karakteristik diperoleh dengan: 1 1 A S5 I 1 1 1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0 0 A S5 I
1 0 0 0 0
1
1
1 2
0
1
2 2 1 2
1
1
1
1
1
1
1 3 2
2
2
0
0
0
0
0
0
0
0
0
0
0
2
1
2 2
2
2 4
2
3
2
2 2
3 5 4 2
2
0
1
2
56
4 2 5
Nilai eigen diperoleh dengan:
A S5 I 4 2 5 0
4 5 5 0
1 0 , 2 5 atau 3 5 Basis dari representasi matrik adjacent dari graf star dengan n = 5 adalah: Untuk 1 0 , maka 0 1 1 A S5 1I x 1 1 1
1 1 1 1 1 x1 0 0 0 0 0 x2 0 0 0 0 0 x3 0 0 0 0 0 0 x4 0 0 0 0 0 x5 0 0 0 0 0 x6
kemudian diperoleh sistem persamaan linier: x2 x3 x4 x5 x6 0 x6 x2 x3 x4 x5
... 1
x1 0
... 2
Misalkan x2 s , x3 t , x4 u , x4 v dan s, t , u, v 0 , dengan mencari nilai dari x6 pada persamaan (1) maka diperoleh vektor eigennya adalah: 0 x1 0 0 0 0 s x2 1 0 0 0 x3 0 1 0 0 t s t u v u x4 0 0 1 0 x5 0 0 0 1 v 1 1 1 1 x6 s t u v
basisnya adalah 4 dengan 1 0 .
57
Untuk 2 5 , maka
5 1 1 A S5 2 I x 1 1 1
1
1
1
1
5
0
0
0
0
5
0
0
0
0
5
0
0
0
0
5
0
0
0
0
1 x 1 0 x2 0 x3 0 0 x4 0 x5 x 5 6
kemudian diperoleh sistem persamaan linier:
5 x1 x2 x3 x4 x5 x6 0 x1 5 x2 0 x1 5 x2
x1 5 x3 0 x1 5 x3 x1 5 x4 0 x1 5 x4
x1 5 x5 0 x1 5 x5 x1 5 x6 0 x1 5 x6 Misalkan x1 s dan s 0 , maka diperoleh vektor eigennya adalah: 1 x1 5 1 x2 x3 5 1 x4 x5 5 1 x6 5 1 5
s
1 1 5 5s 5 1 5s 5 5 s 1 5s 5 , basisnya adalah 1 dengan 2 5 . 5 1 5s 5 5 1 5s 5 5
58
Untuk 3 5 , maka
A S5 3 I x
5
1
1
1
1
1
5
0
0
0
1
0
5
0
0
1
0
0
5
0
1
0
0
0
5
1
0
0
0
0
1 x 1 0 x2 0 x3 0 0 x4 0 x5 x 5 6
kemudian diperoleh sistem persamaan linier:
5 x1 x2 x3 x4 x5 x6 0 x1 5 x2 0 x1 5 x2 x1 5 x3 0 x1 5 x3 x1 5 x4 0 x1 5 x4 x1 5 x5 0 x1 5 x5 x1 5 x6 0 x1 5 x6 Misalkan x1 s dan s 0 , dengan mencari nilai dari x2 dan x3 pada persamaan diatas maka diperoleh vektor eigennya adalah:
59 s 1 x1 5 1 x2 x3 5 1 x4 x5 5 1 x6 5 1 5
1 1 5s 5 1 5s 5 s 1 5s 5 1 5s 5 1 5s 5
5 Jadi Spec S5 1
5 5 5 , basisnya adalah 1 dengan 3 5 . 5 5
0 5 4 1
5. Spectrum S 6
S6 :
Representasi matrik adjacent dari graf star dengan n = 5 adalah:
0 1 1 A S6 1 1 1 1
1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Persamaan polynomial karakteristik diperoleh dengan:
60
1 1 A S6 I 1 1 1 1 0
A S6 I
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1 2
1
1
1 0 0 0 0 0
2 2
1
1
1
1
1
2 1
2 1
2 1
2 2 2 4
2 2
2 2
2 1 2 3
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
5 2 6
1
0
2 1
1
2 2
3 2
3 2 5
3
2
2
4 2
0
Nilai eigen diperoleh dengan:
A S 6 I 5 2 6 0
5 6 6 0
1 0 , 2 6 atau 3 6 Basis dari representasi matrik adjacent dari graf star dengan n = 6 adalah: Untuk 1 0 , maka
4 2 6 2
2 5
61 0 1 1 A S6 1I x 1 1 1 1
1 1 1 1 1 1 x1 0 0 0 0 0 0 x2 0 0 0 0 0 0 x3 0 0 0 0 0 0 x4 0 0 0 0 0 0 0 x5 0 0 0 0 0 0 x6 0 0 0 0 0 0 x7
kemudian diperoleh sistem persamaan linier: x2 x3 x4 x5 x6 x7 0 x7 x2 x3 x4 x5 x6
... 1
x1 0
... 2
Misalkan x2 s , x3 t , x4 u , x5 v , x6 w dan s, t , u, v, w 0 , dengan mencari nilai dari x6 pada persamaan (1) maka diperoleh vektor eigennya adalah: 0 x1 0 0 0 0 0 s x2 1 0 0 0 0 x3 0 1 0 0 0 t u x4 s 0 t 0 u 1 v 0 w 0 x5 0 0 0 1 0 v w x6 0 0 0 0 1 1 1 1 1 1 x s t u v w 7
basisnya adalah 5 dengan 1 0 . Untuk 2 6 , maka 6 1 1 A S6 2 I x 1 1 1 1
1
1
1
1
1
6
0
0
0
0
0
6
0
0
0
0
0
6
0
0
0
0
0
6
0
0
0
0
0
6
0
0
0
0
0
kemudian diperoleh sistem persamaan linier:
6 x1 x2 x3 x4 x5 x6 x7 0
x1 6 x2 0 x1 6 x2
1 x1 0 x 2 0 x3 0 x4 0 0 x5 x 0 6 x7 6
62
x1 6 x3 0 x1 6 x3 x1 6 x4 0 x1 6 x4 x1 6 x5 0 x1 6 x5 x1 6 x6 0 x1 6 x6 x1 6 x7 0 x1 6 x7 Misalkan x1 s dan s 0 , maka diperoleh vektor eigennya adalah: 1 6 x1 1 x2 6 x3 1 x4 6 x5 1 x6 6 x 1 7 6 1 6
s
1 1 6s 6 6 1 6s 6 6 1 6s 6 s 6 , basisnya adalah 1 dengan 2 6 . 1 6s 6 6 1 6s 6 6 1 6s 6 6
Untuk 3 6 , maka
A S6 3 I x
6
1
1
1
1
1
1
6
0
0
0
0
1
0
6
0
0
0
1
0
0
6
0
0
1
0
0
0
6
0
1
0
0
0
0
6
1
0
0
0
0
0
kemudian diperoleh sistem persamaan linier:
6 x1 x2 x3 x4 x5 x6 x7 0
1 x1 0 x 2 0 x3 0 x4 0 0 x5 x 0 6 x7 6
63
x1 6 x2 0 x1 6 x2 x1 6 x3 0 x1 6 x3 x1 6 x4 0 x1 6 x4 x1 6 x5 0 x1 6 x5 x1 6 x6 0 x1 6 x6 x1 6 x7 0 x1 6 x7 Misalkan x1 s dan s 0 , maka diperoleh vektor eigennya adalah: s 1 6 x1 1 x2 6 x3 1 x4 6 x5 1 x6 6 x 1 7 6 1 6
1 1 6s 6 1 6s 6 1 6s s 6 1 6s 6 1 6s 6 1 6 s 6
6 Jadi Spec S6 1
6 6 6 , basisnya adalah 1 dengan 3 6 . 6 6 6
0 6 5 1
Teorema Misal S n adalah graf star dengan n N 1 , maka spectrum S n adalah
n Spec S n 1 Bukti
n n 1 1 0n 1
64 Misalkan A Sn adalah matrik adjacent dari graf star Sn , maka 0 1 A Sn 1
1 1 0 0 0 0
Pertama akan ditentukan persamaan karakteristik dari A Sn , yaitu 1 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1
0 1 det A S n I 1
Melalui operasi baris matrik 𝐴 𝑆𝑛 − 𝜆𝐼
1 0 0 1
direduksi menjadi matrik segitiga atas
diperoleh: 0 0 0 0 0
1
1
1
1
(1)( )( 1)
1
1
1
2
1 2 2
2 1
2 1
2
0
2 1
0
1
0
2
2
2
3
2
2
1
2
4
0
0
0
0
0
0
0
2
3
1 2 1 2 2 2 n 2 1 2 n 2 n 1 1
det A Sn I tidak lain adalah hasil perkalian diagonal matrik segitiga atas
tersebut. Jadi persaman polinomial karakteristiknya adalah : det A S n I
2
1 n
n
2
n
65
2
2
1
1 n
n
1
n 1
n
n
n 1
2
n
2
n
2
n
Nilai eigenya adalah:
det A Sn I 1
1 n 1
n 1
n 1
n 1
2
n 0
0 atau 2 n 0
Kemudian diperoleh nilai eigen 1 0n1 atau 2,3 n . Selanjutnya akan ditentukan basis untuk ruang vektor eigen yang bersesuain dengan
1 . Untuk 1 0n1 , kita subsitusikan 1 ke dalam matrik A S n 1 I diperoleh:
0 1 1
1 1 x1 0 0 0 x2 0 0 0 xn 0
Didapatkan sistem persamaan linier: x2 xn 0
... 1
x1 0
... 2
Misalkan x2 s2 ,..., xn1 sn 1 dan s2 ,..., sn1 0 , dengan mencari nilai dari xn pada persamaan (1) maka diperoleh vektor eigennya adalah:
66 0 x1 0 0 0 0 0 s2 x2 1 0 0 0 0 x3 0 1 0 0 0 s3 s4 x4 s2 0 s3 0 s4 1 ... sn 1 0 sn 0 x5 s5 0 0 0 1 0 1 1 1 1 1 x s s s s ... s n n 2 3 4 5
Jadi basis pada matrik diatas adalah m 1 n 1 . Untuk 2 n , vektor eigennya diperoleh dengan mensubsitusikan 2 ke dalam matrik A Sn 2 I , sehingga diperoleh:
n
1
1
1
n
0
1
0
n
1
0
0
1 x1 0 0 x2 0 x3 0 0 n xn 0
Didapatkan sistem persamaan linier:
nx1 x2 x3 ... xn 0 x1 nx2 x1 nx3 x1 nxn Misalkan x1 s dan s 0 , maka diperoleh vektor eigennya adalah:
67
x1 x2 x3 x n
s n s n n s s n n s n
1 n n n n n n
Jadi basis pada matrik diatas adalah m 2 n 1 . Untuk 3 n , vektor eigennya: n 1 1 1
1 n 0 0
1 x1 0 0 0 x2 0 n x3 0 0 0 n xn 0 1
Didapatkan sistem persamaan linier:
nx1 x2 x3 ... xn 0 x1 nx2 x1 nx3 x1 nxn Misalkan x1 s dan s 0 , maka diperoleh vektor eigennya adalah:
68
x1 x2 x3 x n
s n n n n n n
1 n s n n s s n n s n
Jadi basis pada matrik diatas adalah m 3 n 1 .
n Jadi, terbukti bahwa Spec S n 1
n n 1 1 0n 1
C. Spectrum Graf Komplit Bipartisi K m ,n 1. Spectrum K2,2
K2,2 :
Representasi matrik adjacent K2,2 adalah:
0 0 A K 2,2 1 1
0 1 1 0 1 1 1 0 0 1 0 0
Persamaan polynomial karakteristik diperoleh dengan:
69
0 0 A K 2,2 I 1 1
0 1 1 1 0 1 1 0 0 1 0 0 0 1 0 0
0 0 0 1 0 0 0 0 1 0 1 0 0 1 1
0
1
1
0
1
1
det K 2,2 I K 2,2 I 0
0
0
0
2 2
0
0
1
1
1
1
0
2
2 4
1 1 0
2 2 4
2 2
Nilai eigen diperoleh dengan:
K 2,2 I 2 2 4 0
2 4 4 0
1 0 , 2 4 atau 3 4 Basis dari representasi matrik adjacent dari K2,2 adalah: Untuk 1 0 , maka
0 0 K 2,2 1I x 1 1
0 1 1 x1 0 1 1 x2 0 1 0 0 x3 1 0 0 x4
kemudian diperoleh sistem persamaan linier:
x3 x4 0 x3 x4
... 1
x1 x2 0 x1 x2
... 2
Misalkan x2 s , x4 t dan s, t 0 , dengan mencari nilai dari x1 dan x3 persamaan (1) dan (2), maka diperoleh vektor eigennya adalah:
pada
70
x1 s 1 0 x2 s s 1 t 0 x3 t 0 1 0 1 x4 t basisnya adalah 2 dengan 1 0 . Untuk 2 4 , maka
4 0 K 2,2 2 I x 1 1
0
1
4
1
1
4
1
0
1 x1 1 x2 0 0 x3 4 x4
kemudian diperoleh sistem persamaan linier:
4 x1 x3 x4 0 x3 x4 4 x1
4 x2 x3 x4 0 x3 x4 4 x2 x1 x2 4 x3 0 x1 x2 4 x3
x1 x2 4 x4 0 x1 x2 4 x4 Persamaan diatas dapat juga ditulis:
x3 x4
x x x1 x2 dan x1 x2 3 4 4 4
Misalkan x1 x2 s dan s 0 , dengan mencari nilai dari x3 dan x4 pada persamaan diatas, maka diperoleh vektor eigennya adalah:
71
x1 x2 x3 x4
s s 2 s s 4 2 s 4
1 1 2 , basisnya adalah 1 dengan 2 4 . 4 2 4
Untuk 3 4 , maka
K
2,2
3 I x
4 0
0 4
1
1
1
1
1 1 4 0
1 x1 1 x2 0 0 x3 4 x4
kemudian diperoleh sistem persamaan linier:
4 x1 x3 x4 0 x3 x4 4 x1
4 x2 x3 x4 0 x3 x4 4 x2 x1 x2 4 x3 0 x1 x2 4 x3
x1 x2 4 x4 0 x1 x2 4 x4 Persamaan diatas dapat juga ditulis:
x3 x4
x x x1 x2 dan x1 x2 3 4 4 4
Misalkan x1 x2 s dan s 0 , dengan mencari nilai dari x3 dan x4 , maka diperoleh vektor eigennya adalah:
72
s x1 s x2 2 x3 4 x4 2 4
1 1 2 s s 4 2 s 4
basisnya adalah 1 dengan 3 4 .
4 0 4 Jadi Spec K 2,2 1 1 2
2. Spectrum K2,3
K2,3 :
Representasi matrik adjacent K2,3 adalah:
0 0 A K 2,3 1 1 1
0 1 1 1 0 1 1 1 1 0 0 0 1 0 0 0 1 0 0 0
Persamaan polynomial karakteristik diperoleh dengan:
73
0 0 A K 2,3 I 1 1 1
0 1 1 1 1 0 1 1 1 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0
0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 0 0 1 1
0
1
1
1
0
1
1
1
2
2
0
0
0
0
K 2,3 I
0
2
0
2
0
2 4
2 2
2
0
2
0
2
2 6
Nilai eigen diperoleh dengan:
K 2,3 I 3 2 6 0
3 6 6 0
1 0 , 2 6 atau 3 6 Basis dari representasi matrik adjacent dari K2,3 adalah: Untuk 1 0 , maka
0 0 K 2,3 1I x 1 1 1
0 1 1 1 x1 0 1 1 1 x2 1 0 0 0 x3 0 1 0 0 0 x4 1 0 0 0 x5
kemudian diperoleh sistem persamaan linier:
x3 x4 x5 0 x3 x4 x5
... 1
2 4
0
1
1
1
1
1
0
1
0
1
0
0
3 2 6
1 1 0 0
74 ... 2
x1 x2 0 x1 x2
Misalkan x2 s , x4 t , x5 u dan s, t , u 0 , dengan mencari nilai dari x1 dan x3 pada persamaan (1) dan (2), maka diperoleh vektor eigennya adalah:
x1 s 1 0 0 x2 s 1 0 0 x3 t u s 0 t 1 u 1 x4 t 0 1 0 0 0 1 x u 5 basisnya adalah 3 dengan 1 0 . Untuk 2 6 , maka
6 0 K 2,3 2 I x 1 1 1
0
1
1
6
1
1
1
6
0
1
0
6
1
0
0
1 x 1 1 x2 0 x3 0 0 x4 x 6 5
kemudian diperoleh sistem persamaan linier:
6 x1 x3 x4 x5 0 x3 x4 x5 6 x1 6 x2 x3 x4 x5 0 x3 x4 x5 6 x2
x1 x2 6 x3 0 x1 x2 6 x3 x1 x2 6 x4 0 x1 x2 6 x4
x1 x2 6 x5 0 x1 x2 6 x5 Persamaan diatas dapat juga ditulis:
x3 x4 x5
x x x x1 x2 dan x1 x2 3 4 5 6 6
75 Misalkan x1 x2 s dan s 0 , dengan mencari nilai dari x3 , x4 dan x5 , diperoleh vektor eigennya adalah:
x1 x2 x3 x4 x 5
s s 2 s 6 s 2 s 6 2 s 6
1 1 2 6 2 6 2 6
basisnya adalah 1 dengan 2 6 . Untuk 3 6 , maka
K
2,3
3 I x
6
0
1
1
0
6
1
1
1
1
6
0
1
1
0
6
1
1
0
0
1 x 1 1 x2 0 x3 0 0 x4 x 6 5
kemudian diperoleh sistem persamaan linier:
6 x1 x3 x4 x5 0 x3 x4 x5 6 x1 6 x2 x3 x4 x5 0 x3 x4 x5 6 x2
x1 x2 6 x3 0 x1 x2 6 x3 x1 x2 6 x4 0 x1 x2 6 x4
x1 x2 6 x5 0 x1 x2 6 x5 Persamaan diatas dapat juga ditulis:
maka
76
x3 x4 x5
x x x x1 x2 dan x1 x2 3 4 5 6 6
Misalkan x1 x2 s dan s 0 , dengan mencari nilai dari x3 , x4 dan x5 , maka diperoleh vektor eigennya adalah: x1 x2 x3 x4 x 5
s s 2 6 2 6 2 6
1 1 2 s 6 basisnya adalah 1 dengan s 2 s 6 2 s 6
3 6 .
6 0 6 Jadi Spec K 2,3 1 3 1 3. Spectrum K2,4
K2,4 :
Representasi matrik adjacent K2,4 adalah:
0 0 1 A K 2,4 1 1 1
0 1 1 1 1 0 1 1 1 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0
Persamaan polynomial karakteristik diperoleh dengan:
77
0 1 A K 2,4 I 1 1 1
0
1
1
1
1
1
1
1
0
0
1
0
0
1
0
0
1
0
0
0
1 1 0 0 0
1
1
1
1
1
0
1
1
1
1
0
0
2
2
2
K 2,4 I 0
0
2 2
2 2
0
2 2 0
0
0
0
0
0
2 4 2 2
0 0
2
2 6 4 0
K 2,4 I 4 2 8 0
4 8 8 0
1 0 , 2 8 atau 3 8 Basis dari representasi matrik adjacent dari K2,4 adalah: Untuk 1 0 , maka
0 0 1 K 2,4 1I x 1 1 1
0 1 1 1 1 x1 0 1 1 1 1 x2 1 0 0 0 0 x3 0 1 0 0 0 0 x4 1 0 0 0 0 x5 1 0 0 0 0 x6
2 4
2
Nilai eigen diperoleh dengan:
2
2
2 8 2 6
4 2 8
78 kemudian diperoleh sistem persamaan linier:
x3 x4 x5 x6 0 x3 x4 x5 x6
... 1
x1 x2 0 x1 x2
... 2
Misalkan x2 s , x4 t , x5 u, x6 v dan s, t , u, v 0 , dengan mencari nilai dari x1 dan x3 pada persamaan (1) dan (2), maka diperoleh vektor eigennya adalah:
x1 s 1 0 0 0 s x2 1 0 0 0 x3 t u v 0 1 1 1 s t u v t x4 0 1 0 0 x5 0 0 1 0 u v 0 0 0 1 x6 basisnya adalah 4 dengan 1 0 . Untuk 2 8 , maka 8 0 1 1 1 1 x 1 8 1 1 1 1 x2 0 1 8 0 0 0 x3 1 K 2,4 2 I x 0 1 0 8 0 0 x4 1 1 1 0 0 8 0 x5 x 1 1 0 0 0 8 6
kemudian diperoleh sistem persamaan linier:
8 x1 x3 x4 x5 x6 0 x3 x4 x5 x6 8 x1
8 x2 x3 x4 x5 x6 0 x3 x4 x5 x6 8 x2 x1 x2 8 x3 0 x1 x2 8 x3
x1 x2 8 x4 0 x1 x2 8 x4
79
x1 x2 8 x5 0 x1 x2 8 x5 x1 x2 8 x6 0 x1 x2 8 x6 Persamaan diatas dapat juga ditulis:
x x x x x1 x2 dan x1 x2 3 4 5 6 8 8
x3 x4 x5 x6
Misalkan x1 x2 s dan s 0 , maka diperoleh vektor eigennya adalah: x1 x2 x3 x4 x5 x6
s s 2 s 8 2 s s 8 2 s 8 2 s 8
1 1 2 8 2 basisnya adalah 1 dengan 8 2 8 2 8
2 8 .
Untuk 3 8 , maka K 2,4 2 I x
8
0
1
1
1
0
8
1
1
1
1
1
8
0
0
1
1
0
8
0
1
1
0
0
8
1
1
0
0
0
1 x 1 1 x2 0 x3 0 0 x4 0 x5 x 8 6
kemudian diperoleh sistem persamaan linier:
8 x1 x3 x4 x5 x6 0 x3 x4 x5 x6 8 x1 8 x2 x3 x4 x5 x6 0 x3 x4 x5 x6 8 x2
x1 x2 8 x3 0 x1 x2 8 x3
80
x1 x2 8 x4 0 x1 x2 8 x4 x1 x2 8 x5 0 x1 x2 8 x5 x1 x2 8 x6 0 x1 x2 8 x6 Persamaan diatas dapat juga ditulis:
x3 x4 x5 x6
x x x x x1 x2 dan x1 x2 3 4 5 6 8 8
Misalkan x1 x2 s dan s 0 , maka diperoleh vektor eigennya adalah: x1 x2 x3 x4 x5 x6
1 s 1 2 2 s 8 8 2 2 s s 8 8 2 2 s 8 8 2 2 s 8 8 s
basisnya adalah 1 dengan 3 8 .
8 0 8 Jadi Spec K 2,4 1 4 1 4. Spectrum K3,3
K3,3 :
Representasi matrik adjacent K3,3 adalah:
81
0 0 0 A K 3,3 1 1 1
0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0
Persamaan polynomial karakteristik diperoleh dengan:
0 0 A K 3,3 I 1 1 1
0
0
1
1
0
1
1
0
1
1
1
1
0
1
1
0
1
1
0
0
1 1 1 0 0
0
0
1
1
1
0
0
1
1
1
0
0
1
1
1
3
3
K 3,3 I
0
0
0
0
0
0
0
0
0
2
3
0 0
2 6
3 2 3
3 2
0
Nilai eigen diperoleh dengan:
K3,3 I 4 2 9 0
4 9 9 0
1 0 , 2 9 atau 3 9 Basis dari representasi matrik adjacent dari K3,3 adalah: Untuk 1 0 , maka
2 9 2 6
4 2 9
82
0 0 0 K3,3 1I x 1 1 1
0 0 1 1 1 x1 0 0 1 1 1 x2 0 0 1 1 1 x3 0 1 1 0 0 0 x4 1 1 0 0 0 x5 1 1 0 0 0 x6
kemudian diperoleh sistem persamaan linier:
x4 x5 x6 0 x4 x5 x6
... 1
x1 x2 x3 0 x1 x2 x3
... 2
Misalkan x2 s , x3 t , x5 u, x6 v dan s, t , u, v 0 , dengan mencari nilai dari x1 dan x4 pada persamaan (1) dan (2), maka diperoleh vektor eigennya adalah:
x1 s t 1 1 0 0 x2 s 1 0 0 0 x3 t 0 1 0 0 s t u v x4 u v 0 0 1 1 x5 u 0 0 1 0 0 0 0 1 x6 v basisnya adalah 4 dengan 1 0 . Untuk 2 9 , maka
9 0 0 K3,3 2 I x 1 1 1
0
0
1
1
9
0
1
1
0
9
1
1
1
1
9
0
1
1
0
9
1
1
0
0
kemudian diperoleh sistem persamaan linier:
1 x 1 1 x2 1 x3 0 0 x4 0 x5 x 9 6
83
9 x1 x4 x5 x6 0 x4 x5 x6 9 x1 9 x2 x4 x5 x6 0 x4 x5 x6 9 x2
9 x3 x4 x5 x6 0 x4 x5 x6 9 x3 x1 x2 x3 9 x4 0 x1 x2 x3 9 x4
x1 x2 x3 9 x5 0 x1 x2 x3 9 x5 x1 x2 x3 9 x6 0 x1 x2 x3 9 x6 Persamaan diatas dapat juga ditulis:
x4 x5 x6
x1 x2 x3 9
dan x1 x2 x3
x4 x5 x6 9
Misalkan x1 x2 x3 s dan s 0 , maka diperoleh vektor eigennya adalah:
x1 x2 x3 x4 x5 x6
s s s 3 s 9 s 3 s 9 3 s 9
1 1 1 3 9 3 9 3 9
basisnya adalah 1 dengan 2 9 . Untuk 3 9 , maka
84
K
3,3
3 I x
9
0
0
1
1
0
9
0
1
1
0
0
9
1
1
1
1
1
9
0
1
1
1
0
9
1
1
1
0
0
1 x 1 1 x2 1 x3 0 0 x4 0 x5 x 9 6
kemudian diperoleh sistem persamaan linier:
9 x1 x4 x5 x6 0 x4 x5 x6 9 x1
9 x2 x4 x5 x6 0 x4 x5 x6 9 x2 9 x3 x4 x5 x6 0 x4 x5 x6 9 x3
x1 x2 x3 9 x4 0 x1 x2 x3 9 x4 x1 x2 x3 9 x5 0 x1 x2 x3 9 x5
x1 x2 x3 9 x6 0 x1 x2 x3 9 x6 Persamaan diatas dapat juga ditulis:
x4 x5 x6
x1 x2 x3 9
dan x1 x2 x3
x4 x5 x6 9
Misalkan x1 x2 x3 s dan s 0 , maka diperoleh vektor eigennya adalah:
x1 x2 x3 x4 x5 x6
s s s 3 9 3 9 3 9
1 1 1 3 s s 9 3 s 9 3 s 9
85 basisnya adalah 1 dengan 3 9 .
9 0 9 Jadi Spec K 3,3 1 4 1 5. Spectrum K3,4
K3,4 :
Representasi matrik adjacent K3,3 adalah:
0 0 0 A K 3,4 1 1 1 1
0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 1 1 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0
Persamaan polynomial karakteristik diperoleh dengan:
0 0 0 A K 3,4 I 1 1 1 1
0 0 1 1 1 1 1 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1
86 0 0 1 1 1 1
K 3,4 I
1 1 1 0 0 0
0
0
1
1
1
0
1
1
1
0
1
1
1
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
0
0
0
1
1
1
1
0
0
1
1
1
1
0
0
1
1
1
1
3
3
3
3 2 3
3 2 3
3 2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
5 2 12
2 6 3 2
Nilai eigen diperoleh dengan:
K3,4 I 5 2 12 0
5 12 12 0
1 0 , 2 12 atau 3 12 Basis dari representasi matrik adjacent dari K3,4 adalah: Untuk 1 0 , maka
2 9
3 6
6 2
0
2
2 12 2 9
87
0 0 0 K3,4 1I x 1 1 1 1
0 0 1 1 1 1 x1 0 0 1 1 1 1 x2 0 0 1 1 1 1 x3 1 1 0 0 0 0 x4 0 1 1 0 0 0 0 x5 1 1 0 0 0 0 x6 1 1 0 0 0 0 x7
kemudian diperoleh sistem persamaan linier:
x4 x5 x6 x7 0 x4 x5 x6 x7
... 1
x1 x2 x3 0 x1 x2 x3
... 2
Misalkan x2 s , x3 t , x5 u, x6 v, x7 w dan s, t , u, v, w 0 , dengan mencari nilai dari x1 dan x4 pada persamaan (1) dan (2), maka diperoleh vektor eigennya adalah:
x1 s t 1 1 0 0 0 s x2 1 0 0 0 0 x3 0 1 0 0 0 t x4 u v w s 0 t 0 u 1 v 1 w 1 x5 0 0 1 0 0 u v x6 0 0 0 1 0 x w 0 0 0 0 1 7 basisnya adalah 5 dengan 1 0 . Untuk 2 12 , maka
88
12 0 0 K3,4 2 I x 1 1 1 1
0
0
1
1
1
12
0
1
1
1
0
12
1
1
1
1
1
12
0
0
1
1
0
12
0
1
1
0
0
12
1
1
0
0
0
1 x1 1 x 2 1 x3 0 x4 0 0 x5 x 0 6 x7 12
kemudian diperoleh sistem persamaan linier:
12 x1 x4 x5 x6 x7 0 x4 x5 x6 x7 12 x1
12 x2 x4 x5 x6 x7 0 x4 x5 x6 x7 12 x2 12 x3 x4 x5 x6 x7 0 x4 x5 x6 x7 12 x3
x1 x2 x3 12 x4 0 x1 x2 x3 12 x4 x1 x2 x3 12 x5 0 x1 x2 x3 12 x5
x1 x2 x3 12 x6 0 x1 x2 x3 12 x6 x1 x2 x3 12 x7 0 x1 x2 x3 12 x7 Persamaan diatas dapat juga ditulis:
x4 x5 x6 x7
x1 x2 x3 12
dan x1 x2 x3
x4 x5 x6 x7 12
Misalkan x1 x2 x3 s dan s 0 , maka diperoleh vektor eigennya adalah:
89 x1 x2 x3 x4 x5 x6 x 7
s s s 3 12 3 12 3 12 3 12
s s s s s
1 1 1 3 12 basisnya adalah 1 dengan 2 12 . 3 , 12 3 12 3 12
Untuk 3 12 , maka
K3,4 3 I x
12
0
0
1
1
1
0
12
0
1
1
1
0
0
12
1
1
1
1
1
1
12
0
0
1
1
1
0
12
0
1
1
1
0
0
12
1
1
1
0
0
0
kemudian diperoleh sistem persamaan linier:
12 x1 x4 x5 x6 x7 0 x4 x5 x6 x7 12 x1
12 x2 x4 x5 x6 x7 0 x4 x5 x6 x7 12 x2 12 x3 x4 x5 x6 x7 0 x4 x5 x6 x7 12 x3
x1 x2 x3 12 x4 0 x1 x2 x3 12 x4 x1 x2 x3 12 x5 0 x1 x2 x3 12 x5
x1 x2 x3 12 x6 0 x1 x2 x3 12 x6
1 x1 1 x 2 1 x3 0 x4 0 0 x5 x 0 6 x7 12
90
x1 x2 x3 12 x7 0 x1 x2 x3 12 x7 Persamaan diatas dapat juga ditulis:
x4 x5 x6 x7
x1 x2 x3 12
dan x1 x2 x3
x4 x5 x6 x7 12
Misalkan x1 x2 x3 s dan s 0 , maka diperoleh vektor eigennya adalah:
x1 x2 x3 x4 x5 x6 x 7
s s s 3 12 3 12 3 12 3 12
s s s s s
1 1 3 12 3 12 3 12 3 12 1
basisnya adalah 1 dengan 3 12 .
12 0 12 Jadi Spec K 3,4 1 1 5 Teorema Misal Km,n adalah graf komplit bipartisi dengan m, n N 1 , maka spectrum Km,n adalah
mn Spec K m ,n 1
mn mn2 1 0m n 2
Bukti Misalkan A K m ,n adalah matrik adjacent dari Km,n , maka
91 0 0 0 A K m,n 1 1 1 1
0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 1 1 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0
Pertama akan ditentukan persamaan karakteristik dari A K m ,n , yaitu 0
0
1
1
1
1
0
1
1
1
1
1
1
1
1
0
0
det A K m ,n I 1
0
1
1
0
0
0
1
1
1
0
0
0
1
1
1
0
0
0
1
1
1
0
0
0
Melalui operasi baris matrik A K m ,n I direduksi menjadi matrik segitiga atas diperoleh:
92 0 0 0 0 0 0 0
0
0
0
1
1
1
0
0
1
1
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
1 2 m
m
m
2
0
0
0
0
2 1 2 2m
0
0
0
0
0
0
0
0
0
0
det A K m ,n I
2
2
m m
m
2
1 2 3m 2m
0
0
0
2
1 1 1 m 2 m 2 m m 2 m n 2 1 2 mn 2 m n 1 1
tidak lain adalah hasil perkalian diagonal matrik segitiga atas
tersebut. Jadi persaman polinomial karakteristiknya adalah :
det A K m,n I
1 m
m
1 n
2
1 1 m
m
1
mn
n
n
n
2
m n
2
2
2
mn
2
mn
mn 1
m n
m n 2
Nilai eigenya adalah:
det A K m ,n I 1
1
mn
mn2
mn
mn2
2
mn 0
0 atau 2 mn 0
Kemudian diperoleh nilai eigen 1 0m n2 atau 2,3 mn .
2
mn
93 Selanjutnya akan ditentukan basis untuk ruang vektor eigen yang bersesuain dengan
1 .
Untuk 1 0m n2 , kita subsitusikan 1 ke dalam matrik A K m ,n 1 I diperoleh: 0 0 0 1 1 1 1
0 0 1 1 1 1 x1 0 0 0 1 1 1 1 x2 0 0 0 0 1 1 1 1 xm 1 1 1 0 0 0 0 xm 0 1 1 0 0 0 0 y1 0 1 1 0 0 0 0 yn 1 0 1 1 0 0 0 0 yn 0
Didapatkan sistem persamaan linier: y1 y2 yn1 yn 0 x1 x2 xm1 xm 0
Persamaan diatas dapat juga ditulis: y1 y2 yn1 yn dan x1 x2 xn1 xn
maka diperoleh vektor eigennya adalah: x1 x2 ... xm 1 1 1 0 0 x2 x2 1 0 0 0 0 0 1 xm 1 xm 1 0 0 0 0 xm x2 0 x3 ... xm 1 y2 0 ... yn 0 xm y1 y2 yn 1 yn 0 0 0 1 1 0 y2 1 ym 1 0 0 0 y ym 0 0 0 0 1 m
Jadi basis pada matrik diatas adalah m 1 m 1 n 1 m n 2 .
94 Untuk 2 mn , vektor eigennya diperoleh dengan mensubsitusikan 2 ke dalam
matrik A K m ,n 2 I , sehingga diperoleh:
mn 0
0
1
1
1
mn
0
1
1
1
1
1
1
0
0
0
mn
1
1
1
mn
0
0
1
1
1
0
mn
0
1
1
1
0
0
1
1
1
0
0
0
mn
Didapatkan sistem persamaan linier yang pertama:
mnx1 y1 ... yn 0 mnx2 y1 ... yn 0 mnxm y1 ... yn 0 Dapat ditulis dengan
x1 x2 xm 1 xm
y1 y2 ... yn 1 yn mn
Persamaan linier yang kedua:
x1 x2 ... xm 1 xm mn y1 0 x1 x2 ... xm 1 xm mn y2 0 x1 x2 ... xm 1 xm mn yn 0 Dapat ditulis dengan
x1 0 1 x 0 2 0 1 xm 1 0 xm 0 0 y1 0 0 yn 1 0 y 0 n mn 1
95
y1 y2 yn 1 yn
x1 x2 ... xm 1 xm mn
maka diperoleh vektor eigennya adalah: y1 y2 ... yn 1 yn mn y1 y2 ... yn 1 yn mn x1 x2 y1 y2 ... yn 1 yn mn xm 1 xm y1 y2 ... yn 1 yn mn y1 x x ... xm 1 xm 1 2 mn yn 1 y n x x ... x x 1 2 m 1 m mn x1 x2 ... xm 1 xm mn
Dimana s
y1 y2 ... yn 1 yn mn
s s s ms s mn ms mn ms mn s
1 1 m mn m mn m mn 1 1
, jadi basis pada matrik diatas adalah m 2 1 .
Untuk 3 mn , juga menggunakan cara yang sama, sehingga diperoleh
m 3 1
mn Jadi, terbukti bahwa Spec K m ,n 1
mn mn2 1 0m n 2
D. Spectrum pada Graf Lintasan Pn 1. Spectrum P1 P1 :
Representasi matrik adjacent dari graf lintasan dengan n = 1 adalah: A P1 0
96 Persamaan polynomial karakteristik diperoleh dengan:
A P I 0 1
n
det A P1 I A P1 I
Nilai eigen diperoleh dengan: A P1 I 0
0 Basis dari representasi matrik adjacent dari graf lintasan dengan n = 1 adalah: Untuk 0 , maka
A P I x 0x 0 1
Misalkan x s dan s 0 , maka diperoleh vektor eigennya adalah: x s s 1 , basisnya adalah 1 dengan 0 .
0 Jadi Spec P1 1
2. Spectrum P2 P2 :
Representasi matrik adjacent dari graf lintasan dengan n = 2 adalah: 0 1 A P2 1 0
Persamaan polynomial karakteristik diperoleh dengan: 1 0
0 1 1 0 A P2 I n 1 0 0 1 1 det A P2 I A P2 I
0
1 2 2 1 1
1 1 2
97 Nilai eigen diperoleh dengan: A P2 I 2 1 0
1 1 0 1 1 atau 2 1 Basis dari representasi matrik adjacent dari graf lintasan dengan n = 2 adalah: Untuk 1 1 , maka 1
A P I x 1 2
1
1 x1 0 1 x2
kemudian diperoleh sistem persamaan linier:
... 1
x1 x2 0
x1 x2 0 x1 x2 ... 2
Misalkan x1 s dan s 0 , dengan mencari nilai dari x1 dan x2 pada persamaan (1) dan (2) maka diperoleh vektor eigennya adalah:
x1 s 1 s , basisnya adalah 1 dengan 1 1 . 1 x2 s Untuk 2 1 , maka 1 1 x1 0 1 x2
A P I x 1 2
2
kemudian diperoleh sistem persamaan linier: x1 x2 0 x1 x2
Misalkan x1 s dan s 0 , dengan mencari nilai dari x1 dan x2 pada persamaan (1) dan (2) maka diperoleh vektor eigennya adalah:
x1 s 1 s , basisnya adalah 1 dengan 2 1 . 1 x2 s 1 1 Jadi Spec P2 1 1
98
3. Spectrum P3 P3 :
Representasi matrik adjacent dari graf lintasan dengan n = 3 adalah: 0 1 0 A P3 1 0 1 0 1 0
Persamaan polynomial karakteristik diperoleh dengan:
0 1 0 1 0 0 A P3 I n 1 0 1 0 1 0 1 0 1 0 0 0 1 0
det A P3 I A P3 I 0 0
1 1
1
1 0 2 1 1 2 2 0 2 1
0
2 1 0
0 1 0 0
1
2 2
2 2 2 1
Nilai eigen diperoleh dengan:
A P3 I 2 2 0 Atau dapat ditulis dengan A P3 I 2 2 0
2 2 0 1 0, 2 2 atau 3 2 Basis dari representasi matrik adjacent dari graf lintasan dengan n = 3 adalah: Untuk 1 0, maka
99 0 1 0 x1 A P3 1I x 1 0 1 x2 0 0 1 0 x 3
kemudian diperoleh sistem persamaan linier: x1 0
... 1
x1 x3 0 x1 x3 ... 2
x2 0
... 3
Misalkan x3 s dan s 0 , maka diperoleh vektor eigennya adalah: x1 0 0 x2 0 s 0 , basisnya adalah 1 dengan 1 0 . x s 1 3
Untuk 2 2 , maka
2 A P3 2 I x 1 0
1 2 1
0 x1 1 x2 0 2 x3
kemudian diperoleh sistem persamaan linier:
2 x1 x2 0 2 x1 x2 ... 1 x1 2 x2 x3 0
... 2
2 x3 x2 0 2 x3 x2 ... 3 Misalkan x2 s dan s 0 , dengan mencari nilai dari x1 dan x3 pada persamaan (1) dan (2) maka diperoleh vektor eigennya adalah: 1 1 2s 2 2 x1 2 x s s 1 , basisnya adalah 1 dengan 2 2 . 2 x 1 1 3 2s 2 2 2
100 Untuk 3 2 , maka
2 A P3 3 I x 1 0
1 2 1
0 x1 1 x2 0 2 x3
kemudian diperoleh sistem persamaan linier:
2 x1 x2 0 2 x1 x2 ... 1
x1 2 x2 x3 0
... 2
2 x3 x2 0 2 x3 x2 ... 3 Misalkan x2 s dan s 0 , dengan mencari nilai dari x1 dan x3 pada persamaan (1) dan (2) maka diperoleh vektor eigennya adalah: 1 1 2s 2 x1 2 2 x s s 1 , basisnya adalah 1 dengan 3 2 . 2 x 1 1 3 2s 2 2 2
2 Jadi Spec P3 1
0 2 1 1
4. Spectrum P4 P4 :
Representasi matrik adjacent dari graf lintasan dengan n = 4 adalah:
101 0 1 A P4 0 0
1 0 0 0 1 0 1 0 1 0 1 0
Persamaan polynomial karakteristik diperoleh dengan:
1 A P4 I n 0 0
0 A P4 I
1
0
1
1
0
1
1
1
0 0 0 1 0 0
1
0
1 2
1
0
2 2
0
2 1 0
0
0
1
0
0 1 4 3 2 1 2 2 0
2
0
0
0
0
2 2
1
2 1 0
4 3 2 1
4 3 2 1 2 2
Nilai eigen diperoleh dengan: A P4 I 4 3 2 1 0
2
1 2 1 0
1,2
1 5 1 5 atau 3,4 2 2
Basis dari representasi matrik adjacent dari graf lintasan dengan n = 4 adalah: Untuk 1
1 5 , maka: 2
102
1 5 2 1 A P4 1I x 0 0
1
0
1 5
1
2
1
1 5 2
0
0 x1 0 x 2 0 x3 x 1 4 1 5 2
1
kemudian diperoleh sistem persamaan linier:
1 5 x x 1
2
2
0
x1
1 5 x x
x2
1 5 x x
x3
1 5 x
2
2
3
2
2
3
4
4
0
0
0
Misalkan x3 s dan s 0 , maka diperoleh vektor eigennya adalah:
4 1 s 2 1 5 x1 1 5 2 x2 2 x3 1 5 x 4 s 2 s 1 5
basisnya adalah 1 dengan 1
4 1 2 1 5 1 5 2 s s 2 1 5 1 2 1 5
1 5 . 2
103 Untuk 2
1 5 , maka: 2
1 5 2 1 A P I x 4 2 0 0
1
1 5 2 1 0
0 1
1 5 2
0 x1 0 x 2 0 x3 x 1 4 1 5 2
1
kemudian diperoleh sistem persamaan linier:
1 5 x x 1
2
2
0
x1
1 5 x x
x2
1 5 x x
x3
1 5 x
2
2
3
3
2
4
2
4
0
0
0
Misalkan x3 s dan s 0 , maka diperoleh vektor eigennya adalah:
4 s 2 1 1 5 x1 1 5 2 x2 2 x3 1 5 x4 s 2 s 1 5
4 2 1 1 5 1 5 2 s s 2 1 5 1 2 1 5
104 basisnya adalah 1 dengan 1 Untuk 3
1 5 . 2
1 5 , maka: 2
1 5 2 1 A P4 3 I x 0 0
1
0
1 5
1
2 1 0
1 5 2 1
x1 0 x 2 0 x3 x 1 4 1 5 2 0
kemudian diperoleh sistem persamaan linier:
1 5 x x 1
2
2
0
x1
1 5 x x
x2
1 5 x x
x3
1 5 x
2
2
2
2
3
4
3
4
0
0
0
Misalkan x3 s dan s 0 , maka diperoleh vektor eigennya adalah:
105
x1 x2 x3 x4
1 5 2 s s 2 1 5 s 2 s 1 5 4 1 1 5
s 2
basisnya adalah 1 dengan 3 Untuk 4
1 5 2 2 1 5 1 2 1 5 4 1 1 5
1 5 x x 1
2
0
x1
1 5 x x
x2
1 5 x x 2
1 5 . 2
1
0
1 5
1
2 1
1 5
0
kemudian diperoleh sistem persamaan linier:
2
2
2
1 5 , maka:
1 5 2 1 A P4 4 I x 0 0
2
2
3
3
4
0
0
2 1
x1 0 x 2 0 x3 x 1 4 1 5 2 0
106
x3
1 5 x
0
4
2
Misalkan x3 s dan s 0 , maka diperoleh vektor eigennya adalah: x1 x2 x3 x4
1 5 2 s s 2 1 5 s 2 s 1 5 4 1 1 5
s 2
basisnya adalah 1 dengan 4
1 5 Jadi Spec P4 2 1
1 5 2 2 1 5 1 2 1 5 4 1 1 5
2
1 5 . 2
1 5 1 5 1 5 2 1
2 1
2 1
5. Spectrum P5 P5 :
Representasi matrik adjacent dari graf lintasan dengan n = 4 adalah: 0 1 A P5 0 0 0
1 0 0 0 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0
Persamaan polynomial karakteristik diperoleh dengan:
107 1 A P5 I n 0 0 0
0 0 0 0
0
0
1
0
1
1
0
1
0
0
1
1
0
1
0
0
0
2 1 0
0
0
2 1 0
2 2
0
4 4 2 3
0
0
0
0
1
0
0
1
0
2 2 2 1 0
0
0 0 1 0 4 3 2 1 1 2 2 4 2 4 3 0 4 3 2 1 0
1
0
0
0 0 0 1
2
1
0
A P5 I
1
4 3 2 1 2 2
0
0
1
4 4 2 3 4 3 2 1
Nilai eigen diperoleh dengan:
A P5 I 4 4 2 3 0 atau dapat ditulis dengan
A P5 I 5 4 3 3 0
1 1 2 3 0 1 0, 2 1, 3 1, 4 3 atau 5 3 Basis dari representasi matrik adjacent dari graf lintasan dengan n = 5 adalah:
108 Untuk 1 0, maka: 0 1 A P5 1I x 0 0 0
1 0 0 0 x1 0 1 0 0 x2 1 0 1 0 x3 0 0 1 0 1 x4 0 0 1 0 x5
kemudian diperoleh sistem persamaan linier: x2 0 x1 x3 0
x2 x4 0 x3 x5 0 x4 0
Misalkan x5 s dan s 0 , maka diperoleh vektor eigennya adalah: x1 s 1 x2 0 0 x3 s s 1 x4 0 0 1 x s 5
basisnya adalah 1 dengan 1 0 . Untuk 2 1, maka: 1 1 0 0 0 x1 1 1 1 0 0 x2 A P5 2 I x 0 1 1 1 0 x3 0 0 0 1 1 1 x4 0 0 0 1 1 x 5
kemudian diperoleh sistem persamaan linier: x1 x2 0
109 x1 x2 x3 0 x2 x3 x4 0 x3 x4 x5 0
x4 x5 0
Misalkan x5 s dan s 0 , maka diperoleh vektor eigennya adalah: x1 s 1 x2 s 1 x3 0 s 0 x4 s 1 1 x s 5
basisnya adalah 1 dengan 2 1 .
Untuk 3 1, maka: 1 1 A P5 3 I x 0 0 0
1 0 0 0 x1 1 1 0 0 x2 1 1 1 0 x3 0 0 1 1 1 x4 0 0 1 1 x5
kemudian diperoleh sistem persamaan linier: x1 x2 0 x1 x2 x3 0 x2 x3 x4 0 x3 x4 x5 0
x4 x5 0
Misalkan x5 s dan s 0 , maka diperoleh vektor eigennya adalah:
110 x1 s 1 x2 s 1 x3 0 s 0 x4 s 1 1 x s 5
basisnya adalah 1 dengan 3 1 .
Untuk 4 3, maka: 3 1 0 0 0 x 1 3 1 0 0 x2 1 A P5 4 I x 0 1 3 1 0 x3 0 0 1 3 1 x4 0 0 x5 0 0 1 3
kemudian diperoleh sistem persamaan linier:
3 x1 x2 0
x1 3x2 x3 0 x2 3x3 x4 0 x3 3x4 x5 0 x4 3x5 0 Misalkan x5 s dan s 0 , maka diperoleh vektor eigennya adalah: s 1 x1 2 3 3 s 2 3 3 x 2 x3 s 2s 2 x 4 3s 3 x 5 s 1
basisnya adalah 1 dengan 4 3 .
111 Untuk 5 3, maka: A P5 5 I x
3 1
1 3
0
0
1
0
0
1
3
0
0
1
0
0
0
1 3 1
0 x 1 0 x2 0 x3 0 1 x4 x 3 5
kemudian diperoleh sistem persamaan linier:
3 x1 x2 0 x1 3 x2 x3 0 x2 3x3 x4 0 x3 3x4 x5 0 x4 3x5 0 Misalkan x5 s dan s 0 , maka diperoleh vektor eigennya adalah: 3s 3 x1 2 3 3 s 2 3 3 x 2 x3 s 2s 2 x4 3s 3 x 5 s 1
basisnya adalah 1 dengan 5 3 . 3 1 0 1 3 Jadi Spec P5 1 1 1 1 1
Teorema Misalkan f n adalah persamaan polynomial karakteristik graf Pn . Maka :
f1
112
f2 2 1 f n M1n M 2 n , n 3 Dimana M1n dan M 2n merupakan kofaktor kolom satu dan dua dari matrik
A C I . n
n
Bukti Misalkan A Pn adalah matrik adjacent dari Pn , maka
0 1 0 0 0 1 0 1 0 0 0 1 0 A Pn , 0 1 0 0 1 0 1 0 0 0 1 0
1 0 A Pn I n 0 0
1
0
0
1
0
1
0
1
0
0
1
0 0 0 1
1
Persamaan polynomial karakteristik diperoleh dengan:
A Pn I n
1
0
0
0
1
1
0
0
0
1
0
1
0
0
1
1
0
0
0
1
Dari hasil ekspansi kofaktor kolom pada matrik diatas, kita dapatkan:
A Pn I n
1
0
0
0
1
0
0
0
1
1
0
0
1
1
0
0
0
1
0
1
0
1
0
0
1
0
0
1
1
0
1
1
0
0
0
1
0
0
0
1
1
0
113
1
1
0
A Pn I n 0
1
0 1 1 0
1
1
0
0
1
0
0
1
0 0
0
0
1
1
0
0 2
1
1
1
A Pn I n M 1n M 2 n ,
1
1 dengan M 1n 0
0
0
1
0
1
0
0
0 , M 2n 0 1 1 0 1
0
1
1
0
1
0
1
0
1
Definisi Polynomial Chebyshev jenis kedua adalah deret polynomial U n x sedemikian hingga
U n cos
sin n 1 sin
untuk n = 0, 1, 2, … dimana x cos , : 0, dan x : 1,1 . Teorema Misal Pn adalah graf lintasan dengan n N , maka spectrum Pn adalah
k n 2 cos 2 cos 2 cos Spec Pn n 1 n 1 n 1 1 1 1 untuk k = 1,2,3, …, n. Bukti Petunjuk: dari sifat-sifat trigonometri, dengan mudah kita tunjukkan:
114 sin 0 1 sin 1 sin sin 2 2sin cos
sin 4 sin 8cos 4 cos sin 3 sin 4 cos 2 1 3
Ekspansi dari polinom-polinom Chebyshev jenis kedua, didapatkan:
sin 0 1
n 0 U 0 cos
sin
1
U0 x 1
n 1 U1 cos
sin 1 1 sin
2sin cos 2 cos sin
U1 x 2 x
n 2 U 2 cos
sin 2 1 sin
4cos 1
sin 4cos 2 1 sin
2
U 2 x 4x2 1
n 3 U 3 cos
sin 3 1 sin
sin 8cos3 4cos sin
8cos 4cos 3
U 3 x 8 x3 4 x dan seterusnya.
Dari keterangan diatas, U n cos x cos dengan
Pilih x
sin n 1 sin
0 jika memenuhi syarat
k . n 1
k 2 x 2 cos 2 cos , sehingga kita dapatkan: 2 n 1
115 U1 x U 1 2 2 2
U2 x U2 4 1 2 1 2 2 2
U 3 x U 3 8 4 3 2 2 2 2 3
Dan seterusnya, sehingga persamaan polynomial karakteristik pada graf Pn adalah polynomial chebyshev dengan x
2
atau dapat ditulis:
cos Un x Un Un 2 2 Dengan nilai eigennya: k dimana k = 1,2,3, …, n. n 1
2 cos
Selanjutnya akan ditentukan basis untuk ruang vektor eigen yang bersesuain dengan
. 1 0 0 1 1 0 0 1 0 1 0 1 0 0 0 1
0 x1 0 0 x2 0 x3 0 0 x4 0 1 xn 0
Didapatkan sistem persamaan linier:
x1 x2 0 x2 x1
x1 x2 x3 0 x3 x1 x2 2 1 x1
x2 x3 x4 0 x4 x2 x1 x2 3 2 x1
116
x3 x4 x5 0 x5 x3 x4 4 3 2 1 x1 …
xn 2 xn 1 xn 0 xn xn 2 xn 1 Karena setiap elemen dari vektor taknol x dapat dinyatakan dalam x1 , maka basis dari matrik tersebut adalah satu. Jadi terbukti bahwa spectrum pada graf lintasan Pn dengan n N adalah:
k n 2 cos 2 cos 2 cos Spec Pn n 1 n 1 n 1 1 1 1 dimana k = 1,2,3, …, n.
BAB V PENUTUP
A. Kesimpulan Berdasarkan pembahasan, maka beberapa kesimpulan yang dapat diambil adalah sebagai berikut. 1.
Misal 𝐾𝑛 graf komplit order n, maka spectrum graf komplit (𝐾𝑛 ) adalah
2.
(𝑛 − 1) −1 1 (𝑛 − 1) Misal S n adalah graf star dengan n N 1 , maka spectrum S n Spec 𝐾𝑛 =
adalah
n Spec S n 1 3.
n n 1 1 0n 1
Misal Km,n adalah graf komplit bipartisi dengan m dan n bilangan asli lebih dari 1, maka spectrum Km,n adalah
mn Spec K m ,n 1 4.
mn mn2 1 0m n 2
Misal Pn adalah graf lintasan dengan n N , maka spectrum Pn adalah
k n 2 cos 2 cos 2 cos Spec Pn n 1 n 1 n 1 1 1 1 untuk k = 1,2,3, …, n.
B. Saran Berdasarkan penelitian, disarankan kepada peneliti yang lain untuk mengkaji spectrum pada graf-graf yang lain. 117
