Teori Graf Aljabar 2011 [PDF]

Citation preview

TEORI GRAF ALJABAR



Disusun Oleh : DARMAJID (Bab 1 dan Spektrum Graf ) CORRY CORAZON (Graf Reguler dan Graf Garis) ISMAIL (Cycle dan Cut) ANTON (Pohon Pembangun) ALPHAN (The Tree Number) MEILIN (Ekspansi Determinan) NOPENDRI (Partisi-Titik dan Spektrum) SISILIA (Graf Automorfisma) IRA APNI (Vertex-transitive Graphs) MONA (Graf Simetris)



Program Studi Magister Matematika



INSTITUT TEKNOLOGI BANDUNG 2011



Daftar Isi 1 Sekilas Mengenai Graf dan Istilah Dalam Aljabar



1



1.1



Graf Sederhana . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .



1



1.2



Graf Berhingga dan Derajat Titik . . . . . . . . . . . . . . . . . . . . . . .



2



1.3



Jalan, Lintasan, Jarak, dan Diameter . . . . . . . . . . . . . . . . . . . . . .



3



1.4



Subgraf dan Supergraf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .



4



1.5



Keterhubungan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .



4



1.6



Graf Isomofik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .



5



1.7



Kelas-kelas Graf Tertentu . . . . . . . . . . . . . . . . . . . . . . . . . . . .



6



1.8



Sistem Matematika . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .



9



1.9



Istilah Dalam Ruang Vektor . . . . . . . . . . . . . . . . . . . . . . . . . . . 11



1.10 Beberapa Istilah Dalam Matriks . . . . . . . . . . . . . . . . . . . . . . . . 11 1.11 Nilai Eigen, Polinom Minimal, dan Matriks Hermit . . . . . . . . . . . . . . 12 2 Spektrum Graf



17



2.1



Matriks Ketetanggaan dan Spektrum Suatu Graf . . . . . . . . . . . . . . . 17



2.2



Aljabar Ketetanggaan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21



2.3



Hubungan Antara Aljabar Ketetanggan Dengan Spektrum Graf . . . . . . . 27



3 Graf Reguler dan Graf Garis



29



3.1



Pendahuluan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29



3.2



Graf Reguler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29



4 Cycle dan Cut



48



5 Pohon Pembangun



63



i



DAFTAR ISI



ii



6 The Tree Number



72



7 Ekspansi Determinan



85



8 Partisi-Titik dan Spektrum



93



9 Graf Automorfisma



103



9.1



Pendahuluan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103



9.2



Graf Automorfisma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106



10 Vertex-transitive Graphs



110



11 Graf Simetris



116



Daftar Pustaka



122



Bab 1



Sekilas Mengenai Graf dan Istilah Dalam Aljabar 1.1



Graf Sederhana



Suatu graf adalah pasangan tiga terurut G = (V (G), E(G), ψG ) yang terdiri dari himpunan tak kosong V (G) yang dinamakan himpunan titik, himpunan E(G) yang dinamakan himpunan sisi dimana E(G) ∩ V (G) = ∅, dan fungsi keterkaitan ψ(G) yang mengaitkan setiap sisi di E(G) dengan pasangan tak terurut titik di V (G) yang tidak harus berbeda. Selanjutnya, graf G = (V (G), E(G), ψG ) cukup dituliskan graf G saja. Misalkan e adalah suatu sisi dan u, v adalah dua buah titik (tidak harus beda). Sisi e dikatakan terkait dengan u dan v, titik u dan v dikatakan bertetangga, dan u dan v dikatakan titik ujung dari e jika ψG (e) = uv. Selanjutnya, sisi e cukup ditulis sebagai uv jika ψG (e) = uv. Secara grafis, anggota himpunan titik V (G) digambarkan oleh titik, sedangkan anggota himpunan sisi E(G), misalkan e dengan ψG (e) = uv, digambarkan oleh sisi yang mengaitkan u dan v di V (G). Himpunan semua titik yang bertetangga dengan suatu titik v dinotasikan dengan N (v). Suatu sisi yang memiliki titik ujung yang sama disebut loop. Suatu graf G dikatakan memiliki sisi ganda jika terdapat dua sisi berbeda e1 , e2 ∈ E(G) dan dua titik berbeda u, v ∈ V (G) sehingga ψG (e1 ) = uv = ψG (e2 ). G dikatakan graf sederhana jika G tidak memuat loop ataupun sisi ganda.



Perhatikan graf G yang diberikan pada Gambar 1.1. 1



BAB 1. SEKILAS MENGENAI GRAF DAN ISTILAH DALAM ALJABAR



2



V (G) = {v1 , v2 , v3 , v4 , v5 } dan E(G) = {v1 v2 , v1 v3 , v2 v3 , v3 v4 , v3 v5 , v4 v5 }. N (v1 ) = {v2 , v3 }, N (v2 ) = {v1 , v3 }, N (v3 ) = {v1 , v2 , v4 , v5 }, N (v4 ) = {v3 , v5 } dan N (v5 ) = {v3 , v4 }. Graf G merupakan graf sederhana karena G tidak memuat loop ataupun sisi ganda.



Gambar 1.1: Graf G



Gambar 1.2: Graf G1 Graf G1 pada Gambar 1.2 adalah contoh graf yang tidak sederhana. G1 bukan graf sederhana karena G1 memuat loop e1 dengan ψ(e1 = u1 u1 ) dan terdapat sisi ganda e4 dan e5 dimana ψ(e4 ) = u2 u4 = ψ(e5 ).



1.2



Graf Berhingga dan Derajat Titik



Suatu graf dikatakan berhingga jika himpunan titik V (G) berhingga. Banyaknya anggota dari V (G) disebut orde dari G, dinotasikan dengan |V (G)|, sedangkan banyaknya anggota dari E(G) disebut ukuran dari G, dinotasikan dengan |E(G)|. Graf yang memiliki orde 0 atau 1 disebut graf trivial. Graf G pada Gambar 1.1 mempunyai orde 5 dan ukuran 6. Dengan demikian, G bukan graf trivial. Untuk selanjutnya, pada teori graf aljabar ini, graf yang dibicarakan adalah graf berhingga dan graf sederhana.



BAB 1. SEKILAS MENGENAI GRAF DAN ISTILAH DALAM ALJABAR



3



Banyaknya sisi yang terkait pada suatu titik v ∈ V (G) disebut sebagai derajat titik v, dinotasikan dengan dG (v) = d(v). Derajat terkecil pada suatu graf G dinotasikan dengan δ(G), sedangkan derajat terbesar pada graf G dinotasikan dengan ∆(G). Himpunan semua sisi yang terkait pada suatu titik v dinotasikan dengan E(v). Graf G pada Gambar 1.1 mempunyai barisan derajat dG (v1 ) = 2, dG (v2 ) = 2, dG (v3 ) = 4, dG (v4 ) = 2, dG (v5 ) = 2, sedangkan δ(G) = 2 dan ∆(G) = 4.



E(v1 ) = {v1 v2 , v1 v3 }, E(v2 ) = {v1 v2 , v2 v3 },



E(v3 ) = {v1 v3 , v2 v3 , v3 v4 , v3 v5 }, E(v4 ) = {v3 v4 v4 v5 } dan E(v5 ) = {v3 v5 , v4 v5 }.



1.3



Jalan, Lintasan, Jarak, dan Diameter



Suatu jalan di G adalah suatu barisan tak nol dan hingga W = v0 e1 v1 e2 v2 · · · ek vk yang anggotanya berselang-seling titik dan sisi, sehingga, untuk 1 ≤ i ≤ k, titik ujung dari ei adalah vi−1 dan vi . W dikatakan sebagai suatu jalan dari v0 ke vk . Titik-titik v0 dan vk secara berurutan disebut titik awal dan titik akhir dari W, sedangkan v1 , v2 , · · · vk−1 disebut titik − titik dalam dari W . Bilangan bulat k dinamakan panjang dari W. Jika sisi-sisi e1 , e2 , · · · , ek pada jalan W berbeda, maka W disebut trail. Jika v0 , v1 , · · · , vk berbeda, maka W disebut lintasan. Lintasan yang titik awal dan titik akhirnya sama disebut siklus. Dalam referensi lain jalan dengan panjang l dalam graf G dari vi ke vj didefinisikan sebagai barisan berhingga titik-titik dari graf G, vi = u0 , u1 , . . . , ul = vj , sedemikian sehingga ut−1 dan ut bertetangga untuk 1 ≤ t ≤ l. Namun demikian, definisi ini tidaklah bertentangan dengan definisi yang pertama dan kita akan menggunakan definisi ’jalan’ yang terakhir dalam pembahasan pada bab 2.



Graf G pada Gambar 1.1 memuat lintasan dengan panjang 1, 2, 3 dan 4, juga memuat siklus berukuran 3. Himpunan semua lintasan dengan panjang 1 adalah himpunan semua sisi pada G. Himpunan semua lintasan dengan panjang 2 adalah {v1 v2 v3 , v1 v3 v4 , v1 v3 v5 , v2 v1 v3 , v2 v3 v4 , v2 v3 v5 , v3 v4 v5 , v3 v5 v4 , v4 v3 v1 , v4 v3 v2 }. Himpunan semua lintasan dengan panjang 3 adalah {v1 v2 v3 v4 , v1 v2 v3 v5 , v1 v2 v3 v1 , v1 v3 v4 v5 , v1 v3 v5 v4 , v2 v1 v3 v4 , v2 v1 v3 v5 , v2 v3 v4 v5 , v2 v3 v5 v4 , v3 v4 v5 v3 }, dengan v1 v2 v3 v1 dan v3 v4 v5 v3 juga merupakan siklus dengan panjang 3. Himpunan semua lintasan berukuran 4 adalah {v1 v2 v3 v4 v5 , v1 v2 v3 v5 v4 , v2 v1 v3 v4 v5 , v2 v1 v3 v5 v4 }.



BAB 1. SEKILAS MENGENAI GRAF DAN ISTILAH DALAM ALJABAR



4



Jarak dari x ke y, dinotasikan dengan dG (x, y) = d(x, y), adalah panjang jalan terpendek dari x ke y. Adapun diameter dari graf G yang dinotasikan dengan diam(G) dan radius dari graf G yang dinotasikan dengan rad(G) masing-masing didefinisikan sebagai berikut : diam(G) = maxx,y∈V (G) d(x, y), rad(G) = minx∈V (G) (maxy∈V (G) d(x, y)). Graf G pada Gambar 1.1 memiliki barisan jarak d(v1 , v2 ) = 1, d(v1 , v3 ) = 1, d(v1 , v4 ) = 2, d(v1 , v5 ) = 2, d(v2 , v3 ) = 1, d(v2 , v4 ) = 2, d(v2 , v5 ) = 2, d(v3 , v4 ) = 1, d(v3 , v5 ) = 1, d(v4 , v5 ) = 1. Dengan demikian, diam(G) = 2. Untuk menentukan radius dari G, perhatikan bahwa maxy∈V (G) d(v1 , y) = 2, maxy∈V (G) d(v2 , y) = 2, maxy∈V (G) d(v3 , y) = 1, maxy∈V (G) d(v4 , y) = 2 dan maxy∈V (G) d(v5 , y) = 2. Sehingga diperoleh rad(G) = minx∈V (G) {maxy∈V (G) d(vi , y)|i = 1, 2, · · · 5} = min{2, 2, 1, 2, 2} = 1.



1.4



Subgraf dan Supergraf



Misalkan diberikan suatu graf G. Suatu graf H dikatakan subgraf dari G, ditulis H ⊆ G, jika V (H) ⊆ V (G), E(H) ⊆ E(G) dan ψH merupakan pembatasan fungsi ψG pada E(H). Misalkan H suatu subgraf dari G. Maka G disebut supergraf dari H. H 0 disebut subgraf pembangun dari G jika H 0 ⊆ G dan V (H 0 ) = V (G). Pada Gambar 1.3, G1 dan G2 merupakan subgraf dari G karena V (G1) ⊆ V (G), E(G1 ) ⊆ E(G), V (G2 ) ⊆ V (G) dan E(G2 ) ⊆ E(G). G1 subgraf pembangun dari G, sedangkan G2 subgraf dari G namun bukan subgraf pembangun karena G2 tidak memuat v4 . G3 bukan subgraf dari G karena terdapat sisi v2 v4 di G3 yang tidak termuat di G. G4 juga bukan subgraf dari G karena terdapat titik v5 di G4 yang tidak termuat di G.



1.5



Keterhubungan



Dua titik u dan v dikatakan terhubung jika terdapat jalan dari u ke v. G disebut graf terhubung jika setiap pasang titik u dan v di G terhubung. Subgraf terhubung maksimal disebut komponen. Banyaknya komponen pada graf G dinotasikan dengan ωG . Graf G



BAB 1. SEKILAS MENGENAI GRAF DAN ISTILAH DALAM ALJABAR



5



Gambar 1.3: G1 ⊆ G, G2 ⊆ G, G3 * G, G4 * G pada Gambar 1.1 merupakan graf terhubung karena v1 dan v2 termuat pada lintasan v1 v2 , v1 dan v3 termuat pada lintasan v1 v3 , v1 dan v4 termuat pada lintasan v1 v3 v4 , v1 dan v5 termuat pada lintasan v1 v3 v5 , v2 dan v3 termuat pada lintasan v2 v3 , v2 dan v4 termuat pada lintasan v2 v3 v4 , v2 dan v5 termuat pada lintasan v2 v3 v5 , v3 dan v4 termuat pada lintasan v3 v4 , v3 dan v5 termuat pada lintasan v3 v3 dan v4 dan v5 termuat pada lintasan v4 v5 . Contoh graf yang tidak terhubung diberikan pada gambar di bawah ini. Graf G2 pada gambar tersebut tidak terhubung karena tidak ada lintasan yang memuat v1 dan v3 dan ωG2 = 2.



Gambar 1.4: Contoh graf tak terhubung



1.6



Graf Isomofik



Definisi 1.1. T : A → B pemetaan satu-satu jika untuk setiap x, y ∈ A, x 6= y ⇒ T (x) 6= T (y).



BAB 1. SEKILAS MENGENAI GRAF DAN ISTILAH DALAM ALJABAR



6



Definisi 1.2. T : A → B pemetaan pada jika untuk setiap y ∈ B, terdapat x ∈ A, sedemikian sehingga y = T (x). Misalkan G) dan H dua graf. G dikatakan isomorf dengan H, dinotasikan dengan G∼ = H, jika terdapat suatu pemetaan satu-satu pada θ : V (G) → V (H) dan φ : E(G) → E(H) sedemikian sehingga ∀u, v ∈ V (G), uv ∈ E(G) berlaku ψG (e) = uv jika dan hanya jika ψH (φ(e)) = θ(u)θ(v).



Gambar 1.5: G isomorf dengan G0



1.7



Kelas-kelas Graf Tertentu



Misalkan n ≥ 2. Misalkan G suatu graf dengan n titik dan himpunan titiknya adalah {v1 , v2 , · · · vn }. Maka G dikatakan graf lintasan, dinotasikan dengan Pn , jika himpunan titiknya dapat dibentuk menjadi suatu barisan u = v1 , v2 , . . . , vn = v sedemikian sehingga {vi vi+1 = E(G)} , i = 1, 2, ..., n − 1 dimana vi 6= vj untuk i 6= j.



Gambar 1.6: P4



Gambar 1.7: Contoh Hutan



BAB 1. SEKILAS MENGENAI GRAF DAN ISTILAH DALAM ALJABAR



7



Hutan adalah suatu graf sederhana yang tidak memuat siklus. Sedangkan pohon adalah hutan yang terhubung.



Gambar 1.8: Contoh Pohon Suatu graf G dikatakan graf lengkap jika setiap pasang titiknya bertetangga. Graf lengkap berorde n dinotasikan dengan Kn , n ≥ 2. Graf lengkap dengan n = 3 disebut segitiga. Graf G disebut regular jika derajat setiap titinya sama. Graf G(V (G), E(G)) disebut graf k − regular jika dG (v) = k, untuk setiap v ∈ V (G). Graf terhubung 3-regular disebut kubik.



Gambar 1.9: K5 dan graf 3 − regular Graf lingkaran berorde n, untuk n ≥ 3, dinotasikan dengan Cn , adalah graf terhubung 2-regular.



Gambar 1.10: C5



BAB 1. SEKILAS MENGENAI GRAF DAN ISTILAH DALAM ALJABAR



8



Suatu graf G disebut graf bipartit jika V (G) dapat dipartisi menjadi dua buah subhimpunan tak hampa X dan Y sedemikian sehingga untuk setiap sisi di G berlaku salah satu ujungnya berada di X dan ujung lainnya berada di Y . Misalkan banyaknya titik di X adalah m dan banyaknya titik di Y adalah n, dimana m, n ≥ 1, maka graf G dinotasikan dengan Gm,n . Jika setiap titik di X bertetangga dengan setiap titik di Y , maka G disebut graf bipartit lengkap, dinotasikan dengan Km,n .



Gambar 1.11: Contoh graf bipartit dan bipartit lengkap Graf bintang, dinotasikan dengan K1,n , adalah graf bipartit dengan |X| = 1 dan |Y | = n.



Gambar 1.12: Graf bintang K1 , n Graf kipas, dinotasikan dengan Fn , n ≥ 2, adalah graf yang dibentuk dari lintasan Pn dan satu titik x dengan menghubungkan setiap titik pada lintasan Pn dengan titik x. Graf matahari, dinotasikan dengan Sn , untuk n ≥ 3, adalah graf yang dibentuk dari lingkaran Cn dengan cara menambahkan sebuah titik berderajat 1 (pendan) pada setiap titik di Cn .



BAB 1. SEKILAS MENGENAI GRAF DAN ISTILAH DALAM ALJABAR



9



Gambar 1.13: F4



Gambar 1.14: S5 Graf roda, dinotasikan dengan Wn , n ≥ 2, adalah graf yang dibentuk dari lingkaran Cn dan satu titik x dengan menghubungkan setiap titik pada lingkaran Cn dengan titik x.



Gambar 1.15: W5 Teori graf aljabar adalah ilmu yang membicarakan penerapan aljabar pada teori graf. Dalam bab ini dijelaskan beberapa istilah dalam aljabar.



1.8



Sistem Matematika



Definisi 1.3. Gelanggang dengan unsur kesatuan adalah suatu himpunan tak kosong R yang dilengkapi dengan operasi + dan · sehingga 1. ∀a, b, c ∈ R memenuhi (a + b) + c = a + (b + c),



BAB 1. SEKILAS MENGENAI GRAF DAN ISTILAH DALAM ALJABAR



10



2. ∀a, b ∈ R memenuhi a + b = b + a, 3. terdapat 0 ∈ R, sedemikian sehingga ∀a ∈ R memenuhi a + 0 = a, 4. ∀a ∈ R, terdapat −a ∈ R, sedemikian sehingga a + (−a) = 0, 5. ∀a, b, c ∈ R memenuhi (a · b) · c = a · (b · c), 6. terdapat 1 ∈ R, sedemikian sehingga ∀a ∈ R memenuhi a · 1 = 1 · a = a, 7. ∀a, b, c ∈ R memenuhi a · (b + c) = a · b + a · c, dan 8. ∀a, b, c ∈ R memenuhi (a + b) · c = a · c + b · c. Definisi 1.4. Misalkan F adalah himpunan tak kosong. Sistem matematika (F, +, ·) disebut lapangan jika memenuhi kedelapan sifat gelanggang dan ∀a, b ∈ R memenuhi a · b = b · a dan terdapat a−1 ∈ F , sedemikian sehingga ∀a ∈ R memenuhi a · a−1 = 1. Definisi 1.5. Misalkan F adalah lapangan. Himpunan tak kosong V yang dilengkapi dengan operasi penjumlahan dan aksi F pada V disebut ruang vektor atas lapangan F jika 1. ∀a, b, c ∈ V , memenuhi (a + b) + c = a + (b + c), 2. ∀a, b ∈ V , memenuhi a + b = b + a, 3. terdapat 0 ∈ V , sedemikian sehingga ∀a ∈ V , memenuhi a + 0 = a, 4. ∀a ∈ V , terdapat −a ∈ V , sedemikian sehingga a + (−a) = 0, 5. ∀a, b ∈ V , ∀α ∈ F memenuhi α (a + b) = αa + αb, 6. ∀a ∈ V , ∀α, β ∈ F memenuhi (α + β) a = αa + βa, 7. ∀a ∈ V , ∀α, β ∈ F memenuhi (αβ) a = α (βa), dan 8. ∀a ∈ V , dan 1 ∈ F memenuhi 1a = a. Definisi 1.6. Sistem matematika (A, +, ·) disebut aljabar atas lapangan F jika memenuhi 1. (A, +) ruang vektor atas lapangan F , 2. (A, +, ·) gelanggang, dan 3. α (ab) = a (αb) = (αa) b untuk setiap a, b ∈ A, α ∈ F . Contoh dari aljabar yaitu F [X], himpunan polinom dengan variabel X dengan koefisienkoefisiennya berupa unsur lapangan F .



BAB 1. SEKILAS MENGENAI GRAF DAN ISTILAH DALAM ALJABAR



1.9



11



Istilah Dalam Ruang Vektor



Misalkan V adalah ruang vektor atas lapangan F . Misalkan X ⊆ V, X 6= ∅. Unsur z ∈ V adalah kombinasi linier dari X jika terdapat sejumlah hingga unsur X, katakanlah x1 , x2 , . . . , xk dan unsur-unsur a1 , a2 , . . . , ak di F sedemikian sehingga z = a1 x1 + a2 x2 + · · ·+ak xk . Himpunan semua kombinasi linier dari X dituliskan dalam hXi = {a1 x1 +a2 x2 + · · ·+ak xk | a1 , a2 , . . . , ak ∈ F , x1 , x2 , . . . , xk ∈ X, k adalah bilangan asli}. Subhimpunan X dari V dikatakan membangun V jika V = hXi. Subhimpunan X dari V dikatakan bebas linier jika 0 hanya dapat dituliskan sebagai kombinasi linier dari X dengan satu cara yaitu dengan semua koefisien nol. Jika X tidak bebas linier, kita katakan X bergantung linier. Subhimpunan X dari V dikatakan basis jika V = hXi dan X bebas linier. Jika V memiliki basis hingga, kita katakan bahwa V berdimensi hingga. Dalam hal ini, dimensi V , ditulis dimF V , adalah banyaknya unsur sembarang basis bagi V .



1.10



Beberapa Istilah Dalam Matriks



Misalkan An×n = (aij ) adalah suatu matriks atas bilangan kompleks, trace A didefinisikan sebagai penjumlahan semua entri pada diagonal untama yakni a11 + · · · + ann . Selanjutnya, sembarang matriks An×n mempunyai sub matriks utama berukuran (n − k) × (n − k) yaitu sub matriks yang diperoleh dengan menghapus secara bersamaan k buah baris dan k buah kolom yang berindeks sama. Minor utama berukuran k × k adalah determinan dari sub matriks utama berukuran  1 2    1 0 A=   1 1  1 1



k × k. Sebagai contoh, diberikan matriks  1 1   1 1    0 1   1 0



Suatu sub matriks utama dari A yang berukuran 1 × 1 adalah   1 , diperoleh dengan menghapus baris ke 2,3,4, dan kolom ke 2,3,4. Suatu sub matriks utama dari A yang berukuran 2 × 2 adalah   1 2   1 0



BAB 1. SEKILAS MENGENAI GRAF DAN ISTILAH DALAM ALJABAR



12



diperoleh dengan menghapus baris ke 3 dan 4 dan kolom ke 3 dan 4. Suatu sub matriks utama dari A yang berukuran 3 × 3 adalah   0 1 1      1 0 1    1 1 0 diperoleh dengan menghapus baris ke 1 dan kolom ke 1. Contoh sub matriks yang bukan sub matriks utama adalah   2 1 1      1 0 1    1 1 0 diperoleh dengan menghapus baris ke 2 dan kolom ke 1.



1.11



Nilai Eigen, Polinom Minimal, dan Matriks Hermit



Pada bagian ini kita selalu memisalkan A suatu matriks berukuran n × n atas C. Skalar λ dikatakan nilai eigen dari matriks A jika terdapat vektor taknol v ∈ Cn sehingga Av = λv. Vektor v yang memenuhi kesamaan tersebut dinamakan vektor eigen yang bersesuaian dengan nilai eigen λ. P olinom karakteristik dari A, dinotasikan dengan CA (λ) atau dalam buku teori graf aljabar dinotasikan χ(A; λ), adalah bentuk polinom dari det(λI − A). Ternyata, akar-akar dari polinom karakteristik disebut merupakan nilainilai eigen dari matriks A. Misalkan λ adalah suatu nilai eigen dari matriks An×n . Tinjau nilai determinan dari matriks λIn + A. Dapat diperhatikan bahwa koefisien-koefisien λi1 , . . . , λim pada determinan matriks A + diag{λ1 , . . . , λn } sama dengan minor dari A yang diperoleh dengan menghapus secara bersamaan baris dan kolom dengan indeks i1 , . . . , in . Dengan demikian akan diperoleh nilai det(λIn + A) = λn + E1 (A) λn−1 + E2 (A) λn−2 + E3 (A) λn−3 + ... + En (A) , dengan Ei (A) merupakan jumlah dari semua minor dari A yang berukuran i × i. Ini berarti, polinom karakteristik dari suatu matriks A dapat juga dituliskan dalam χ(A; λ) = det(λIn −A) = λn −E1 (A) λn−1 +E2 (A) λn−2 −E3 (A) λn−3 +...+(−1)n En (A) .



BAB 1. SEKILAS MENGENAI GRAF DAN ISTILAH DALAM ALJABAR



13



Polinom MA (x) dikatakan polinom minimal dari A jika MA (x) merupakan polinom monik (koefisien pemukanya 1) tak nol dengan derajat terkecil sehingga MA (A) = 0. Misalkan λ0 > λ1 > · · · > λs−1 adalah nilai eigen yang berbeda. Misalkan χ(A; λ) = (λ − λ0 )m0 (λ − λ1 )m1 · · · (λ − λs−1 )ms−1 . Bilangan mi dinamakan multiplisitas aljabar dari nilai eigen λi ∀i ∈ {0, 1, · · · , s − 1} sedangkan multiplisitas geometri dari λi adalah dimensi dari ruang eigen yang bersesuaian dengan nilai eigen λi yakni suatu ruang vektor yang basisnya merupakan vektor eigen yang bersesuaian denga nilai eigen λi . Selanjutnya, kita akan membahas beberapa sifat mengenai matriks Hermit. Sebelumnya, misalkan z = x + iy adalah suatu bilangan kompleks dengan x, y ∈ R, z = x − iy dikatakan sekawan dari z. Misalkan A = (aij ) suatu matriks atas lapangan kompleks berukuran m × n. Matriks A∗ dinamakan transpos sekawan dari A dimana entri baris ke−i kolom ke−j dari A∗ adalah aji . Definisi 1.7. Misalkan V adalah ruang vektor atas lapangan F dimana F adalah lapangan kompleks. Misalkan pula h fungsi dari V × V ke F . Kita katakan h suatu hasil kali dalam pada V jika memenuhi keempat sifat berikut : 1. h(u, v) = h(v, u), untuk semua u, v ∈ V , 2. h(u + v, w) = h(u, w) + h(v, w), untuk semua u, v, w ∈ V , 3. h(αu, v) = αh(u, v), untuk semua u, v ∈ V , α ∈ F , 4. h(u, u) ≥ 0, untuk semua u ∈ V , dan h(u, u) = 0 jika dan hanya jika u = 0. Hasil kali dalam lebih sering muncul dalam notasi ”operasional” h(u, v) =< u, v >. Ruang vektor yang dilengkapi hasil kali dalam disebut ruang hasil kali dalam. Contoh ruang hasil kali dalam adalah ruang vektor Cn atas lapangan C dengan hasil kali dalam 



  x1 y    1  .   . < x, y >= y ∗ x = y1 x1 + · · · + yn xn untuk setiap x =  ..  , y =  ..    xn yn



    ∈ Cn . 



BAB 1. SEKILAS MENGENAI GRAF DAN ISTILAH DALAM ALJABAR



14



Untuk pembicaraan seterusnya, kita menggunakan definisi hasil kali dalam tersebut. Dua buah vektor x dan y dikatakan orthogonal jika < x, y >= 0. Komplemen orthogonal dari S dalam ruang vektor didefinisikan sebagai subruang S ⊥ = {v ∈ V | < v, w >= 0, ∀w ∈ S}. Definisi 1.8. Suatu matriks An×n dikatakan Hermit atau adjoin dengan dirinya sendiri jika A∗ = A. Matriks An×n yang adjoin dengan diri sendiri (matriks Hermit) akan memiliki sifatsifat antara lain : 1. Nilai-nilai eigen dari A senantiasa real, 2. Vektor-vektor eigen untuk nilai eigen yang berbeda saling orthogonal, 3. Misalkan λ adalah nilai eigen dari A. Multiplisitas geometri λ, ditulis mg (λ), akan bernilai sama dengan multiplisitas aljabar λ, ditulis ma (λ). Bukti. Misalkan λ adalah nilai eigen dari A. Akan terdapat vektor taknol v ∈ Cn sehingga Av = λv. Diperoleh, < v, Av >=< v, λv >= < λv, v > = λ< v, v > = λ < v, v >, dan < Av, v >=< λv, v >= λ < v, v > . Menggunakan fakta A∗ = A akan diperoleh λ < v, v >=< v, Av >= (Av)∗ v = v ∗ A∗ v = v ∗ (Av) =< Av, v >= λ < v, v >, Karena v adalah vektor tak nol maka < v, v >6= 0 sehingga diperoleh λ = λ yakni λ adalah suatu bilangan real yang membuktikan sifat pertama. Selanjutnya diambil sembarang λ 6= µ dua buah nilai eigen di A. Ini berarti terrdapat vektor taknol u, v ∈ Cn sehingga Av = λv dan Au = µu. Akan diperoleh, λ < u, v >=< u, λv >=< u, Av >= (v ∗ A∗ )u = v ∗ (Au) =< Au, v >=< µu, v >= µ < u, v > . Ini berarti, (λ − µ) < u, v >= 0.



BAB 1. SEKILAS MENGENAI GRAF DAN ISTILAH DALAM ALJABAR



15



Karena λ 6= µ diperoleh < u, v >= 0 yakni u dan v saling orthogonal yang membuktikan sifat kedua. Misalkan λ adalah sembarang nilai eigen dari A dan W = E(λ) yakni subruang dengan basis berupa vektor-vektor eigen yang bersesuaian dengan nilai eigen λ. Menurut sifat kedua, jika µ adalah vektor eigen yang berbeda dari λ maka E(µ) ⊆ W ⊥ . Akan ditunjukkan bahwa Az ∈ W ⊥ untuk semua z ∈ W ⊥ yakni W ⊥ invarian terhadap operator A. Diambil sembarang z ∈ W ⊥ dan x ∈ W . Diperoleh, < Az, x >= x∗ Az = x∗ A∗ z =< z, Ax >=< z, λx >= λ < z, x >= 0. Jadi, terbukti bahwa Az ∈ W ⊥ untuk semua z ∈ W ⊥ . Definisikan operator S : W ⊥ → W ⊥ melalui Sv = Av, untuk setiap v ∈ W ⊥ yakni suatu pembatasan operator A pada W ⊥ . Jelas bahwa setiap nilai eigen dari S merupakan nilai eigen dari A. Sebaliknya, setiap nilai eigen A selain λ merupakan nilai eigen bagi S. Misalkan X adalah basis dari W dan Y adalah basis bagi W ⊥ . Kita peroleh  [A]X∪Y = 



λImg (λ)



0



0



[S]Y



 .



Akibatnya, polinom karakteristik CA (x) = (x − λ)mg (λ) CS (x). Karena CS (x) sama sekali tidak memuat faktor x − λ haruslah mg (λ) = ma (λ). Sebagai konsekuensi dari sifat-sifat ini, matriks A akan memiliki basis yang terdiri atas gabungan dari basis-basis vektor eigen sehingga A dapat didiagonalkan. Lebih jauh, jika matriks A tersebut memiliki s ≤ n buah nilai eigen berbeda λ1 , . . . , λs maka polinom minimal dari A dapat terurai atas faktor-faktor linier yakni MA (x) = (x − λ1 ) · · · (x − λs ). Dalam kasus ini, polinom minimal dari A akan memiliki derajat s. Secara umum, untuk matriks An×n atas bilangan kompleks akan memiliki derajat polinom minimal yang tidak melebihi derajat polinom karakteristiknya. Dengan kata lain, polinom minimal An×n akan berderajat paling tinggi n. Hal ini terjadi sebagai akibat dari adanya teorema Cayley-Hamilton. Teorema 1.9. Cayley-Hamilton. Misalkan An×n adalah matriks atas bilangan kompleks. Jika polinom karakteristik dari A adalah CA (x) maka CA (A) = 0.



BAB 1. SEKILAS MENGENAI GRAF DAN ISTILAH DALAM ALJABAR



16



Bukti. Bukti dibuat berdasarkan induksi atas orde matriks n. Untuk n = 1 maka persamaan karakteristik dari A1×1 = (a) adalah CA (x) = x−a. Diperoleh, CA (A) = A−aI1 = A − A = 0. Asumsikan bahwa untuk matriks A(k−1)×(k−1) memenuhi CA (A) = 0. Akan dibuktikan bahwa matriks Ak×k memenuhi CA (A) = 0. Misalkan λ adalah nilai eigen dari A dengan vektor taknol e1 sebagai vektor eigen yang berkorespondensi dengan λ. n Misalkan e1 , e2 , . . . , en diperluas menjadi basis  bagi C . Dalam basis e1 , e2 , . . . , en , ma λ ∗ , dimana A1 adalah suatu matriks persegi triks A akan mempunyai bentuk  0 A1 berukuran (k − 1) × (k − 1) dengan polinom karakteristik CA1 (x). Akibatnya, CA (x) =



(x − λ)|xIn−1 − A1 | = (x − λ)CA−1 (x). Berdasarkan hipotesis induksi, CA1 (A1 ) = 0. Selain itu, Karena e1 merupakan vektor eigen yang bersesuaian dengan nilai eigen λ maka diperoleh (λI − A)e1 = 0 Akibatnya, CA (A) = 0. Dengan demikian berdasarkan induksi terbukti bahwa CA (A) = 0.



Bab 2



Spektrum Graf 2.1



Matriks Ketetanggaan dan Spektrum Suatu Graf



Pada pembahasan bab berikut ini, diasumsikan bahwa graf yang diberikan adalah graf sederhana dan berhingga. Definisi 2.1. Misalkan G suatu graf dengan V (G) = {v1 , . . . , vn }. M atriks ketetanggaan suatu graf G adalah suatu matriks A = A(G) berukuran n × n dimana   1, jika vi dan vj bertetangga; aij =  0, jika v dan v tidak bertetangga. i



j



Berdasarkan definisi di atas, karena aij = aji maka A adalah suatu matriks simetri. Jika A dipandang sebagai matriks atas bilangan kompleks maka A merupakan matriks Hermit. Selanjutnya, karena graf yang dibicarakan adalah graf sederhana maka entri pada diagonal utama bernilai nol sehingga trace dari matriks A bernilai nol. Lebih jauh, karena matriks ketetanggaan A merupakan matriks Hermit maka nilai-nilai eigen dari A merupakan bilangan real. Misalkan λ adalah nilai eigen bagi A maka akan diperoleh fakta bahwa multisiplitas geometri dari λ akan sama dengan multiplisitas aljabar dari λ. Sebagai contoh, matriks ketetanggaan  0    1   A= 1    0  0



dari graf G pada Gambar 1.1 adalah,  1 1 0 0   0 1 0 0    1 0 1 1    0 1 0 1   0 1 1 0 17



BAB 2. SPEKTRUM GRAF



18



Definisi 2.2. Misalkan λ adalah suatu nilai karakteristik dari A dan m(λ) adalah multiplisitas dari λ. Misalkan A(G) memiliki nilai-nilai eigen berbeda λ0 > λ1 > . . . > λs−1 dengan multiplisitas masing-masing m(λ0 ), m(λ1 ), . . . , m(λs−1 ). Spektrum dari graf G, dinotasikan dengan Spec G, dapat dituliskan dalam bentuk berikut ini.   λ0 λ1 ··· λs−1  Spec G =  m(λ0 ) m(λ1 ) · · · m(λs−1 ) . Berikut ini diberikan contoh penentuan spektrum dari suatu graf lengkap K4 . Matriks



Gambar 2.1: K4 ketetanggaan dari K4 adalah 



0 1    1 0 A(K4 ) = A =    1 1  1 1



1 1







  1 1  .  0 1   1 0



Selanjutnya, nilai-nilai eigen dari A didapat dengan mencari akar-akar persamaan karak-



BAB 2. SPEKTRUM GRAF



19



teristik matriks A sebagai berikut.   λ −1 −1 −1      −1 λ −1 −1    det(λI − A) = det    −1 −1 λ −1    −1 −1 −1 λ     λ −1 −1 −1 −1 −1         = λdet  −1 λ −1  − (−1)det  −1 λ −1      −1 −1 λ −1 −1 λ    −1 λ −1 −1 λ −1       + (−1)det  −1 −1 −1  + (−1)det  −1 −1 λ    −1 −1 λ −1 −1 −1



    



= λ(λ3 − 3λ − 2) + (−λ2 − 2λ − 1) − (λ2 + 2λ + 1) + (−λ2 − 2λ − 1) = λ4 − 6λ2 − 8λ − 3 = (λ − 3)(λ + 1)3 . Dengan demikian, spektrum dari K4 adalah  Spec K4 = 



3 −1 1



3



 .



Biasanya, suatu nilai karakteristik dari matriks ketetanggaan A = A(G) disebut sebagai nilai karakteristik dari graf G. Demikian juga dengan polinom karakteristik dari A(G) biasanya disebut sebagai polinom karakteristik dari graf G yang dinotasikan dengan χ(G; λ). Misalkan Γ graf sederhana dengan |V (Γ)| = n. Misalkan juga polinom karakteristik dari Γ adalah χ (Γ; λ) = λn + c1 λn−1 + c2 λn−2 + ... + cn . Proposisi 2.3. Koefisien-koefisien polinom karakteristik dari graf Γ memenuhi 1. c1 = 0, 2. −c2 adalah banyaknya sisi pada graf Γ yakni −c2 = E(Γ), 3. −c3 adalah dua kali banyaknya segitiga pada graf Γ.



BAB 2. SPEKTRUM GRAF



20



Bukti. 1. Misalkan A(Γ) = An×n adalah matriks ketetanggan graf Γ. Karena Γ adalah graf sederhana, maka semua entri diagonal utama pada matriks A(Γ) barnilai 0. Akibatnya, semua submatriks utama dari A yang berukuran 1×1 berupa matriks nol sehingga julmlah determinan semua matriks utama berukuran 1 × 1 tersebut adalah 0. Oleh karena itu, c1 = −E1 (A) = 0. 2. bahwa submatriks utama dari A yang berukuran 2×2   hanya  akan berbentuk      Perhatikan 0 1 0 0 0 1 0 0  pada A  dan  . Misalkan submatriks utama   atau   1 0 0 0 1 0 0 0 masing-masing sebanyak p dan q buah. Diperoleh, 0 0 0 1 +q = p.0 + q(−1) = −q. c2 = E2 (A) = p 0 0 1 0  Tetapi, submatriks 



0 1







 merupakan representasi dari pasangan titik yang bertetangga 1 0 yakni sebuah sisi pada graf Γ. Dengan demikian, banyaknya sisi pada graf Γ adalah E(Γ) = q. Lebih jauh, diperoleh −c2 = −(−q) = q = E(Γ). 







0 0 0     3. Submatriks utama A yang berukuran 3×3 merupakan salah satu dari bentuk  0 0 0 ,   0 0 0             0 1 0 0 0 1 0 0 0 0 1 1 0 0 1 0 1 0                          1 0 0 ,  0 0 0 ,  0 0 1 ,  1 0 0 ,  0 0 1 ,  1 0 1  atau             0 0 0 1 0 0 0 1 0 1 0 0 1 1 0 0 1 0   0 1 1 0 1 1     . Perhatikan bahwa 1 0 1 = 2 dan determinan dari submatriks utama  1 0 1    1 1 0 1 1 0 bentuk lainnya   bernilai nol. Misalkan submatriks utama ukuran 3 × 3 yang berbentuk 0 1 1      1 0 1  ada sebanyak p buah sedangkan total banyak dari submatriks utama 3 × 3   1 1 0 selain itu  adalah q buah. Akibatnya, E3 (A) = p(2) + q(0) = 2p. Tetapi, submatriks 0 1 1     utama  1 0 1  merupakan representasi dari 3 buah titik yang saling bertetangga   1 1 0



BAB 2. SPEKTRUM GRAF



21



yakni sebuh segitiga pada graf Γ. Dengan demikian, −c3 = −(−E3 ) = 2p = 2 banyak segitiga pada graf Γ.



Gambar 2.2: graf G 



0 1 0 1



   1 0 Contoh 2.4. Matriks ketetanggaan dari graf G adalah A = A (G) =    0 1  1 1 Adapun polinom karakteristik dari graf G merupakan polinom karakteristik dari







  1 1  .  0 1   1 0 matriks



A yakni χ (G; λ) = λ4 − 5λ2 − 4λ. Koefisien dari λ3 adalah 0, banyaknya sisi adalah 5, dan banyaknya segitiga adalah 2. Ternyata bebrrapa koefisien dari polinom karakteristik suatu graf memberikan informasi mengenai graf tersebut dalam hal banyak sisi dan banyak segitiga walaupun draf tersebut tidak digambarkan secara visual.



2.2



Aljabar Ketetanggaan



Misalkan A adalah suatu matriks persegi berukuran n × n atas C. Didefinisikan himpunan polinom dengan variabel berupa matriks A dan koefisien bilangan kompleks yakni n o C[A] = a0 + a1 A + · · · + ak Ak |ai ∈ C, k ≥ 0, k ∈ Z .



BAB 2. SPEKTRUM GRAF



22



Didefinisikan operasi penjumlahan, perkalian, dan aksi skalar oleh C pada C[A] sebagai berikut. + : C[A] × C[A] → C[A] (p(A), q(A)) 7→ p(A) + q(A), ∗ : C[A] × C[A] → C[A] (p(A), q(A)) 7→ p(A)q(A), · : C × C[A] → C[A] (c, q(A)) 7→ cq(A),



dimana untuk setiap c ∈ C, p(A), q(A) ∈ C[A] dengan p(A) = p0 + p1 A + · · · dan q(A) = q0 + q1 A + · · · hampir semua pi , qj ∈ C, i, j ∈ Z bernilai nol memenuhi aturan : p(A) + q(A) = r0 + r1 A + · · · dengan ri = pi + qi , ∀i ∈ Z, p(A)q(A) = r0 + r1 A + · · · dengan ri = pi q0 + pi−1 q1 + · · · + p1 qi−1 , ∀i ∈ Z, cq(A) = r0 + r1 A + · · · dengan ri = cqi , ∀i ∈ Z, dan untuk setiap w ∈ C dan matriks A = (aij ) perkalian wA didefinisikan dengan baik komponen demi komponen, yakni wA = (bij ) dengan bij = waij . Proposisi 2.5. Himpunan C[A] dengan operasi penjumlahan, perkalian, dan perkalian dengan skalar yang telah didefinisikan sebelumnya membentuk aljabar atas lapangan bilangan kompleks C Bukti. Diambil sembarang p(A), q(A), r(A) ∈ C[A] dengan p(A) = p0 + p1 A + · · · , q(A) = q0 + q1 A + · · · , dan r(A) = r0 + r1 A + · · · hampir semua pi , qj , rk ∈ C, i, j, k ∈ Z bernilai nol. 1. Ditunjukkan berlakunya sifat komutatif terhadap penjumlahan p(A) + q(A) = (p0 + q0 ) + (p1 + q1 )A + · · · = (q0 + p0 ) + (q1 + p1 )A + · · · = q(A) + p(A) 2. Ditunjukkan berlakunya sifat assosiatif terhadap penjumlahan



BAB 2. SPEKTRUM GRAF



23



p(A) + (q(A) + r(A)) = p0 + p1 + · · · + ((q0 + r0 ) + (q1 + r1 )A + · · · ) = (p0 + q0 + r0 ) + (p1 + q1 + r1 )A + · · · = ((p0 + q0 ) + (p1 + q1 )A + · · · ) + p0 + p1 + · · · = (p(A) + q(A)) + r(A) 3. Terdapat o(A) ∈ C[A] dimana semua koefisien oi = 0 sehingga untuk setiap p(A) ∈ C[A] dengan p(A) = p0 + p1 A + · · · dan hampir semua pi ∈ C, i ∈ Z bernilai nol berlaku p(A) + o(A) = (p0 + 0) + (p1 + 0)A + · · · = p0 + p1 A + · · · = p(A), dan o(A) + p(A) = (0 + p0 ) + (0 + p1 )A + · · · = p0 + p1 A + · · · = p(A). 4. Untuk setiap p(A) ∈ C[A] dengan p(A) = p0 + p1 A + · · · dan hampir semua pi ∈ C, i ∈ Z bernilai nol, terdapat p(A) ∈ C[A] dimana pi = −pi , ∀i ∈ Z sedemikian sehingga p(A) + p(A) = (p0 + p0 ) + (p1 + p1 )A + · · · = (p0 − p0 ) + (p1 − p1 )A + · · · = o(A), dan p(A) + p(A) = (p0 + p0 ) + (p1 + p1 )A + · · · = (−p0 + p0 ) + (−p1 + p1 )A + · · · = o(A). Diambil sembarang p(A), q(A), rA ∈ C[A] dengan p(A) = p0 + p1 A + · · · = q(A) = q0 + q1 A + · · · =



∞ X



qj Aj , dan r(A) = r0 + r1 A + · · · =



j=0



∞ X k=0



pi , qj , rk ∈ C, i, j, k ∈ Z bernilai nol. 5. Ditunjukkan berlakunya sifat distributif kiri  ! ∞ ∞ X X p(A) [q(A) + r(A)] = pi Ai  (qj + rj )Aj  i=0



=



i=0



=



j=0



∞ i X X



!



pi−k (qk + rk ) Ai



k=0



∞ i X X i=0



!



k=0



pi−k qk +



i X k=0



= p(A)q(A) + p(A)r(A) 6. Ditunjukkan berlakunya sifat distributif kanan



! pi−k rk



! A



i



∞ X



p i Ai ,



i=0



pk Ak hampir semua



BAB 2. SPEKTRUM GRAF [p(A) + q(A)] r(A) =



24 ∞ X (pi + qi )Ai



! 



i=0



= =



rj Aj  !



pi−k rk +



k=0



i X



! Ai !



(pi−k + qi−k )rk



k=0



∞ i X X i=0







j=0



∞ i X X i=0



∞ X



qi−k rk



! i



A



k=0



= p(A)r(A) + q(A)r(A) 7. Ditunjukkan berlakunya sifat assosiatif terhadap perkalian ! ∞ !  j ∞ X X X p(A)(q(A)r(A)) = p i Ai  qj−k rk Aj  = = = =



i=0 ∞ X



j X



j=0 ∞ X



l=0 k=0 j X l X



j=0 ∞ X



j X j X



j=0



k=0 l=k



j=0 l X



!! Aj



ql−k rk !



Aj



pj−l ql−k rk



l=0 k=0



j X j−k ∞ X X j=0



k=0



! Aj



pj−l ql−k rk ! pj−l−k ql rk



Aj



k=0 l=0



j j−k ∞ X X X



!



!



p(j−k)−l ql rk Aj j=0 k=0 l=0  ! ! ∞ ∞ i X X X = pi−l ql Ai  rj Aj 



=



i=0



l=0



j=0



= (p(A)q(A))r(A). 8. Terdapat i(A) = 1 ∈ C[A] sehingga untuk setiap p(A) ∈ C[A] dengan p(A) = p0 + p1 A + · · · dan hampir semua pi ∈ C, i ∈ Z bernilai nol berlaku p(A)i(A) = (p0 + p1 A + · · · ) (1) = p0 + p1 A + · · · = p(A), dan i(A)p(A) = (1) (p0 + p1 A + · · · ) = p0 + p1 A + · · · = p(A). Karena C[A] memenuhi sifat 1 sampai 8 maka C[A] disebut sebagai gelanggang. Selanjutnya, diambil sembarang p(A), q(A) ∈ C[A] dengan p(A) = p0 + p1 A + · · · dan q(A) = q0 + q1 A + · · · hampir semua pi , qj ∈ C, i, j, k ∈ Z bernilai nol dan diambil sembarang 1, w, z ∈ C. a. Ditunjukkan berlakunya sifat distributif skalar terhadap vektor



BAB 2. SPEKTRUM GRAF



25



w(p(A) + q(A)) = w ((p0 + p1 A + · · · ) + (q0 + q1 A + · · · )) = w(p0 + p1 A + · · · ) + w(q0 + q1 A + · · · ) = wp(A) + wq(A) b. Ditunjukkan berlakunya sifat distributif vektor terhadap skalar (w + z)p(A) = (w + z)(p0 + p1 A + · · · ) = w(p0 + p1 A + · · · ) + z(p0 + p1 A + · · · ) = wp(A) + zp(A) c. (wz)p(A) = wz(p0 + p1 A + · · · ) = w(z(p0 + p1 A + · · · ))w(zp(A)). d. 1p(A) = 1(p0 + p1 A + · · · ) = p0 + p1 A + · · · = p(A) Karena C[A] memenuhi sifat 1 sampai 4 dan sifat a sampai d maka C[A] disebut sebagai ruang vektor. Akhirnya, diambil sembarang p(A), q(A) ∈ C[A] dengan p(A) = p0 + p1 A + · · · dan q(A) = q0 + q1 A + · · · hampir semua pi , qj ∈ C, i, j, k ∈ Z bernilai nol dan diambil sembarang z ∈ C sedemikian sehingga w(p(A)q(A)) = w ((p0 + p1 A + · · · )(q0 + q1 A + · · · )) = (w(p0 + p1 A + · · · ))(q0 + q1 A + · · · ) = (wp(A))q(A) = (w(p0 + p1 A + · · · ))(q0 + q1 A + · · · ) = (wp0 + wp1 A + · · · )(q0 + q1 A + · · · ) = (p0 w + p1 Aw + · · · )(q0 + q1 A + · · · ) = (p(A)w)q(A) Definisi 2.6. Misalkan Γ adalah suatu graf dengan V (Γ = n). Aljabar ketetanggaan dari graf Γ, dinotasikan A(Γ), adalah aljabar dari polinom dengan variabel berupa matriks An×n dan koefisien bilangan kompleks, dimana A merupakan matriks ketetanggaan dari graf Γ. Misalkan persamaan karakteristik dari graf Γ dengan V (G) = n dan matriks ketetanggaan An×n adalah C( A)(x) = xn + c1 xn−1 + · · · + cn . Berdasarkan teorema Cayley-Hamilton, An + c1 An−1 + · · · + cn In = CA (A) = 0.  Ini berarti matriks nol dituliskan sebagai kombinasi linier dari In , A, A2 , . . . , An dengan tidak semua skalarnya nol yakni koefisien dari An . Dengan demikian, himpunan



BAB 2. SPEKTRUM GRAF 26  In , A, A2 , . . . , An yang memiliki unsur sebanyak n + 1 buah tidaklah bebas linier. Akibatnya, dimensi dari A(Γ) maksimal n. Berikutnya akan dibahas tentang hubungan antara banyaknya jalan pada suatu graf dengan matriks ketetanggaannya yang disajikan pada lema berikut. Lema 2.7. Misalkan Γ adalah suatu graf sederhana dengan V (G) = n dan matriks ketetanggaan A. Banyaknya jalan dengan panjang l dari vi ke vj di Γ adalah entri (Al )ij dari matriks Al . Bukti. Pembuktian dilakukan dengan menggunakan induksi. Untuk k = 0 diperoleh A0 = In . Dapat diperhatikan bahwa entri-entri diagonal utama dari In adalah 1 yang menyatakan banyaknya jalan dengan panjang 0 dari vi ke vi sedangkan entri selain diagonal utama bernilai nol yang menyatakan banyaknya jalan dengan panjang 0 dari vi ke vj dengan i 6= j. Ini berarti Lema tersebut benar untuk kasus k = 0. Untuk k = 1 diperoleh A1 = A. Entri-entri matriks A pada diagonal utama bernilai nol yang berarti tidak ada jalan dengan panjangnya 1 dari vi ke vi sedangkan untuk i 6= j, entri selain diagonal utama bernilai 1 jika vi bertetangga dengan vj yang berarti terdapat sebuah jalan dengan panjang 1 dari vi ke vj dan bernilai 0 jika vi dan vj yang berarti tidak terdapat jalan dengan panjang 1 dari vi ke vj . Jadi, lema juga benar untuk kasus k = 1. Asumsikan lema benar untuk k = L. Akan dibuktikan lemma ini juga benar untuk k = L + 1. Diambil sebarang vi , vj ∈ V Γ. Untuk mendapatkan jalan dengan panjang L + 1 dari vi ke vj , tinjau semua titik yang bertetangga dengan vj . Untuk setiap vh vj ∈ E(Γ),
banyaknya jalan dengan panjang L dari vi ke vh adalah AL ih , yaitu entri baris ke-i kolom ke-h pada matriks AL . Berdasarkan hal tersebut, banyaknya jalan dengan panjang X L + 1 dari vi ke vj adalah )(AL )ih . Karena entri ahj bernilai 1 jika vh dan vj (vh vj )∈E(Γ



bertetangga dan bernilai 0 jika vh dan vj tidak bertetangga maka bentuk sigma terakhir dapat diperumum untuk semua titik v ∈ V (Γ) menjadi n X



(AL )ih ahj = (AL A)ij = (AL+1 )ij .



h=1



Dengan demikian, dapat diperhatikan bahwa banyaknya jalan dari vi ke vj yang pan
jangnya L + 1 adalah entri AL+1 ij . Jadi, lema terbukti berdasarkan induksi matematika.



BAB 2. SPEKTRUM GRAF



2.3



27



Hubungan Antara Aljabar Ketetanggan Dengan Spektrum Graf



Pada pembahasan ini, graf Γ selalu diasumsikan sederhana dan mempunyai berhingga titik V (Γ) = {v1 , . . . , vn }. Proposisi 2.8. Misalkan Γ graf terhubung dengan aljabar ketetanggaan A(Γ) dan diameter k. Dimensi dari A(Γ) minimal k + 1. Bukti. Diambil sembarang x, y ∈ V Γ dengan d(x, y) = k. Misalkan x = w0 , w1 , ..., wk = y adalah jalan dari x ke y dengan panjang k. Karena diam(Γ) = k maka tidak ada jalan dari x ke y dengan panjang kurang dari k. Karena Γ terhubung maka untuk setiap i ∈ {1, 2, ..., k}, terdapat paling sedikit 1 buah jalan dengan panjang i dari w0 ke wi tetapi bukan merupakan jalan terpendek. Misalkan saja w0 = vk dan wi = vl . Ak


ibatnya, Ai kl 6= 0 dan (In )kl = (A)kl = A2 kl = ... = Ai−1 kl = 0. Mengingat entri baris k kolom l tersebut, Ai tidak akan bisa dinyatakan sebagai kombinasi linier   dari In , A, A2 , ..., Ai−1 . Akibatnya, In , A, A2 , ..., Ai merupakan himpunan bebas linier. Karena hal tersebut berlaku untuk sembarang i ∈ {1, 2, ..., k} maka dapat dipilih i terbesar yakni i = k untuk mendapatkan In , A, A2 , ..., Ak ∈ A (Γ) bebas linier. Ini berarti paling sedikit k + 1 matriks tersebut dapat menjadi unsur-unsur suatu basis bagi A (Γ). Dengan demikian, dimensi dari A (Γ) minimal k + 1. Terdapat suatu hubungan antara aljabar ketetanggaan dengan spektrum suatu graf Γ. Misalkan An×n , matriks ketetanggaan dari graf Γ, memiliki s buah nilai eigen yang berbeda. Akan ditunjukkan bahwa dimA (Γ) = s. Karena A adalah suatu matriks Hermit maka polinom minimal dari A mempunyai derajat s. Misalkan polinom minimal dari A adalah MA (x) = xs + c1 xs−1 + · · · + cn . Ini berarti, As + c1 As−1 + · · · + cn In = MA (A) = 0. Perhatikan bahwa 0 tidak dapat dinyatakan sebagai kombinasi linier dari  s s−1 A , A , . . . , A, In dengan semua skalarnya nol karena koefisien dari As bernilai 1. Akibatnya, subhimpunan A (Γ) yang memuat s + 1 unsur tidak bebas linier. Andaikan  himpunan As−1 , . . . , A, In ⊆ A(Γ) tidak bebas linier. Akibatnya, terdapat skalar ki 6= 0 dimana i diasumsikan sebagai indeks terbesar sedemikian sehingga ks−1 As−1 + · · · + k1 A + k0 In = 0 dengan kj ∈ C. Dengan membuang suku bernilai nol dengan indeks j > i dan membagi kedua ruas dengan ki akan diperoleh MA0 (A) = Ai +



ki−1 i−1 ki A



+ ··· +



BAB 2. SPEKTRUM GRAF k1 ki A



+



k0 ki In



28



= 0. Akibatnya terdapat polinom dengan Mx0 (A) dengan derajat i kurang



dari s sehingga MA0 (A) = 0. Kontradiksi dengan polinom minimal MA (A) berderajat s  Jadi, As−1 , . . . , A, In ⊆ A(Γ) dengan banyaknya unsur s buah bebas linier. Akibatnya dimA (Γ) = s. Akibat 2.9. Suatu graf terhubung Γ dengan diameter k memiliki paling sedikit k + 1 buah nilai eigen yang berbeda. Bukti. Karena diam(Γ) = k maka manurut proposisi 2.8, dim(A(Γ)) ≥ k + 1. Andaikan matriks ketetanggaan A = A(Γ) mempunyai paling banyak k nilai eigen berbeda. Karena A adalah suatu matriks Hermit maka polinom minimal dari A mempunyai derajat s dengan s ≤ k. Misalkan polinom minimal dari A adalah MA (x) = xs +c1 xs−1 +· · ·+cn . Ini berarti, As +c1 As−1 +· · ·+cn In = MA (A) = 0. Perhatikan bahwa 0 tidak dapat dinyatakan sebagai  kombinasi linier dari As , As−1 , . . . , A, In dengan semua skalarnya nol karena koefisien dari As bernilai 1. Akibatnya, subhimpunan A (Γ) yang memuat s + 1 unsur tidak bebas linier sehingga dim(A (Γ)) ≤ s ≤ k < k + 1. Kontradiksi dengan dim(A(Γ)) ≥ k + 1. Dengan demikian, graf Γ memiliki paling sedikit k + 1 nilai eigen berbeda.



Bab 3



Graf Reguler dan Graf Garis 3.1



Pendahuluan



U . ntuk setiap lapangan F , polinom dalam x adalah ekspresi dalam bentuk an X n + an−1 X n−1 + ... + a1 X + a0 dengan a0 , a1 , ..., an ∈ F . P.olinom monik adalah polinom dalam bentuk X n + an−1 X n−1 + ... + a1 X + a0 dengan a0 , a1 , ..., an ∈ F . M . isalkan A adalah matriks berukuran nxn. MA (x) dikatakan polinom minimum dari A jika MA (x) adalah polinom monik dengan derajat terkecil sehingga MA (A) = 0. M . isalkan A adalah matriks berukuran nxn. Polinom karakteristik dari A adalah CA (x) = det(xIn − A).



3.2



Graf Reguler



Sebuah graf disebut graf reguler berderajat k (atau k-reguler) jika setiap titiknya berderajat k. Proposisi 3.1. Misalkan Γ adalah graf reguler berderajat k, maka 1. k adalah nilai eigen dari Γ 2. Jika Γ terhubung maka multiplisitas dari k adalah 1 3. Untuk setiap nilai eigen λ dari Γ, diperoleh |λ| ≤ k. 29



BAB 3. GRAF REGULER DAN GRAF GARIS



30



Bukti. Misalkan Γ adalah graf reguler dengan n titik dan berderajat k. 1. Misalkan A adalah matriks ketetanggaan dari Γ.   1, jika vi dan vj bertetangga; (A)ij =  0, jika v dan v tidak bertetangga. i



j







 1    .  Pilih u =  .. . Karena Γ adalah graf   1 matriks A memiliki k buah entri bernilai 1.    1     ..   Au = A  .  =     1



reguler berderajat k, setiap baris dari Sehingga diperoleh    k 1    ..   ..  .  = k .     k 1



jadi, k adalah nilai eigen dari Γ.   x1    .  2. Misalkan x =  ..  adalah sebarang vektor tak nol yang memenuhi Ax = kx dan   xn xj adalah entri dari x dengan nilai mutlak terbesar. Karena (Ax)j = kxj , diperoleh P0 P0 adalah penjumlahan dari k buah titik vi yang bertetangga xi = kxj dimana dengan vj . Akan ditunjukkan xi = xj untuk setiap vi yang bertetangga dengan vj . Andaikan ada x1 ,x2 ,...,xm yang tidak sama dengan xj . Akibatnya |xi | < |xj | untuk i=1,2,...,m ; m < k. Sehingga | Jadi |



P0



P0



xi | ≤



P0



|xi | < k|xj | = |kxj |.



xi | < |kxj |. Hal ini kontradiksi dengan



P0



xi = kxj . Jadi haruslah xi = xj



untuk i=1,2,...,m. Sehingga diperoleh xi = xj untuk setiap vi yang bertetangga dengan vj . Kemudian, akan ditunjukkan xk = xj untuk setiap vk yang tidak bertetangga dengan vj . Pilih xk sehingga vk bertetangga dengan vi . Karena Γ reguler berderajat k, vi bertetangga dengan k buah titik vl , yang salah satunya adalah vk . Karena (Ax)i = P0 P0 kxi , diperoleh xl = kxi dimana adalah penjumlahan dari k buah titik vl yang bertetangga dengan vi . Akan ditunjukkan xl = xi untuk setiap vl yang bertetangga



BAB 3. GRAF REGULER DAN GRAF GARIS



31



dengan vi . Andaikan ada x1 ,x2 ,...,xp yang tidak sama dengan xi . Karena xi = xj adalah entri dari x dengan nilai mutlak terbesar, akibatnya |xl | < |xi | untuk l=1,2,...,p. Sehingga | Jadi |



P0



P0



xl | ≤



P0



|xl | < k|xi | = |kxi |.



xl | < |kxi |. Hal ini kontradiksi dengan



P0



xl = kxi . Jadi haruslah xl = xi



untuk l=1,2,...,p. Sehingga diperoleh xl = xi untuk setiap vl yang bertetangga dengan vi . Artinya xl = xj untuk setiap vl yang bertetangga dengan vi . Karena Γ terhubung, hal diatas dapat dilakukan sampai didapatkan xi = xj untuk setiap titik. Jadi x adalah kelipatan dari u dan ruang eigen yang berasosiasi dengan nilai eigen k mempunyai dimensi 1. Dapat disimpulkan bahwa jika Γ terhubung maka multiplisitas dari k adalah 1. 3. Misalkan λ adalah sebarang nilai eigen dari A dan y adalah vektor eigen yang berkorespondensi dengan nilai eigen λ. Tulis Ay = λy, y 6= 0. Misalkan yj adalah entri dari y dengan nilai mutlak terbesar. Karena (Ay)j = λyj , P0 diperoleh yi = λyj sehingga |λ||yj | = |



P0



yi | ≤



P0



|yi | = k|yj |.



Sehingga terbukti bahwa |λ| ≤ k.



Contoh 3.2. Contoh graf reguler adalah graf lengkap Kn dan graf lingkaran Cn . Perhatikan graf C3 berikut.



Gambar 3.1: Contoh graf reguler



BAB 3. GRAF REGULER DAN GRAF GARIS Misalkan A adalah matriks ketetanggaan dari C3 .  0 1 1   A= 1 0 1  1 1 0 



λ



−1 −1



32



    







    Diperoleh det(λI − A) = det  −1 λ −1  = λ3 − 3λ − 2 = (λ − 2)(λ2 + 2λ + 1) =   −1 −1 λ (λ − 2)(λ + 1)2 . Dapat dilihat bahwa 2 adalah nilai eigen dari C3 dengan multiplisitasnya 1.



Selanjutnya, perhatikan graf reguler G yang tidak terhubung berikut.



Gambar 3.2: Contoh graf regular yang tak terhubung Matriks ketetanggaan dari graf G adalah 



0 1 0 0







     1 0 0 0    A=   0 0 0 1    0 0 1 0



Nilai eigen dari matriks  ketetanggaan A adalah  λ −1 0 0      −1 λ 0 0    det(λI − A) = det    0 0 λ −1    0 0 −1 λ



BAB 3. GRAF REGULER DAN GRAF GARIS     −1 0 0 λ 0 0         = λ det  0 λ −1  + det  0 λ −1     0 −1 λ 0 −1 λ       λ −1 λ −1   − det  = λ λ det  −1 λ −1 λ = λ(λ(λ2 − 1)) − (λ2 − 1)



33     



= λ4 − 2λ2 + 1 = (λ + 1)2 (λ − 1)2 Perhatikan bahwa multiplisitas dari nilai eigen 1 adalah 2 (Proposisi 3.1 bagian 2 tidak berlaku).



Aljabar ketetanggaan dari graf reguler yang terhubung memiliki sifat yang khusus terkait dengan Proposisi 1. Misalkan J adalah matriks dengan semua entrinya +1. Maka jika A adalah matriks ketetanggaan dari graf regular berderajat k, kita peroleh AJ=JA=kJ. Berikut hasil yang lebih lengkap. Proposisi 3.3. (Hoffman 1963) Matriks J anggota aljabar ketetanggaan A(Γ) jika dan hanya jika Γ graf reguler terhubung. Bukti. ⇒ Misalkan J anggota A(Γ). Berdasarkan definisi A(Γ), J adalah polinom dari A. Tulis J=an An + an−1 An−1 + ... + a0 I. Sehingga diperoleh Perhatikan bahwa  nAJ=JA. n n X X X a a ... a1j  1j 1j       j=1 j=1  j=1  a11 a12 ... a1n 1 1 ... 1 n n n   X X     X      a2j a2j ... a2j   a21 a22 ... a2n   1 1 ... 1      AJ=  j=1 j=1 j=1  .. .. .. ..   .. .. .. ..  =    .  . . . .   .. .. .. .. . . .       . . . .   n  n n an1 an2 ... ann 1 1 ... 1 X X  X   anj anj ... anj       JA=   



1 1 ... 1







a11



a12



... a1n



  1 1 ... 1   a21 a22 ... a2n  .. .. .. ..   .. .. .. ..  . . . . .  . . .  1 1 ... 1 an1 an2 ... ann



j=1



j=1



n X



n X



j=1 n X



ai1 ai2 ... ain   i=1 i=1 i=1  n n n   X X X   ai1 ai2 ... ain    =  i=1 i=1 i=1   .. .. .. ..     . . . .  n n n  X X X  ai1 ai2 ... ain 



i=1



i=1



i=1



             



BAB 3. GRAF REGULER DAN GRAF GARIS



34



Misalkan k (i) adalah derajat dari titik vi . Maka (AJ)ij = k (i) dan (JA)ij = k (j) . Karena AJ=JA, k (i) = k (j) untuk setiap i dan j. Sehingga Γ reguler. Selanjutnya, andaikan Γ tak terhubung, misalkan vi dan vj tak terhubung. Artinya tidak terdapat walk antara vi dan vj . Sehingga berdasarkan Lema 2.5, entri ke-ij pada matriks Al sama dengan 0 untuk setiap l. Kontradiksi dengan J ∈ A(Γ) karena J adalah matriks dengan semua entrinya +1. Jadi haruslah Γ terhubung. ⇐ Sebaliknya, misalkan Γ terhubung dan reguler dengan derajat k. Dari Proposisi 1 bagian (1), k adalah nilai eigen dari Γ. Jadi, polinom minimum dari A dapat ditulis p(λ) = (λ − k)q(λ). Berdasarkan definisi, p(A) = 0, sehingga Aq(A) = kq(A). Jadi, setiap kolom q(A) adalah vektor eigen dari A yang berkorespondensi dengan nilai eigen k. Berdasarkan Proposisi 1 bagian (2), setiap kolom dari q(A) kelipatan dari u = [1 1 . . . 1]t . Karena q(A) simetris, q(A) = αJ, untuk suatu α. Jadi, J ∈ A(Γ). Akibat 3.4. Misalkan Γ k-reguler dan terhubung dengan n titik. Misalkan nilai eigen Y yang berbeda dari Γ adalah k > λ1 > λ2 > · · · > λs−1 . Jika q(λ) = (λ − λi ) maka 1≤i≤s−1



J=







n q(k)







q(A)



Bukti. Dari proposisi 3, diperoleh q(A) = αJ, untuk suatu α. Akan ditunjukkan semua nilai eigen dari q(A) adalah q(k) dan q(λi ), 1 ≤ i ≤ s − 1. Misalkan Ax = kx dengan x 6= 0 adalah vektor eigen dari A yang berkorespondensi dengan nilai eigen k dan Avi = λi vi ; 1 ≤ i ≤ s − 1 dengan vi 6= 0 adalah vektor eigen dari A yang berkorespondensi dengan nilai eigen λi . Misal q(A) = (A − λ1 I)(A − λ2 I)...(A − λs−1 I) q(A) = as−1 As−1 + as−2 As−2 + ... + a1 A1 + a0 I ; untuk suatu konstanta ai ; 1≤i≤s−1 Perhatikan bahwa q(A)x = (as−1 As−1 + as−2 As−2 + ... + a1 A1 + a0 I)x = as−1 As−1 x + as−2 As−2 x + ... + a1 A1 x + a0 Ix = as−1 k s−1 x + as−2 k s−2 x + ... + a1 k 1 x + a0 x = (as−1 k s−1 + as−2 k s−2 + ... + a1 k 1 + a0 )x



BAB 3. GRAF REGULER DAN GRAF GARIS



35



= q(k)x Artinya q(k) adalah nilai eigen dari q(A). Selanjutnya, q(A)vi = (as−1 As−1 + as−2 As−2 + ... + a1 A1 + a0 I)vi = as−1 As−1 vi + as−2 As−2 vi + ... + a1 A1 vi + a0 Ivi = as−1 λs−1 vi + as−2 λs−2 vi + ... + a1 λ1i vi + a0 vi i i = (as−1 λis−1 + as−2 λs−2 + ... + a1 λ1i + a0 )vi i = q(λi )vi Artinya q(λi ) adalah nilai eigen dari q(A). Dari definisi q(λ), q(λi ) = 0 untuk setiap 1 ≤ i ≤ s − 1, sedangkan q(k) 6= 0. Klaim nilai eigen q(A) yang tak nol hanyalah q(k). Andaikan ada dua nilai eigen q(A) yang tak nol, katakan r1 dan r2 dengan r1 6= r2 . Tulis q(A)w1 = r1 w1 dengan w1 6= 0 adalah vektor eigen dari q(A) yang berkorespondensi dengan nilai eigen r1 dan q(A)w2 = r2 w2 dengan w2 6= 0 adalah vektor eigen dari q(A) yang berkorespondensi dengan nilai eigen r2 . Karena w1 dan w2 adalah vektor eigen yang berkorespondensi dengan nilai eigen yang berbeda, w1 dan w2 bebas linier. Sehingga r1 w1 dan r2 w2 juga bebas linier. Artinya dim(q(A)) ≥ 2. Hal ini kontradiksi dengan q(A) = αJ karena q(A) = αJ menyebabkan q(A) berdimensi 1. Jadi nilai eigen q(A) yang tak nol hanyalah q(k). Sementara nilai eigen tak nol dari αJ adalah αn. Buktinya : Misalkan λ adalah nilai eigen tak nol dari αJ. Tulis αJx = λx ; dengan x 6= 0 adalah vektor eigen dari αJ yang berkorespondensi dengan nilai eigen λ. Perhatikan bahwa        



α α ... α α α ... α .. .. .. .. . . . . α α ... α







       



x1 x2 .. .











       = λ      



   α(x1 + x2 + ... + xn )   ..  .  α(x1 + x2 + ... + xn )



x2 .. .



       



xn



xn



α(x1 + x2 + ... + xn )



x1











λx1







        λx2  =    ..    .     λxn



BAB 3. GRAF REGULER DAN GRAF GARIS



36



Sehingga diperoleh   α(x1 + x2 + ... + xn ) = λx1       α(x1 + x2 + ... + xn ) = λx2 ..   .      α(x1 + x2 + ... + xn ) = λxn λ(x1 ) = λ(x2 ) = ... = λ(xn )



              



Karena λ 6= 0, x1 = x2 = ... = xn . Misalkan x1 = x2 = ... = xn = a. Maka     αna λa          αna   λa   =   ..   ..   .   .      αna λa     a a          a   a     αn   ..  = λ  ..   .   .      a a Jadi, λ = αn adalah nilai eigen tak nol dari αJ. Sehingga diperoleh α = q(k)/n. Contoh 3.5. Dari contoh 2 diperoleh det(λI − A) = (λ − 2)(λ2 + 2λ + 1). Jadi q(λ) = λ2 + 2λ + 1. Perhatikan bahwa :   2 0 1 1         n 3   1 0 1  q(A) = + 2   q(k) 22 + 2 × 2 + 1      1 1 0      1 2 1 1 0 2 2      1      =  1 2 1  +  2 0 2  +  0 3      0 1 1 2 2 2 0     3 3 3 1 1 1    1     =  3 3 3 = 1 1 1 =J 3    3 3 3 1 1 1



 0 1 1 1 0 0        1 0 1  +  0 1 0      1 1 0 0 0 1  0 0   1 0   0 1 







BAB 3. GRAF REGULER DAN GRAF GARIS



37



Matriks S berukuran n × n dikatakan matriks sirkulan jika entri-entrinya memenuhi sij = s1,j−i+1 dimana indeks-indeksnya bilangan modulo n dan terletak di himpunan {1, 2, . . . , n}. Dengan kata lain baris i dari matriks S didapatkan dari baris pertama yang digeser ke kanan sebanyak i − 1. Sehingga sebarang matriks sirkulan dapat ditentukan dari baris pertamanya. Misalkan W matriks sirkulan dengan baris pertamanya adalah [0, 1, 0, . . . , 0] dan S matriks sirkulan dengan baris pertamanya adalah [s1 , s2 , . . . , sn ]. Perhatikan bahwa n X sj Wj−1 = s1 W 0 + s2 W 1 + s3 W 2 + ... + sn W n−1 j=1







1 0 0 ... 0



     = s1     



Jadi











0 1 0 ... 0











        0 1 0 ... 0   0 0 1 ... 0           0 0 1 ... 0 +s2  0 0 0 ... 0 +s3       .. .. ..  .. .. .. ..  ..   . . .   . . . .  .     0 0 0 ... 1 1 0 0 ... 0   0 0 0 ... 1      1 0 0 ... 0      + ... + sn  0 1 0 ... 0     .. .. .. ..   . . . .    0 0 0 ... 0   s1 s2 s3 ... sn      sn s1 s2 ... sn−1      =  sn−1 sn s1 ... sn−2  = S    ..  .. .. ..  .  . . .   s2 s3 s4 ... s1 n X S= sj Wj−1 . j=1



Akan dicari nilai eigen dari W .



0 0 1 0 ... 0







  0 0 0 1 ... 0    0 0 0 0 ... 0    .. .. .. ..  . . . .  0 1 0 0 ... 0



BAB 3. GRAF REGULER DAN GRAF GARIS    λ −1 0 ... 0 0      0 λ −1 ... 0 0       0 0 λ ... 0 0   det(λI − W ) = det  . .. .. .. ..   .. . . . .        0 0 ... λ −1   0   −1 0 0 ... 0 λ λ −1 ... 0 0 −1 0 0 λ ... 0 0 λ −1 .. .. .. .. 0 = λ . + (−1)n−1 (−1) 0 λ . . . .. .. 0 0 ... λ −1 . . 0 0 ... 0 λ 0 0 λ ... 0 0 −1 ... .. .. .. . λ ... . . n−1 0 = λ.λ (−1)(−1) . + (−1) 0 ... λ −1 .. 0 ... 0 λ 0 ... n−1 n−1 n−1 0 = λ.λ + (−1) (−1)(−1)



38



0 0 0 0 0 .. .. . . λ −1 0 0 .. . −1



... 0 ... ...



... 0 0 .. . λ



0 = λn + (−1)2n−1 = λn − 1 λn = 1 λr = e2πri/n dengan r = 0, 1, 2, ..., n − 1 Sehingga nilai-nilai eigen dari W adalah 1, ω, ω 2 , . . . , ω n−1 dimana ω =exp(2πi/n), akibatnya nilai-nilai eigen dari S adalah λ0 = s1 + s2 + s3 + ... + sn λ1 = s1 .1 + s2 .ω 1 + s3 .ω 2 + ... + sn .ω n−1 λ2 = s1 .1 + s2 .ω 2 + s3 .ω 4 + ... + sn .ω 2(n−1) .. . λn−1 = s1 .1 + s2 .ω (n−1) + s3 .ω 2(n−1) + ... + sn .ω (n−1)(n−1) Atau secara umum dapat dituliskan λr =



n X



sj ω (j−1)r , r = 0, 1, . . . , n − 1.



j=1



S.uatu graf sirkulan adalah graf Γ dimana titik-titiknya dapat diurutkan sehingga matriks ketetanggaan A(Γ) adalah matriks sirkulan. Matriks ketetanggaan adalah matriks



BAB 3. GRAF REGULER DAN GRAF GARIS



39



simetri dengan entri nol pada diagonal utama. Akibatnya jika baris pertama matriks ketetanggaan dari graf sirkulan adalah [a1 , a2 , . . . , an ] maka a1 = 0 dan ai = an−i+2 untuk i = 2, . . . , n. Proposisi 3.6. Misalkan [0, a2 , . . . , an ] adalah baris pertama dari matriks ketetanggaan suatu graf sirkulan Γ maka nilai-nilai eigen dari Γ adalah λr =



n X



aj ω (j−1)r , r=0, 1, . . . , n − 1.



j=2



Bukti. Karena matriks ketetanggaan dari graf Γ dapat ditulis n X A(Γ) = aj Wj−1 , j=2



nilai-nilai eigen dari A(Γ) adalah λr =



n X



aj ω (j−1)r , r=0, 1, . . . , n − 1.



j=2



Contoh 3.7. Menghitung nilai-nilai eigen dari graf sirkulan. Contoh pertama, graf lengkap Kn adalah graf sirkulan dengan baris pertama matriks ketetanggaannya adalah [0, 1, 1, . . . , 1]. Berdasarkan proposisi 7, nilai eigen dari Kn adalah λ0 = a2 + a3 + ... + an = n − 1 λ1 = a2 .ω 1 + a3 .ω 2 + ... + an .ω n−1 = ω 1 + ω 2 + ... + ω n−1 λ2 = a2 .ω 2 + a3 .ω 4 + ... + an .ω 2(n−1) = ω 2 + ω 4 + ... + ω 2(n−1) .. . λn−1 = a2 .ω (n−1) +a3 .ω 2(n−1) +...+an .ω (n−1)(n−1) = ω (n−1) +ω 2(n−1) +...+ω (n−1)(n−1)



Karena 1 + ω r + · · · + ω (n−1)r = 0 untuk r ∈ {1, 2, . . . , n − 1}, nilai eigen dari Kn adalah n − 1 dan -1. Sehingga spectrum Kn adalah:   n − 1 −1 . SpecKn =  1 n−1 Contoh kedua adalah graf lingkaran Cn dimana matriks ketetanggaannya adalah matriks sirkulan dengan baris pertama adalah [0, 1, 0, . . . , 0, 1]. Berdasarkan proposisi 7,



BAB 3. GRAF REGULER DAN GRAF GARIS



40



nilai-nilai eigennya adalah λr = 2cos(2πr/n) yang semuanya belum tentu berbeda; dengan melihat semua bentuk nilai-nilai eigennya kita peroleh spectrumnya adalah :   2 2cos2π/n . . . 2cos(n − 1)π/n  (n ganjil), Spec Cn =  1 2 ... 2   2 2cos2π/n . . . 2cos(n − 2)π/n −2  (n genap). Spec Cn =  1 2 ... 2 1



3.3. Graf Garis



Misalkan Γ adalah suatu graf dengan himpunan sisi EΓ={e1 , e2 , ..., em } dan himpunan titik V Γ={v1 , v2 , ..., vn }. Matriks ketetanggaan suatu graf Γ adalah suatu matriks A = A(Γ)n×n dimana   1, jika vi dan vj bertetangga; (A)ij =  0, jika v dan v tidak bertetangga. i j Berdasarkan definisi di atas, A adalah suatu matriks simetri dan setiap unsur pada diagonal utama adalah 0. Contohnya, graf Γ yang terdiri dari 4 titik dan 5 sisi berikut. Matriks ketetanggaan dari



Gambar 3.3: graf Γ



graf Γ tersebut adalah 



0 1 1 1







     1 0 1 0   A=    1 1 0 1    1 0 1 0



BAB 3. GRAF REGULER DAN GRAF GARIS



41



Dari suatu graf Γ dapat dibentuk graf garis L(Γ), dimana setiap sisi di Γ adalah titik di L(Γ) dan untuk setiap titik pada Γ yang terkait pada sisi ea dan sisi yang lain misal eb , maka ea dan eb bertetangga di L(Γ). Dari L(Γ) dapat juga dibentuk matriks ketetanggaannya yaitu AL berukuran m × m dimana   1, jika ei dan ej bertetangga; (AL )ij =  0, jika e dan e tidak bertetangga. i



j



Sebagai contoh, graf garis L(Γ) dan matriks ketetanggaan AL dari graf Γ di atas adalah



Gambar 3.4: Contoh graf L(Γ)







0 1 0 1 1



   1 0 1   AL =  0 1 0    1 0 1  1 1 1







  0 1    1 1    0 1   1 0



Definisikan matriks Xn×m sebagai berikut.   1, jika vi dan ej terkait; (X)ij =  0, jika v dan e tidak terkait. i j Sebagai contoh, matriks X dari graf Γ di atas adalah 



1 0 0 1 1







   1 1 0 0 0 X=   0 1 1 0 1  0 0 1 1 0



      



Definisi di atas akan digunakan untuk membuktikan lema berikut.



BAB 3. GRAF REGULER DAN GRAF GARIS



42



Lema 3.8. Didefinisikan Γ, A, L(Γ), AL dan X seperti di atas. Maka 1. X t X = AL + 2Im 2. Jika Γ adalah graf k-reguler, maka XX t = A + kIn Bukti. 1. 



Misalkan



x11



x12



... x1m



   x21 x22 ... x2m (X)ij =   .. .. .. ..  . . . .  xn1 xn2 ... xnm











xn1







      x x22 ... xn2  (X)ij t =  12   .. .. .. ..   . . . .   x1m x2m ... xmn



      



x11



x21



...







x .x + x21 .x21 + ... + xn1 .xn1 x11 .x12 + ... + xn1 .xn2 ... x11 .x1m + ... + xn1 .xnm  11 11 . .. .. ..  .. X tX =  . . .  x1m .x11 + x2m .x21 + ... + xnm .xn1 x1m .x12 + ... + xnm .xn2 ... x1m .x1m + ... + xnm .xnm Sehingga t



(X X)ij =



n X



(X)li (X)lj



(3.1)



l=1



Dari definisi (X)ij dan dari (1) maka (X t X)ij adalah banyaknya titik vl yang terkait dengan sisi ei dan ej . Jika i = j, artinya banyaknya titik vl yang terkait dengan sisi ei yaitu sebanyak 2. Sehingga (X t X)ij = 2, untuk i = j. Jika i 6= j artinya banyaknya titik vl yang terkait dengan sisi ei dan ej yaitu sebanyak 1 (jika ei dan ej bertetangga) atau 0 (jika ei dan ej tidak bertetangga). Sehingga (X t X)ij = 1 (jika ei dan ej bertetangga) atau (X t X)ij = 0 (jika ei dan ej tidak bertetangga). Perhatikan bahwa    2, jika i = j;   (AL + 2Im )ij = 1, jika i 6= j, ei dan ej bertetangga;     0, jika i = 6 j, ei dan ej tidak bertetangga. dapat dilihat bahwa (X t X)ij = (AL + 2Im )ij . Terbukti (X t X) = AL + 2Im .



    



BAB 3. GRAF REGULER DAN GRAF GARIS



43



2. Dengan pemisalan X dan X t di atas, diperoleh  x .x + x12 .x12 + ... + x1m .x1m x11 .x21 + ... + x1m .x2m ... x11 .xn1 + ... + x1m .xmn  11 11 .. .. .. ..  t XX =  . . . .  xn1 .x11 + xn2 .x12 + ... + xnm .x1m xn1 .x21 + ... + xnm .x2m ... xn1 .xn1 + ... + xnm .xmn Sehingga t



(XX )ij =



n X



(X)il (X)jl



(3.2)



1=1



Dari definisi (X)ij dan dari (2) maka (XX t )ij adalah banyaknya sisi el yang terkait dengan titik vi dan vj . Jika i = j, artinya banyaknya sisi el yang terkait dengan titik vi yaitu sebanyak k (karena Γ adalah graf reguler berderajat k). Sehingga (X t X)ij = k, untuk i = j Jika i 6= j artinya banyaknya sisi el yang terkait dengan titik vi dan vj yaitu sebanyak 1 (jika vi dan vj bertetangga) atau 0 (jika vi dan vj tidak bertetangga). Sehingga (XX t )ij = 1 (jika vi dan vj bertetangga) atau (XX t )ij = 0 (jika vi dan vj tidak bertetangga). Sekarang perhatikan bahwa



(A + kIn )ij =



   k, jika i = j;  



1, jika i 6= j, vi dan vj bertetangga;     0, jika i 6= j, v dan v tidak bertetangga. i j



dapat dilihat bahwa (XX t )ij = (A + kIn )ij . Terbukti (XX t ) = A + kIn . Contoh 3.9. Berdasarkan contoh di atas, matriks X dan X t dari graf Γ adalah sebagai berikut.  



1 0    1 1 X=   0 1  0 0



0 1 1







  0 0 0    1 0 1   1 1 0



1 1 0 0



   0 1 1   t X = 0 0 1    1 0 0  1 0 1







  0    1    1   0



    



BAB 3. GRAF REGULER DAN GRAF GARIS Sehingga diperoleh 



1 1 0 0



   0 1 1   X tX =  0 0 1    1 0 0  1 0 1 







 



  0    1    1   0



0 1 0 1 1



   1 0 1   = 0 1 0    1 0 1  1 1 1



44



1 0 0 1 1



2 1 0 1 1







     1 2 1 1 1 0 0 0   =   0 1 2 0 1 1 0 1      1 0 1  0 0 1 1 0 1 1 1











     0 1      1 1  + 2      0 1    1 0



1 0 0 0 0







  0 1    1 1    2 1   1 2







  0 1 0 0 0    0 0 1 0 0  = AL + 2Im   0 0 0 1 0   0 0 0 0 1



dan  



1 0 0 1 1



   1 1 t XX =    0 1  0 0 



0 1    1 0 =   1 1  1 0







1 1 0 0



   0 1 1 0 0 0    0 0 1 1 0 1    1 0 0 1 1 0  1 0 1   1 1 1 0      0 1 1 0   + 2    0 0 0 1    1 0 0 0







  3 1 1  0      1 2 1  1 =     1 1 3 1    1 0 1 0  0 0   0 0   6= A + kIn  1 0   0 1



1



  0    1   2



(karena Γ tidak reguler) Proposisi 3.10. Jika λ adalah nilai eigen dari AL , maka λ ≥-2. Bukti. Misal µ adalah nilai eigen dari X t X, maka



X t X.z = µ.z dengan z adalah vektor eigen yang bersesuaian dengan µ z t X t Xz = µ.z t z Di sisi lain, k Xz k2



= < Xz, Xz >



=



(Xz)t .Xz



=







z t X t Xz.



BAB 3. GRAF REGULER DAN GRAF GARIS Karena k Xz k2



45



≥ 0, z t X t Xz ≥0. Sementara z t z ≥ 0. Maka µ ≥ 0.



Pandang X t X.z = µ.z (AL + 2Im ).z = µ.z AL .z + 2Im .z = µ.z AL .z = −2Im .z + µ.z AL .z = (µ − 2).Im .z AL .z = (µ − 2).z AL .z = λ.z Karena µ ≥ 0, nilai eigen dari AL yaitu λ ≥ -2.



Satu fakta tentang hubungan graf reguler dengan graf garisnya yaitu jika Γ graf reguler berderajat k maka graf garis L(Γ) adalah graf reguler dengan derajat 2k − 2. Teorema berikut menjelaskan hubungan antara polinomial karakteristik dari suatu graf reguler Γ dengan polinomial karakteristik dari graf garis L(Γ). Sehingga bila kita telah mengetahui polinomial karakteristik dari suatu graf reguler kita dapat langsung mengetahui polinomial karakteristik graf garis L(Γ) tanpa menghitung det(λI − AL ) lebih dulu. Teorema 3.11. (Sachs 1967) Jika Γ suatu graf reguler berderajat k dengan n titik dan m = 12 nk sisi maka χ(L(Γ); λ) = (λ + 2)m−n χ(Γ; λ + 2 − k). Bukti. Definisikan dua matriks yang dipartisi dengan ukuran (n + m) × (n + m) sebagai berikut:  U=



λIn −X 0



Im











, V = 



In X



t



X λIm



 .



Maka kita peroleh  UV = 



λIn − XXt



0



Xt



λIm











 , VU = 



λIn



0



λXt λIm − Xt X



 .



BAB 3. GRAF REGULER DAN GRAF GARIS



46



Kita dapat menggunakan ekspansi kofaktor untuk menghitung det(UV) dan det(VU). Sehingga kita peroleh det(UV)=λm det(λIn − XXt ) dan det(VU)=λn det(λIm − Xt X). Karena det(UV)=det(U)det(V)=det(VU) maka λm det(λIn − XXt ) = λn det(λIm − Xt X). Akibatnya, untuk λ 6= −2,



χ(L(Γ); λ) = det(λIm − AL ) = det((λ + 2)Im − Xt X) = (λ + 2)m−n det((λ + 2)In − XXt ) = (λ + 2)m−n det((λ + 2 − k)In − A) = (λ + 2)m−n χ(Γ; λ + 2 − k).



Sedangkan untuk λ = −2,



χ(L(Γ); −2) = det(−2Im − AL ) = det(−XX t ) = det(−(A + kIn )) = det(−kIn − A)) = χ(Γ; −k)



Jika Γ suatu graf reguler dan spectrum dari Γ adalah sebagai berikut:   k λ1 . . . λs−1 , SpecΓ =  1 m1 . . . ms−1



BAB 3. GRAF REGULER DAN GRAF GARIS



47



Artinya polinomial karakteristik dari graf Γ yaitu χ(Γ; λ) = (λ − k)(λ − λ1 )m1 . . . (λ − λs−1 )ms−1 . Berdasarkan teorema 12 kita peroleh χ(L(Γ); λ) = (λ + 2)m−n χ(Γ; λ + 2 − k) = (λ + 2)m−n (λ + 2 − k − k)(λ + 2 − k − λ1 )m1 . . . (λ + 2 − k − λs−1 )ms−1 = (λ + 2)m−n (λ − 2k + 2)(λ − k + 2 − λ1 )m1 . . . (λ − k + 2 − λs−1 )ms−1 . Sehingga kita peroleh bahwa 2k − 2, −2 dan k − 2 + λi untuk 1 ≤ i ≤ s − 1 adalah nilainilai eigen dari L(Γ). Dapat diperiksa bahwa masing-masing nilai eigen dari L(Γ) diatas semuanya berbeda. Akibatnya spectrum dari L(Γ) bisa kita tuliskan menjadi   2k − 2 k − 2 + λ1 . . . k − 2 + λs−1 −2 . Spec L(Γ) =  1 m1 ... ms−1 m−n Sebagai contoh, misalkan Kt graf lengkap dengan t titik. Graf garis L(Kt ) kadang dinamakan triangle graf dan ditulis ∆t . Perhatikan himpunan I = {1, 2 . . . , t}, maka titik pada graf garis bisa kita tulis sebagai pasangan bilangan dari I. Sehingga banyaknya titik dari graf garis dari graf Kt yaitu 12 t(t − 1). Lebih jelasnya angka ini kita peroleh dengan alasan sebagai berikut. Setiap titik pada graf garis merupakan sisi pada Kt , sehingga dapat direpresentasikan sebagai pasangan tak terurut (a, b) dimana a, b ∈ I dan ab adalah sisi pada graf Kt . Selain itu setiap titik (a, b) di ∆t berlaku a 6= b. Jadi banyaknya titik di ∆t sama dengan setengah dari banyaknya cara mengisi komponen pertama dan mengisi komponen kedua yang berbeda dari digit pertama pada (a, b). Sekarang dengan representasi di atas, sisi pada ∆t berkorespondensi dengan dua pasangan terurut yang memiliki satu digit yang sama. Kita ketahui pada pembahasan sebelumnya spectrum dari Kt yaitu   t − 1 −1 . Spec Kt =  1 t−1 Akibat dari teorema di atas kita peroleh  2t − 4 t − 4 Spec∆t =  1 t−1



−2 1 2 t(t



− 3)



 .



Bab 4



Cycle dan Cut Misalkan C dinotasikan sebagai lapangan atas bilangan kompleks, dan X adalah sebarang himpunan berhingga. Misalkan himpunan seluruh fungsi dari X ke C mempunyai struktur ruang vektor berdimensi hingga. Misal f : X → C dan g : X → C , dimana operasinya memenuhi: (f + g)(x) = f (x) + g(x),



(αf )(x) = αf (x),



(x ∈ X, α ∈ C)



R . uang titik C0 (Γ) dari suatu graf adalah ruang vektor dari semua fungsi V Γ → C. Ruang sisi C1 (Γ) dari suatu graf adalah ruang vektor dari fungsi EΓ → C. Misal V Γ = {v1 , v2 , . . . , vn }, EΓ = {e1 , e2 , . . . , en }. Akan dibuktikan C0 (Γ) dan C1 (Γ) adalah ruang vektor.



C0 (Γ) = {f |f : V Γ → C} Definisikan operasi + : C0 (Γ) × C0 (Γ) → C0 (Γ) oleh (f, g) 7→ f + g (f + g)(x) = f (x) + g(x) × : C0 (Γ) × C0 (Γ) → C0 (Γ) 48



BAB 4. CYCLE DAN CUT



49



oleh (α, f ) 7→ αf Sifat-sifat ruang vektor yang harus dipenuhi yaitu:



(1)(f + g)(x) = f (x) + g(x) = g(x) + f (x) = (g + f )(x) karena f (x), g(x) ∈ C (sifat komutatif)



(2)((f + (g + h))(x) = f (x) + (g + h)(x) = f (x) + g(x) + h(x) = (f + g)(x) + h(x) = ((f + g) + h)(x) karena f (x), g(x), h(x) ∈ C (sifat assosiatif)



(3)∃0 ∈ C0 (Γ)∀xi ∈ V (Γ), 1 ≤ i ≤ n sedemikian hingga (f + 0) = f



misalkan 0 : vi (Γ)) 7→ 0 (f + 0)(xi ) = f (xi ) + 0(xi ) = f (xi ) + 0 = f (xi )



(4)∃ − f ∈ C0 (Γ), ∀f ∈ C0 (Γ) sedemikian hingga f + (−f ))(x) = f (x) − f (x) = 0 = 0(x)



(5)(α(f + g))(x) = α(f + g)(x) = α(f (x) + g(x)) = αf (x) + αg(x) = (αf + αg)(x)



(6)((α + β)f ))(x) = (α + β)f (x) = αf (x) + βf (x) = (αf + βf )(x)



(7) ((αβ)f )(x) = (αβf )(x) = (αβ)f (x) = α(βf (x) = (α(βf ))(x) = β(αf (x) = (β(αf ))(x)



(8)(1 × f )(x) = 1 × f (x) = f (x)



Jadi C0 (Γ) adalah ruang vektor. Dengan langkah pengerjaan yang sama akan terbukti bahwa C1 (Γ) juga merupakan ruang vektor.



Selanjutnya akan ditunjukkan dim C0 (Γ) = n dan dim C1 (Γ) = m.



BAB 4. CYCLE DAN CUT



50



Misalkan V Γ = v1 , v2 , ..., vn dan misalkan A = a1 , a2 , ..., an adalah basis standart dari C0 (Γ), didefinisikan oleh:   1, if i = j; ai (vj ) =  0, yang lain. Ambil sebarang f ∈ C0 (Γ) dan misalkan f (vi ) = ki untuk suatu ki ∈ C ¸. P Akan ditunjukkan f = αi ai untuk suatu αi ∈ C, i=1, 2,...,n. Pilih αi = ki (domain f P dan αi ai adalah C0 (Γ)). Selanjutnya ambil vj ∈ C0 (Γ))sebarang maka f (vj ) = kj . P P αi ai (vj ) = ki ai (vi ) P αi ai (vj ) = kj aj (vj ) = kj . Jadi ai membangun C0 (Γ) Selanjutnya perhatikan kombinasi linier β1 a1 + β2 a2 + ... + βn an = 0 Ambil sebarang vj ∈ V Γ P Tulis αi ai (vj ) = βj aj (vj ) = βj = 0(vj ) = 0 Jadi ai bebas linier. Karena ai membangun dan bebas linier maka ai merupakan basis bagi C0 (Γ), sehingga dapat disimpulkan dim C0 (Γ) = n Selanjutnya setiap fungsi f : V Γ → C dapat direpresentasikan oleh vektor kolom y = [y1 , y2 , ..., yn ]t dimana yi = f (ai )(1 ≤ i ≤ n).



Selanjutnya misalkan EΓ = e1 , e2 , ..., em dan misalkan juga Misal B = b1 , b2 , ..., bn adalah basis standart dari C1 (Γ), didefinisikan oleh:   1, if i = j; bi (ej ) =  0, yang lain. Ambil sebarang f ∈ C1 (Γ) dan misalkan f (ei ) = ki untuk suatu ki ∈ C ¸. P Akan ditunjukkan f = αi bi untuk suatu αi ∈ C, i=1, 2,...,m. Pilih αi = ki (domain f P dan αi bi adalah C1 (Γ)). Selanjutnya ambil ej ∈ C1 (Γ))sebarang maka f (ej ) = kj .



BAB 4. CYCLE DAN CUT P



51



P



αi bi (ej ) =



P



αi bi (ej ) = kj bj (ej ) = kj . Jadi bi membangun C1 (Γ)



ki bi (ei )



Selanjutnya perhatikan kombinasi linier β1 b1 + β2 b2 + ... + βm bm = 0 Ambil sebarang ej ∈ EΓ P Tulis αi bi (vj ) = βj bj (vj ) = βj = 0(vj ) = 0 Jadi bi bebas linier. Karena bi membangun dan bebas linier maka bi merupakan basis bagi C1 (Γ), sehingga dapat disimpulkan dim C1 (Γ) = m Selanjutnya setiap fungsi f : EΓ → C dapat direpresentasikan oleh vektor kolom x = [x1 , x2 , ..., xn ]t dimana xi = f (bi )(1 ≤ i ≤ m). Pandang edge eα = (vσ , vτ ) dari Γ dipilih vσ sebagai positive end, dan vτ sebagai negative end. Prosedur ini dinamakan memberikan (Γ) suatu orientation.



M . atrik incidensi Dn×m dari (Γ) dengan orientasi didefinisikan oleh:    +1, vi positive end dari ej ;   dij = −1, vi negative end dari ej ;     0, yang lain.



Dengan barisnya bersesuaian dengan vertek - vertek Γ, dan kolomnya bersesuaian dengan edge - edge Γ. Misal diberikan Γ:



Maka matriks incidensinya adalah: 



−1



  D= 1  0



0



1







  1 0   −1 −1



(4.1)



BAB 4. CYCLE DAN CUT



52



Gambar 4.1: K3 Dapat dilihat bahwa setiap kolom dari graph Γ memuat hanya dua entry yang tidak nol yaitu +1 dan -1. Dianggap d adalah matriks representasi dengan basis standart dari pemetaan linier f : C1 Γ → C0 Γ. Pemetaan ini disebut pemetaan insidensi dan dinotasikan dengan D. untuk setiap g : EΓ → C maka fungsi Dg : V Γ → C didefinisikan dengan Dg(vi ) =



m X



dij g(ej )



(1 ≤ i ≤ n)



j=1



Proposisi 4.1. Matriks insidensi D dari graf Γ mempunyai rank = n − c, dimana c merupakan banyaknya komponen terhubung pada graf Γ dan komponen merupakan subgraf terhubung yang maksimal. Bukti. Matriks insidensi D bisa ditulis dalam bentuk  D(1) 0 ···    0 D(2) · · · D=  .. .. ..  . . .  0 0 ···



partisi sebagai berikut :  0   0   ..  .   D(c)



dengan pelabelan yang sesuai pada titik-titik dan sisi-sisi pada graf Γ, dimana matriks D(i) untuk 1 ≤ i ≤ c merupakan matriks insidensi dari komponen Γ(i) pada graf Γ.



Akan dibuktikan bahwa rank D adalah n − c.



Pertama akan dibuktikan bahwa rank D(i) adalah ni − 1, dimana ni = V Γ(i) . Perlu diketahui bahwa rank sebuah matriks adalah banyaknya baris bebas linier yang maksimal.



BAB 4. CYCLE DAN CUT



53



Misal dj dinotasikan sebagai baris pada D(i) yang berkorespondensi dengan titik vj pada Γ(i) . Tinjau entri di setiap kolom pada D(i) . Karena hanya terdapat satu +1 dan satu -1 di setiap kolom, maka jumlah dari semua baris pada D(i) menghasilkan vektor 0.



Pandang kombinasi linier α1 d1 + α2 d2 + · · · + αn dn = 0, Karena



Pn 1



(4.2)



dj = 0, maka kombinasi linier (1) terpenuhi oleh αj 6= 0 untuk setiap 1 ≤ j ≤



n. Sehingga {d1 , d2 , · · · , dn } tidak bebas linier (bergantung linier), dan diperoleh rank D(i) ≤ ni − 1.



Kemudian pilih baris dk dengan αk 6= 0. Perhatikan bahwa entri tak nol pada baris dk yang berkorespondensi dengan sisi, misal et , berinsidensi dengan titik vk . Jadi hanya terdapat satu baris lain, sebut dl , dimana entri tak nolnya juga berkorespondensi dengan sisi et , berinsidensi dengan titik vl . Perhatikan bahwa entri tak nol pada kolom et hanyalah +1 dan -1. Sehingga kombinasi linier α1 d1 + · · · + αk dk + · · · + αl dl + · · · + αn dn = 0 dengan αk 6= 0 menyebabkan αk = αl .



Selanjutnya jika αk 6= 0 maka αk = αl untuk setiap titik vk yang bertetangga dengan titik vl . Karena Γ(i) merupakan subgraf terhubung, maka setiap sisi eρ akan bertetangga dengan dua titik vσ , vτ menyebabkan koefisien αj akan bernilai sama untuk setiap 1 ≤ j ≤ n, dapat ditulis αj = β, untuk semua αj = 0 atau αj 6= 0. Sehingga kombinasi P linier (1) bisa ditulis dengan β n1 dj = 0.



Akan dibuktikan {d1 , d2 , · · · , dn−1 } bebas linier.



Pandang kombinasi linier α1 d1 + α2 d2 + · · · + αn−1 dn−1 = 0, Perhatikan bahwa kombinasi linier (3) bisa ditulis sebagai



(4.3)



BAB 4. CYCLE DAN CUT



54



α1 d1 + α2 d2 + · · · + αn−1 dn−1 + 0.dn = 0 Karena αj = β, untuk setiap, maka α1 = α2 = · · · = αn−1 = 0 = αn . Jadi kombinasi linier (3) dipenuhi hanya oleh α1 = α2 = · · · = αn−1 = 0, dan diperoleh {d1 , d2 , · · · , dn−1 } bebas linier.



Jadi rank D(i) adalah ni − 1. Karena rank D merupakan penjumlahan dari rank D(i) , maka rank D adalah n − c. Contoh 4.2. Diberikan graf Γ dengan 2 komponen, sebagai berikut : diperoleh matriks



Gambar 4.2: graf-1 insidensi 



+1



0



+1



0







     −1 −1 0 0      D =  0 +1 −1 0       0 0 0 −1    0 0 0 +1 dengan asumsi arah panah masuk merupakan ujung positif dan ujung negatif untuk lainnya.



Matrik D tersebut bisa dipartisi menjadi 2, karena graf Γ mempunyai 2komponen.  +1 0 +1     (1) Perhatikan matriks insidensi untuk komponen pertama berikut : D =  −1 −1 0 .   0 +1 −1 Misal d1 ,d2 ,d3 merupakan baris-baris di D(1) , maka d1 +d2 +d3 = 0.



BAB 4. CYCLE DAN CUT



55



Pandang kombinasi linier α1 d1 + α2 d2 + α3 d3 = 0, (4.4)      0 0 +1 −1                 Tulis α1  0  + α2  −1  + α3  +1  =  0  pilih α1 = α2 = α3 = 2 6= 0, se        0 −1 +1 0 hingga kombinasi linier (3) terpenuhi. Dapat disimpulkan bahwa {d1 , d2 , d3 } bergantung 











linier dan rank D(1) ≤ 2.



Pilih baris dengan koefisien α 6= 0, misal d2 , yang berkorespondensi dengan v2 . Karena v2 bertetangga dengan v3 dan pada setiap kolom di D(1) hanya terdapat satu +1 dan satu -1, menyebabkan α2 = α3 . Dan karena v3 juga bertetangga dengan v1 , diperoleh α3 = α1 . Sehingga α1 = α2 = α3 . Sehingga kombinasi linier (3) bisa ditulis dengan α(d1 +d2 +d3 ) = 0.



Kemudian akan dibuktikan {d1 , d2 } bebas linier.



Pandang kombinasi linier α1 d1 + α2 d2 = 0,



(4.5)



Kombinasi linier di atas dapat ditulis dengan α1 d1 + α2 d2 + 0.d3 = 0 Karena α1 = α2 = α3 dan α3 = 0, maka kombinasi linier (4) dipenuhi hanya oleh α1 = α2 = 0. Jadi {d1 , d2 } bebas linier. Sehingga rank D(1) = 2.



D . iberikan graf Γ dengan n-titik, m-sisi dan c-komponen. Rank dari graf Γ, ditulis dengan r(Γ) adalah n − c. Co-rank dari graf Γ, ditulis dengan s(Γ) adalah m − n + c.



Misal Q merupakan himpunan sisi-sisi pada graf Γ sehingga subgraf hQi adalah graf siklus. Q disebut cycle pada graf Γ. Perhatikan bahwa terdapat dua kemungkinan orientasi pada Q, yakni searah jarum jam atau berbeda arah jarum jam. Pilih salah satu dari dua kemungkinan orientasi pada Q.



Defenisikan fungsi ξQ : EQ → C dimana Q ∈ C1 (Γ).



BAB 4. CYCLE DAN CUT



56



Gambar 4.3: graf-2     +1, e ∈ Q, orientasi e ∈ Q = orientasi e ∈ Γ    ξQ (e) = −1, e ∈ Q, orientasi e ∈ Q 6= orientasi e ∈ Γ      0 , e ∈ /Q Contoh 4.3. Misal diberikan graf Γ dan Q seperti berikut, dimana graf Q adalah subgraf yang merupakan cycle di Γ.



Gambar 4.4: graf-3 



sehingga diperoleh ξ



Q



        =       



0







  +1    −1    −1 .   0    +1   0



Teorema 4.4. Kernel dari pemetaan insidensi D pada graf Γ adalah ruang vektor dimana dimensinya bernilai sama dengan co-rank dari graf Γ. Jika Q adalah cycle pada graf Γ, maka ξQ ∈ Ker(D). Bukti. Diketahui pemetaan D : C1 (Γ) → C0 (Γ)



BAB 4. CYCLE DAN CUT



57



Akan dibuktikan dim(Ker(D)) = co − rank(D)



Perhatikan bahwa Ker(D) = {f ∈ C1 (Γ) | Df = 0} merupakan subruang dari C1 (Γ). Karena C1 (Γ) berdimensi hingga, maka berlaku : dim C1 (Γ) = rank(D) + null(D) m = (n − c) + null(D) sehingga diperoleh null(D) = m − n + c = co − rank(Γ) Selanjutnya akan dibuktikan jika Q adalah cycle pada graf Γ, maka ξQ ∈ Ker(D).



Misal xQ = ξQ dimana ξQ direpresentasikan sebagai vektor kolom xQ . Perhatikan bahwa (DxQ )i merupakan hasil kali dalam baris di pada matriks insidensi D dan xQ . Akan dibuktikan (DxQ ) = 0



Tinjau dalam 2 kasus : 1. Titik vi tidak berinsidensi dengan sisi di Q. Perhatikan bahwa baris di berkorespondensi dengan titik vi . Karena vi tidak berinsidensi dengan sisi di Q, maka berdasarkan pendefenisian pada ξQ , nilai (xQ )i = 0. Sehingga diperoleh (DxQ )i = 0, untuk 1 ≤ i ≤ n. 2. Titik vi berinsidensi dengan sisi di Q, dimana vi berinsidensi dengan tepat dua sisi di Q. Tinjau semua kemungkinan orientasi pada Γ dan Q. Pilih salah satu arah orientasi pada Q. Kemudian bandingkan dengan 4 kemungkinan orientasi pada graf Γ.



Gambar 4.5: graf-4



BAB 4. CYCLE DAN CUT



58



Dengan pemberian nilai sesuai pendefenisian pada matriks insidensi D dan pada ξQ , maka dapat dilihat bahwa (DxQ )i = 0, untuk 1 ≤ i ≤ n.



Dari 1 dan 2, dapat disimpulkan DξQ = 0 sehingga ξQ ∈ Ker(D).



Contoh 4.5. Misalkan terdapat graf Γ seperti pada contoh 2,



Gambar 4.6: graf-3 diperoleh matriks insidensi 







+1 0 0 0 +1 0 0      −1 +1 0 0 0 −1 0      D =  0 −1 −1 0 0 0 +1       0 0 +1 −1 0 0 0    0 0 0 +1 −1 +1 −1



dan          ξQ =         Perhatikan hasil kali dalam (DxQ ) berikut :



0







  +1    −1    −1    0    +1   0



BAB 4. CYCLE DAN CUT



59 







+1 0 0 0 +1 0 0    −1 +1 0 0 0 −1 0    0 −1 −1 0 0 0 +1    0 0 +1 −1 0 0 0  0 0 0 +1 −1 +1 −1



               



0 +1 −1 −1 0 +1



               =           



0







  0    0    0   0



0 Tinjau titik v1 pada graf Γ yang tidak berinsidensi dengan sisi pada subgraf Q. Berdasarkan pendefenisian pada ξQ , maka entri tak nol pada baris d1 akan dikalikan dengan 0 di vektor xQ dan menghasilkan 0. Kemudian tinjau titik v2 , v3 , v4 , v5 yang berinsidensi dengan sisi pada subgraf Q. Maka berdasarkan pendefenisian pada ξQ , hasil kali entri-entri pada baris d2 , d3 , d4 , d5 dengan entri-entri di vektor xQ juga menghasilkan 0. Sehingga diperoleh DξQ = 0.Dan dapat disimpulkan bahwa ξQ ∈ Ker(D). Sebelumnya telah dijelaskan bahwa C1 (Γ) membentuk ruang vektor. Sekarang untuk setiap ρ dan σ di C1 (Γ), kita definisikan (ρ, σ) =



X



ρ(e)σ(e),



(4.6)



e∈EΓ



dimana garis atas menyatakan konjugat kompleks. Jika y = [y1 , y2 , . . . , ym ]t dan z = [z1 , z2 , . . . , zm ]t



(4.7)



berturut-turut adalah representasi dari ρ dan σ relatif terhadap basis standar di C1 (Γ), maka (ρ, σ) =



m X



yi zi = zt y,



(4.8)



i=1



yang merupakan hasil kali dalam standar di Cm . Jadi, C1 (Γ) juga merupakan ruang hasil kali dalam dengan hasil kali dalam seperti didefinisikan di atas. S.ubruang siklus dari Γ adalah kernel dari matriks insidensi dari Γ. Subruang pemisah dari Γ adalah komplemen orthogonal dari subruang siklus di C1 (Γ), relatif terhadap hasil kali dalam di C1 (Γ) yang didefinisikan di atas. Bagian pertama dari definisi di atas sudah dijustifikasi di Teorema 4.5, yang mengatakan bahwa semua vektor di C1 (Γ) yang merepresentasikan siklus di Γ termuat di



BAB 4. CYCLE DAN CUT



60



kernel dari matriks insidensi, yaitu subruang siklus. Pada bab berikutnya, akan dibuktikan bahwa subruang siklus juga memiliki basis yang setiap anggotanya adalah vektor di C1 (Γ) yang merepresentasikan siklus. Sekarang kita justifikasi bagian kedua dari definisi di atas. Misalkan V1 dan V2 sebarang partisi tak kosong dari V Γ, yaitu V1 dan V2 tak kosong, saling lepas, dan gabungannya sama dengan V Γ. Misalkan H adalah himpunan semua sisi di EΓ yang salah satu titik ujungnya ada di V1 dan ujung satunya di V2 . Jika H tidak kosong, H dikatakan pemisah di Γ. Dalam hal ini, kita katakan juga Γ memisahkan V1 dan V2 . Sekarang kita dapat memilih salah satu dari dua orientasi pemisah yang mungkin untuk H, dengan cara memilih salah satu diantara V1 dan V2 sebagai himpunan yang memuat semua ujung positif dari sisi-sisi di H dan yang satunya memuat semua ujung negatif. Selanjutnya, kita definisikan vektor ξH di C1 (Γ) yang merepresentasikan H sebagai berikut. Untuk setiap e di EΓ, ξH (e) = 1 jika e ∈ H dan orientasi pemisahnya di H sama dengan orientasinya di Γ, ξH (e) = −1 jika e ∈ H dan orientasi pemisahnya di H berlawanan dengan orientasinya di Γ, dan ξH (e) = 0 jika e tidak di H. Proposisi 4.6. Subruang pemisah dari Γ adalah ruang vektor berdimensi rank dari Γ. Jika H suatu pemisah di Γ, ξH termuat di subruang pemisah dari Γ. Bukti. Karena subruang pemisah adalah kompelemen orthogonal dari subruang siklus, maka subruang pemisah dari Γ adalah subruang dari C1 (Γ) yang dimensinya sama dengan dimensi C1 (Γ) dikurang dimensi dari subruang pemisah, yaitu m − (m − n + c) = n − c = r(Γ). Misalkan H pemisah di Γ dan V1 , V2 adalah partisi dari V Γ yang dipisahkan oleh H. Dengan demikian, setiap sisi H memuat tepat satu ujung di V1 dan satunya lagi di V2 . Jadi, jika xH adalah vektor kolom di Cm yang merepresentasikan ξH , kita punya   X X 1 xtH = ±  di − di  , 2 vi ∈V1



(4.9)



vi ∈V2



dengan di adalah baris dari matriks insidensi D yang berkorespondensi dengan titik vi . Tanda plus dan minus pada ruas kanan persamaan di atas hanya bergantung pada pemilihan orientasi pemisah untuk H. Sekarang jika ξ sebarang anggota subruang siklus dari Γ



BAB 4. CYCLE DAN CUT



61



dan z adalah vektor kolom yang merepresentasikan ξ, maka z ada di kernel dari matriks insidensi, yaitu Dz = 0. Akibatnya di z = 0 untuk setiap vi ∈ V Γ. Karena xtH adalah kombinasi linear dari di , maka xtH z = 0, dan akibatnya, (ξ, ξH ) = xtH z = 0. Jadi, ξH termuat di kompelemen orthogonal dari subruang siklus, yaitu subruang pemisah.



Sama seperti subruang siklus, subruang pemisah juga memiliki basis yang anggotanya merupakan vektor-vektor di C1 (Γ) yang merepresentasikan pemisah di Γ. Basis ini akan dijelaskan di bab berikutnya. Kita akhiri pembahasan siklus dan pemisah dengan hubungan sederhana antara matriks Laplacian Q = DDt dengan matriks ketetanggaan A dari Γ.



Proposisi 4.7. Misalkan D matriks insidensi dari (relatif terhadap suatu orientasi) dari graf Γ, dan misalkan juga A matriks ketetanggaan dari Γ. Maka matriks Laplacian Q memenuhi Q = DDt = ∆ − A,



(4.10)



dengan ∆ adalah matriks diagonal yang komponen pada diagonal ke-i adalah derajat dari titik vi , 1 ≤ i ≤ n. Akibatnya, Q tidak bergantung pada orientasi yang telah diberikan untuk Γ. Bukti. Misalkan D = [dij ] dan di adalah baris ke-i dari D. Kita punya t



(DD )ij =



m X



dik djk = dtj di ,



(4.11)



k=1



merupakan hasil kali dalam dari baris di dan dj . Jika i 6= j, kedua baris tersebut memiliki komponen tak nol di kolom yang sama jika dan hanya jika terdapat suatu sisi yang menghubungkan vi dan vj . Kolom tersebut adalah kolom yang berkorespondensi dengan sisi tersebut dan kedua komponen tak nol tersebut adalah +1 dan −1. Akibatnya, (DDt )ij = −1. Dengan cara yang sama, (DDt )ii adalah hasil kali dalam dari di dengan dirinya sendiri. Karena setiap komponen tak nol dari baris tersebut adalah ±1 yang banyaknya sama dengan derajat dari vi . Jadi, (DDt )ii = d(vi ). Akibatnya Q = DDt = ∆ − A,



(4.12)



BAB 4. CYCLE DAN CUT seperti yang diinginkan.



62



Bab 5



Pohon Pembangun Pohon adalah graf terhubung yang tidak mengandung siklus.



Graf terhubung adalah graf dimana untuk setiap dua titik pada graf tersebut selalu terdapat lintasan yang menghubungkan kedua titik itu.



Lintasan adalah perjalanan yang semua sisinya berbeda.



Jalur adalah perjalanan yang semua titiknya berbeda.



Pohon pembangun dari graf Γ adalah subgraf terhubung dari graf Γ yang mengandung semua titik dari graf Γ dan berupa pohon.



Siklus adalah lintasan yang berawal dan berakhir pada titik yang sama.



Cut dari graf terhubung Γ adalah himpunan sisi minimal yang bila dibuang dari graf Γ akan menyababkan graf Γ tidak terhubung lagi.



Permasalahan untuk mencari basis dari subruang siklus dan subruang cut sangatlah penting secara praktis dan teoritis. Permasalahan tersebut diselesaikan oleh Kirchoff (1847) dalam studinya tentang rangkaian listrik.



63



BAB 5. POHON PEMBANGUN



64



Table 5.1: Perbandingan Graf dan Pohon Pembangun



Pembahasan bab ini dibatasi hanya untuk graf yang terhubung, karena subruang siklus dan subruang cut untuk graf yang tidak terhubung adalah hasil tambah langsung dari ruang-ruang yang sesuai dari masing-masing komponen.



Gambar 5.1: Contoh graf Γ Misalkan Γ adalah sebuah graf terhubung yang telah diberi orientasi dengan n titik dan m sisi, maka r(Γ) = n − 1 dan s(Γ) = m − n + 1. Pohon pembangun di graf Γ adalah subgraf terhubung yang memiliki n − 1 sisi dan tanpa siklus. Simbol T menyatakan pohon pembangun maupun himpunan sisi-sisinya. Cyc(T, g) menyatakan siklus yang unik, sedangkan Cut(T, h) menyatakan cut yang unik. ξ(T,g) dan ξ(T,h) menyatakan elemen dari ruang sisi C1 (Γ).



BAB 5. POHON PEMBANGUN



65



Gambar 5.2: Contoh pohon pembangun T dari graf Γ Lema 5.1. Misalkan T adalah sebuah pohon pembangun dalam graf terhubung Γ, maka : (1) Untuk setiap sisi g dari Γ yang tidak termuat dalam T , ada siklus yang unik di Γ yang memuat g dan beberapa sisi di T . (2) Untuk setiap sisi h dari Γ yang termuat dalam T , ada cut yang unik di Γ yang memuat h dan beberapa sisi yang tidak termuat di T ( jika ada ). Bukti. (1) Ambil sebarang sisi g ∈ EΓ − T . Misalkan sisi g menghubungkan titik A dan titik B. Karena T pohon pembangun dari graf Γ maka T memuat titik A dan titik B. Karena T pohon maka terdapat lintasan pada T yang menghubungkan kedua titik tersebut. Lintasan yang menghubungkan titik A dan titik B pada pohon pembangun T membentuk siklus dengan sisi g. Akan dibuktikan siklus tersebut unik. Andaikan ada 2 siklus yang menghubungkan titik A dan titik B maka terdapat dua lintasan pada pohon pembangun T yang menghubungkan titik A dan titik B sehingga T bukan pohon. (2) Ambil sebarang sisi h ∈ T Misalkan sisi h menghubungkan titik A dan titik B pada pohon pembangun T, karena sisi h dibuang dari T maka titik A dan titik B pada pohon pembangun T menjadi tidak terhubung, tapi mungkin saja titik A dan titik B masih terhubung oleh lintasan pada graf Γ yang tidak ada pada pohon pembangun T, maka sisi h dan lintasan tersebut akan membentuk cut pada graf Γ. Akan ditunjukan cut tersebut unik.



BAB 5. POHON PEMBANGUN



66



Ambil sebarang sisi h ∈ T Misalkan sisi h menghubungkan titik A dan titik B. Andaikan ada 2 cut yaitu Cut(T, h) dan Cut(T, h’) maka titik A dan titik B dihubungkan oleh sisi h dan sisi h’. Karena ada dua sisi pada T yang menghubungkan titik A dan titik B maka T bukanlah pohon.



Teorema 5.2. Dengan hipotesis yang sama dengan Lema 5.1, maka : (1) Ketika g berjalan melalui himpunan EΓ - T, (m - n + 1) elemen ξ(T,g) membentuk suatu basis bagi subruang siklus dari Γ. (2) Ketika h berjalan melalui himpunan T, (n - 1) elemen ξ(T,h) membentuk suatu basis bagi subruang cut dari Γ. Bukti. Subruang siklus adalah kernel dari pemetaan insidensi. Pemetaan insidensi D : C1 (Γ) → C0 (Γ) Ker(D) = {f ∈ C1 (Γ) | Df = 0} Subruang siklus adalah Ker(D) Basis sub ruang siklus = {ξ(T,g) | g ∈ EΓ − T }. Subruangnya adalah X



αg ξ(T,g)



g∈(EΓ−T )



dengan α ∈ C



(1) Misalkan gi ∈ EΓ − T untuk i = 1, . . . , m − n + 1. Pandang kombinasi linier dari 0 = α1 ξ(T,g1 ) + ... + αm−n+1 ξ(T,gm−n+1 ) 0(gi ) = (α1 ξ(T,g1 ) + ... + αm−n+1 ξ(T,gm−n+1 ) )(gi ) 0 = α1 ξ(T,g1 ) (gi ) + ... + αi ξ(T,gi ) (gi ) + ... + αm−n+1 ξ(T,gm−n+1 ) (gi ) 0 = 0 + ... + αi ξ(T,gi ) (gi ) + ... + 0 0 = αi Jadi αi = 0 untuk i = 1, . . . , m − n + 1 sehingga elemen-elemen ξ(T,g) bebas linier. Karena elemen-elemen ξ(T,g) berkaitan dengan siklus-siklus, mengikuti dari teorema 4.5,



BAB 5. POHON PEMBANGUN



67



maka elemen-elemen tersebut milik subruang siklus. Akhirnya karena jumlah elemenelemen tersebut adalah m − n + 1 yang merupakan dimensi dari subruang siklus maka elemen-elemen tersebut membentuk basis bagi subruang siklus. (2) Hal ini dibuktikan menggunakan argumen yang serupa dengan yang dipakai dalam bukti pada bagian pertama.



Proposisi 5.3. (Poincare 1901) Sebarang submatriks persegi dari matriks insidensi D dari graf Γ memiliki determinan sama dengan 0 atau + 1 atau - 1. Bukti. : Matrik incidensi Dn×m dari    +1,   dij = −1,     0,



graf Γ dengan elemen-elemennya : jika vi tempat keluarnya panah pada sisi ej ; jika vi tempat masuknya panah pada sisi ej ; yang lain.



Contoh matriks insidensi dari graf  +1   −1   D= 0   0  0



pada gambar 5.1 0



0



0



0



−1



0







  0   −1 0 +1 +1 0 0   0 0 0 −1 0 +1  0 −1 −1 0 +1 −1



+1 +1



0



0



0



Misalkan S adalah suatu submatriks dari matriks D. Kasus 1 Jika setiap kolom S tidak memiliki entri tidak nol, maka det S = 0. Kasus 2 Jika setiap kolom dari S memiliki dua entri tak nol, maka entri tersebut haruslah + 1 dan - 1, karena masing-masing kolom harus memiliki entri-entri yang jumlahnya nol sehingga S matriks singulir, jadi det S = 0.



BAB 5. POHON PEMBANGUN



68



Kasus 3 Jika sebuah kolom dari S memiliki tepat satu entri tak nol. Dalam hal ini det S = ± det S 0 , dengan S’ memiliki satu baris dan satu kolom lebih sedikit daripada S. Proses ini dilanjutkan sampai pada akhirnya tiba pada determinan nol atau entri tunggal dari D.



Proposisi 5.4. Misalkan U adalah subhimpunan dari EΓ dengan | U | = n - 1. Submatriks (n-1) x (n-1) dari D, dinotasikan sebagai Du , terdiri atas perpotongan n-1 kolom dari D yang bersesuaian dengan sisi-sisi di U dan sebarang himpunan dari n-1 baris dari D. Du dapat dibalik jika dan hanya jika subgraf adalah pohon pembangun dari Γ. Bukti. : Misalkan subgraf adalah pohon pembangun dari Γ, maka submatriks Du terdiri atas (n-1) baris pada matriks insidensi D’ dari U. Karena subgraf adalah graf terhubung, maka rank D’ = n - 1 sehingga Du dapat dibalik. Sebaliknya, misalkan Du dapat dibalik. maka matriks insidensi D’ dari memiliki submatriks (n-1) x (n-1) yang dapat dibalik, konsekuensinya rank dari D’ adalah n - 1, ini berarti bahwa dimensi dari subruang siklus dari adalah nol, sehingga adalah pohon pembangun dari Γ.



Proposisi 5.5. Misalkan T adalah pohon pembangun dari graf Γ dan misalkan a dan b adalah sisi-sisi dari Γ sedemikian sehingga a ∈ T dan b ∈ / T maka : b ∈ Cut(T,a) jika dan hanya jika a ∈ Cyc(T,b) Bukti. : Hasil ini dapat diperoleh dari pendefinisian CT dan KT , serta fakta bahwa CT + KT t = 0. Misalkan T adalah pohon pembangun dari graf Γ. Matriks insidensi dari Γ dipartisi sebagai berikut :



BAB 5. POHON PEMBANGUN



69



 DT D=



DN dn



 



DT adalah matriks persegi berukuran (n − 1) × (n − 1) yang invertible, sedangkan dn bergantung linier. Misalkan C adalah matriks yang kolomnya berupa vektor yang mewakili elemen-elemen ξ(T,ej ) dengan n ≤ j ≤ m Kemudian C dapat ditulis dalam bentuk partisi :   CT  C= Im−n+1 Karena setiap kolom dari C mewakili sebuah siklus, konsekuensinya menjadi kernel dari D maka : DC=0 sehingga CT = −DT−1 DN Dengan cara yang serupa, matriks K adalah matriks yang kolomnya berupa vektor yang mewakili elemen-elemen ξ(T,ej ) dengan 1 ≤ j ≤ n − 1 dapat ditulis dalam bentuk partisi :   In−1  K= KT Karena masing-masing kolom dari matriks K adalah komplemen ortogonal dari subruang siklus maka CK t = 0 sehingga CT + K t = 0 jadi KT = (DT−1 DN )t



BAB 5. POHON PEMBANGUN



70



Contoh Aplikasi Pohon Pembangun : Suatu Rangkaian Listrik merupakan sebuah graf terhubung Γ yang memiliki karakteristik fisik tertentu, yang dinyatakan oleh dua buah vektor pada ruang sisi dari Γ yaitu vektor arus i dan vektor tegangan v. Vektor-vektor ini dihubungkan oleh persamaan linier v=Ri+E dimana R adalah matriks diagonal yang entri-entrinya adalah konduktansi dari sisi-sisi, sedangkan E mewakili sumber tegangan yang digunakan. Selanjutnya i dan v memenuhi persamaan : Di = 0C t v = 0 Kedua persamaan tersebut dikenal sebagai Hukum Kirchoff. Pilih pohon pembangun T di graf Γ dan partisi D dan C seperti penjelasan sebelumnya maka :  i=



iT iN



 



dan  v=



vT vN



 



Kemudian dari Di = 0 diperoleh DT i T + DN i N = 0 Karena CT = −DT−1 DN maka iT = CT iN dan i = C iN



BAB 5. POHON PEMBANGUN



71



Dengan kata lain, seluruh entri dari vektor arus dinyatakan oleh entri yang berkorespondensi dengan sisi-sisi di luar T. Substitusikan v = Ri + E dan sebelumnya kalikan dengan C t , Sehingga diperoleh (C t C) iN



= −C t E



Karena (C t RC ) adalah matriks persegi dengan ukuran yang sama dengan ranknya yaitu m-n+1, maka invertible. Sehingga dari persamaan ini diperoleh iN , konsekuensinya i juga dapat diperoleh dari i = CiN serta v dapat diperoleh dari v = Ri + E. Inilah metode yang sistematis untuk menyelesaikan persamaan rangkaian listrik.



Bab 6



The Tree Number Beberapa hasil yang terkenal pada teori graf aljabar adalah mencari banyaknya pohon pembangun pada suatu graf. Pada bab ini akan digunakan matriks laplacian untuk mendapatkan banyaknya pohon pembangun dari suatu graf sederhana.



Definisi 6.1 Misalkan Γ suatu graf dengan n titik. Pohon pembangun dari graf Γ adalah subgraf terhubung dari Γ yang banyaknya sisi adalah n − 1 dan tidak memuat siklus. Banyaknya pohon pembangun dari Γ dinamakan bilangan pohon dan dilambangkan dengan κ (Γ) .



Untuk graf tidak terhubung Γ, didefinisikan κ (Γ) = 0. Selanjutnya akan dibahas tentang sifat-sifat yang berkaitan dengan bilangan pohon dari suatu graf.



Lemma 6.2 Misalkan D matriks insidensi dari suatu graf Γ. Jika Q = DDt adalah matriks laplacian maka adjugate (matriks kofaktor) dari Q adalah perkalian matriks J dengan suatu skalar. Beberapa fakta yang diperlukan untuk membuktikan teorema: 1. Misalkan qij merupakan     d(vi )    qij = −1      0



entri dari Q maka berlaku , jika i = j , jika i 6= j dan vi bertetangga dengan vj , jika i 6= j dan vi tidak bertetangga dengan vj 72



BAB 6. THE TREE NUMBER



73



2. proposisi 4.3 3. rank(A) = rank(AAt ) untuk suatu A matriks berukuran n × n. Bukti: Akan ditunjukkan Ker(A) = Ker(At A) (i) Ambil v ∈ Ker(A) maka Av = 0, akibatnya At Av = 0. Jadi v ∈ Ker(At A) sehingga Ker(A) ⊂ Ker(At A) (ii) Ambil v ∈ Ker(At A) maka At Av = 0 ⇐⇒ v t At Av = 0 ⇐⇒ (Av)t Av = 0 ⇐⇒ kAvk2 = 0 ⇐⇒ Av = 0 jadi v ∈ Ker(A) sehingga Ker(At A) ⊂ Ker(A). Menurut (i) dan (ii) Ker(A) = Ker(At A). Karena rank(A) + dim(Ker(A)) = n = rank(At A) + dim(Ker(At A)) dan Ker(A) = Ker(At A) akibatnya rank(A) = rank(At A). Tetapi rank(A) = rank(At ) sehingga rank(A) = rank(At A) = rank(At A)t = rank(AAt ). Bukti: Misalkan kardinalitas titik dari Γ adalah n. Kasus Γ tidak terhubung Jika Γ tidak terhubung maka c ≥ 2, dengan c menyatakan banyaknya komponen dari Γ. Berdasarkan proposisi 4.3 rank(D) = n − c, akibatnya rank(Q) = rank(DDt ) = rank(D)< n − 1. Ambil Pn−1×n−1 sebarang submatriks dari Q, rank(P) ≤ rank(D) < n − 1, akibatnya det(P) = 0. Perhatikan bahwa elemen adjugate (Q) adalah cij = (−1)i+j det(Mij ), dengan Mij adalah submatriks dari Q yang berukuran n − 1 × n − 1, akibatnya cij = (−1)i+j det(Mij ) = (−1)i+j 0 = 0. Jadi adjugate(Q) = 0 = 0J. Kasus Γ terhubung Jika Γ terhubung maka rank(Q) = rank(D) = n − 1.



Karena Q = DDt , Q



simetri, akibatnya adjugate(Q) juga simetri, sehingga diperoleh bahwa adjugate(Q) = [adjugate(Q)]t = adjoint(Q). Berdasarkan sifat adjoint Q.adj(Q) = (det(Q)) .I



BAB 6. THE TREE NUMBER



74



Karena rank(Q) = n − 1, det(Q) = 0, dengan demikian Q.adj(Q) = 0. Jadi kolom dari adj(Q) ∈ Ker(Q). rank(Q) = n − 1 maka dim(Ker(Q)) = 1. Misalkan qij merupakan entri dari Q maka berlaku    d(vi ) , jika i = j    qij = −1 , jika i 6= j dan vi bertetangga dengan vj      0 , jika i 6= j dan vi tidak bertetangga dengan vj Misalkan u = [1, 1, ..., 1]t dan ambil [Qi ] sebarang baris dari Q maka [Qi ] u = d(vi ) + (−1)d(vi ) = 0, akibatnya Qu = 0 dan u ∈Ker(Q). Karena dim(Ker(Q)) = 1 dan 0 6= u ∈Ker(Q) maka {u} adalah pembangun dari Ker(Q).Dengan demikian, setiap kolom dari adj(Q) dapat dinyatakan sebagai perkalian dari u, yaitu adj(Q) = [k1 u k2 u ... kn u] . adj(Q) simetri, akibatnya k1 = k2 = ... = kn = k, jadi adjugate(Q) = adj(Q) = k [u u...u] = kJ.



Teorema Cauchy-Binet digunakan pada pembuktian teorema 6.3 Teorema Cauchy-Binet Misalkan A matrik berukuran k × n dan B matrik berukuran n × k. Maka det(AB) =



X



det(AJ ) det(BJ )



J



dengan J = (j1 , j2 , · · · , jk ), 1 ≤ j1 < j2 < · · · < jk ≤ n untuk semua himpunan indeks yang mungkin, AJ matriks yang diperoleh dari A dengan menggunakan kolom-kolom J (dengan urutan J), BJ matriks yang diperoleh dari B dengan menggunakan baris-baris J (dengan urutan J)



Untuk memahami teorema ini,  berikut  disajikan contoh penerapannya:   2 1   1 0 5   dan B =  A=  1 3 . Dengan demikian AJ dan BJ beruku  2 2 4 3 5 ran 2 × 2 untuk setiap J sehingga terdapat tiga buah submatrik A dan tiga



BAB 6. THE TREE NUMBER



75



buah submatrik B, yaitu:  AJ1



=  



AJ2



=  



AJ3



= 



1 0 2 2 1 5 2 4 0 5 2 4











 , BJ1 =  







 , BJ2 =  







 , BJ3 = 



2 1 1 3 2 1 3 5 1 3 3 5



     



sehingga dari perhitungan operasi matrik yang telah dikenal akan didapatkan det(AB) =



3 X



det(AJi ) det(BJi )



Ji =1



= (2).(5) + (−6)(7) + (−10)(−4) = 8 Teorema 6.3 Setiap entri kofaktor Q = DDT sama dengan bilangan pohon dari graf Γ, yaitu adjQ = κ(Γ)J Beberapa fakta yang diperlukan untuk membuktikan teorema: 1. Teorema Cauchy-Binet. 2. Proposisi 5.3 3. Proposisi 5.4 Bukti: Dari lemma 6.2 diperoleh bahwa setiap entri kofaktor dari Q sama. sehingga cukup ditunjukkan bahwa satu entri kofaktor Q sama dengan κ(Γ). Misalkan matrik keterkaitan graf Γ dituliskan dalam bentuk matrik blok sebagai berikut:   D0  D= d Dengan D0 merupakan matrik berukuran (n − 1) × n dan d matrik berukuran 1 × n. Dengan demikian diperoleh bahwa Dt =



h



D0t dt



i



BAB 6. THE TREE NUMBER



76



sehingga  DDt = 



D0 D0t D0 dt dD0t



ddt



 



Dengan demikian, matrik D0 D0t dapat diperoleh dengan cara menghapus baris dan kolom terakhir dari matrik DDt . Misal cnn entri baris ke n dan kolom ke n dari matrik Q. Maka cnn = (−1)n+n |D0 D0t | = |D0 D0t |. Karena setiap kofaktor Q bernilai sama, setiap entri dari matrik Q bernilai |D0 D0t | yang artinya adjQ = det(D0 D0t )J. Selanjutnya akan ditunjukkan bahwa det(D0 D0t ) = κ(Γ). Misal U ⊂ E(Γ) dengan |U | = n−1, Du merupakan submatrik D0 yang berukuran (n−1)×(n−1) yang kolom-kolomnya berkorespondensi dengan sisi di U . Dengan Teorema Cauchy-Binet diperoleh bahwa det(D0 D0t ) =



X



det(Du ) det(Dut ).



|U |=n−1



Dari proposisi 5.3, sebarang submatrik keterkaitan berukuran n × n determinannya bernilai 0, 1, atau -1. Karena Du ⊂ D0 ⊂ D, Du ⊂ D. Dengan demikian det(Du ) adalah 0,1 atau -1. Karena det(Du ) = det(Dut ), det(Du Dut ) adalah 0 atau 1. Berdasarkan proposisi 5.4, det(Du ) taknol jika dan hanya jika subgraf < U > spanning tree dari graf Γ. Jadi det(Du ) brnilai 1 jika subgraf < U > spanning tree Γ. Dengan demikian P det(Du ) det(Dut ) = κ(Γ). Jadi det(D0 D0t ) = κ(Γ).



Teorema 6.4(Temperley 1964) Misalkan Γ graf dengan n titik, bilangan pohon dari Γ adalah κ(Γ) = n−2 det(J + Q) Bukti: Beberapa fakta yang diperlukan untuk membuktikan teorema: 1. nJ = J2 . 2. JQ = 0 Bukti: Q dapat didefinisikan sebagai berikut:    d(vi ) , jika i = j    qij = −1 , jika i 6= j dan vi bertetangga dengan vj      0 , jika i 6= j dan vi tidak bertetangga dengan vj



BAB 6. THE TREE NUMBER



77



Dari definisi tersebut, Q merupakan matrik simetri dengan jumlah entri-entri tiap kolom dan barisnya adalah 0. Sehingga, JQ = 0. 3. adj(B)adj(A) = adj(AB) Bukti: telah diketahui Q−1 = (AB)−1 =



1 det(AB) adj(AB)



1 det(Q) adj(Q).



Sehingga,



⇐⇒



B −1 A−1



=



1 det(A) det(B) adj(AB)



⇐⇒



1 1 det(B) adj(B) det(A) adj(A)



=



1 det(A) det(B) adj(AB)



⇐⇒



adj(B)adj(A)



=



adj(AB)



4. Teorema Cayley yaitu κ(Kn ) = nn−2 . Bukti: Kn adalah graf yang terdiri dari n titik dimana setiap pasang titiknya dihubungkan dengan tepat satu sisi. Buktinya dengan menggunakan korespondensi 1-1 seperti diatas. Korespondensi itu dilakukan antara semua pohon pembangun Kn yang terdiri dari titik-titik v1 , v2 , . . . , vn dengan himpunan barisan a1 , a2 , . . . , an−2 dimana a1 adalah bilangan bulat yang memenuhi 1 ≤ ai ≤ n. jumlah semua kemungkinan yang diperoleh dari korespondensi itu adalah nn−2 , karena ada n cara untuk memilih a1 . (R.Gunawan Santosa,Dua metode pembuktian Teorema Cayley). 5. adjQ(Kn ) = adj(nI − J) = nn−2 J. Bukti: Pada graf lengkap Kn , derajat setiap titik (ditulis d(vi )) adalah n − 1, ∀vi ∈ Kn dan



BAB 6. THE TREE NUMBER



78



setiap titik bertetangga sehingga   n − 1 −1 −1   −1 n − 1 −1   . .. . Q(Kn ) =  . −1  .  . .. ..  . . .  .  −1 −1 · · ·   n 0 0 ··· 0   0 n 0 ··· 0   . . .. . =  . · · · ..  . 0  . . .. ..  . . . 0 .  . .  0 0 ··· ··· n



···







−1   ··· −1    ··· −1    ..  . −1   ··· n − 1     1 0 0     0 1 0     .  −  .. 0 . . .     . . ..   . . .   . .   0 0 ···



··· ··· ··· .. . ···



 0   0   ..  .     0   1



= nI − J Dari teorema Cayley diperoleh κ(Kn ) = nn−2 sehingga adjQ(Kn ) = nn−2 J.



6. adj(nQ) = nn−1 adj(Q). Bukti: Misalkan Q = [qij ] dan Mij merupakan submatriks Q yang diperoleh dengan cara menghapus baris ke i dan kolom ke j. Dengan cara yang sama, misalkan nQ = [nqij ] sehingga didapatkan Mij0 . Sehingga Mij0 = nMij det(Mij0 ) = det(nMij ) = nn−1 det(Mij ) = nn−1 (−1)i+j cij Misalkan c0ij = (−1)i+j det(Mij0 ). Dengan demikian berlaku c0ij



= (−1)i+j det(Mij0 ) = (−1)i+j nn−1 (−1)i+j cij = nn−1 cij



Dari lemma 6.2 diperoleh bahwa adjQ = kJ sehingga setiap entri adj(Q) bernilai sama. Dengan demikian ci j sama untuk setiap i, j = 1, 2, · · · , n. Akibatnya c0ij juga



BAB 6. THE TREE NUMBER



79



bernilai sama untuk setiap i, j = 1, 2, · · · , n. Dengan mengingat bahwa c0ij entri-entri dari matrik adj(Q) maka adj(nQ) = c0ij J = nn−1 cij J = nn−1 adj(Q) Dengan menggunakan fakta-fakta tersebut,akan dibuktikan teorema 6.4. (nI − J)(J + Q) = nJ − J 2 I + nQ − JQ = nQ selanjutnya, adj[(nI − J)(J + Q)]



=



adj(nQ) nn−1 adjQ



⇐⇒ adj(J + Q)adj(nI − J) = ⇐⇒



adj(J + Q)nn−2 J



=



nn−1 adjQ



⇐⇒



adj(J + Q)J



=



n · adj(Q)



⇐⇒



adj(J + Q)J



=



nκ(Γ)J



⇐⇒



(J + Q)adj(J + Q)J



=



(J + Q)nκ(Γ)J



⇐⇒



I det(J + Q)J



= nJκ(Γ)J + nQκ(Γ)J



⇐⇒



=



nκ(Γ)J 2



⇐⇒



=



n2 κ(Γ)J



=



n2 κ(Γ)



⇐⇒ Akibat 6.5



det(J + Q)



Misalkan 0 ≤ µ1 ≤ · · · ≤ µn−1 adalah spektrum Laplacian dari graf



Γ dengan n titik,berlaku κ (Γ) =



µ1 µ2 · · · µn−1 n



Jika Γ terhubung dan k−regular, dan spektrumnya adalah   k λ1 · · · λs−1  Spec Γ =  1 m1 · · · ms−1 maka κ (Γ) = n−1



s−1 Y



(k − λr )mr = n−1 χ0 (Γ; k)



r=1



Fakta yang diperlukan untuk membuktikan teorema:



BAB 6. THE TREE NUMBER 1.



80



Spectrum Laplacian. Misalkan µ0 ≤ µ1 ≤ · · · ≤ µn−1 adalah nilai eigen dari matriks Laplacian Q, maka berlaku (a) µ0 = 0 dengan vektor eigen [1, 1, . . . , 1] (b) Jika Γ terhubung maka µ1 > 0 (c) Jika Γ k−regular maka µi = k − λi , dimana λi adalah nilai eigen dari Γ.



2. Nilai eigen dari matriks diagonal merupakan entri-entri diagonalnya(Bill Jacob). 3. Polinom karakteristik. 4. Karena A simetri maka ada matriks tak singular P sehingga PAP−1 adalah matriks diagonal(Bill jacob). 5. Jika AB = BA maka ada matriks tak singular R sehingga RAR−1 dan RBR−1 (Horn, Analisis Matriks). Bukti Karena matriks Q dan J saling komutatif, nilai eigen J + Q adalah penjumlahan nilai eigen yang bersesuaian dari J dan Q. Nilai eigen dari J adalah n, 0, 0, . . . , 0 jadi nilai eigen dari J + Q adalah n, µ1 , µ2 , . . . , µn−1 . Akibatnya det (J + Q) = nµ1 µ2 . . . µn−1 sehingga dari proposisi 6.4 diperoleh κ (Γ) = n−2 nµ1 µ2 . . . µn−1 =



µ1 µ2 . . . µn−1 n



Berdasarkan pada additional result [4e] bagian c, diperoleh µi = k−λi dan bagian pertama pembuktian menunjukkan bahwa s−1



Y (k − λ1 )m1 (k − λ2 )m2 · · · (k − λs−1 )ms−1 κ (Γ) = = n−1 (k − λr )mr n r=1



kemudian akan ditunjukkan bahwa



s−1 Q



(k − λr )mr = χ0 (Γ; k). Perhatikan bahwa



r=1



χ (Γ; k) = (k − λ0 )m0 (k − λ1 )m1 (k − λ1 )m1 · · · (k − λs−1 )ms−1



BAB 6. THE TREE NUMBER



81



sehingga χ0 (Γ; k) = m0 (k − λ0 )m0 −1 (k − λ1 )m1 (k − λ2 )m2 · · · (k − λs−1 )ms−1 + d ((k − λ1 )m1 (k − λ2 )m2 · · · (k − λs−1 )ms−1 ) (k − λ0 )m0 = (k − λ0 )1−1 (k − λ1 )m1 (k − λ2 )m2 · · · (k − λs−1 )ms−1 + 0 = (k − λ1 )m1 (k − λ2 )m2 · · · (k − λs−1 )ms−1 =



s−1 Y



(k − λr )mr



r=1



Selanjutnya akan ditunjukkan beberapa penerapan dari akibat 6.5. Misalkan Γ adalah graf k−regular dengan n titik dan m =



1 2 nk



sisi, berdasarkan teorema 3.8 polinomial



karakteristik dari graf garisnya L (Γ), χ (L (Γ) ; λ) = (λ + 2)m−n χ (Γ; λ + 2 − k)



(6.1)



Graf garis L (Γ) adalah graf regular dengan derajat 2k−2. Akibat 6.5 menunjukkan bahwa κ (L (Γ)) = m−1 χ0 (L (Γ) ; 2k − 2) κ (Γ) = n−1 χ0 (Γ; k) Dengan mensubstitusi λ = 2k − 2 pada persamaan (6.1) , didapat χ0 (L (Γ) ; 2k − 2) = (2k)m−n χ0 (Γ; k) sehingga diperoleh bilangan pohon dari L (Γ) yaitu κ (L (Γ)) = m−1 (2k)m−n χ0 (Γ; k) = m−1 2m−n k m−n nκ (Γ) karena m =



nk 2



⇒



n m



=



2 k



maka κ (L (Γ)) =



2 m−n m−n 2 k κ (Γ) k



κ (L (Γ)) = 2m−n+1 k m−n−1 κ (Γ)



BAB 6. THE TREE NUMBER



82



Sebagai contoh, bilangan pohon dari graf segitiga ∆t = L (Kt ), dilihat terlebih dahulu graf Kt dengan n = t titik dan m =



t(t−1) 2



sisi dan (t − 1) −regular. Diketahui bahwa



(proposisi 3.5)  Spec (Kt ) = 



t−1



−1



1



t−1



 



Akibatnya L (Kt ) = ∆t mempunyai bilangan pohon κ (∆t ) = 2 =2 =2



t(t−1) −t+1 2 t2 −3t+2 2 t2 −3t+2 2



(t − 1)



t(t−1) −t−1 2



(t − 1)



t2 −3t−2 2



(t − 1)



t2 −3t−2 2







t



−1



κ (Kt ) (t − 1 + 1)



t−1







tt−2



Graf multipartite lengkap Ka1 ,a2 ,...,as mempunyai himpunan titik yang dipartisi ke dalam s bagian yaitu A1 , A2 , . . . , As , dimana |Ai | = ai (1 ≤ i ≤ s); dua vertek dihubungkan oleh sebuah sisi jika dan hanya jika keduanya berada pada partisi yang berbeda. Secara umum graf ini tidak regular, tapi komplemennya memuat komponen graf terhubung dan regular. Bilangan pohon dari graf semacam ini dapat ditentukan dengan memodifikasi proposisi 6.4. Hal ini didasarkan pada sifat-sifat dari fungsi karakteristik matriks Laplacian σ (Γ; µ) = det (µI − Q) Proposisi 6.6



(1) Jika Γ graf tak terhubung maka fungsi σ untuk Γ adalah



perkalian dari fungsi-fungsi σ untuk komponen Γ. (2) Jika Γ graf k−regular maka σ (Γ; µ) = (−1)n χ (Γ; k − µ), dimana χ adalah polinomial karakteristik dari matriks ketetanggaan (3) Jika Γc adalah komplemen Γ, dan Γ mempunyai n titik, maka κ (Γ) = n−2 σ (Γc ; n)



Bukti



(1) Misalkan Γ graf tak terhubung dengan jumlah komponen terhubung



sebanyak s, matriks keterkaitan dari Γ bisa dituliskan dalam bentuk partisi   D(1) 0 ··· 0      0 D(2) · · · 0     .. ..   . ··· .    0



0



···



D(s)



BAB 6. THE TREE NUMBER dengan matriks Laplaciannya 



83



Q (D1 )



   Q=   



···



0



Q (D2 ) · · ·



0 .. .



···



0



      



0 .. .



···



0







0



Q (Ds )



dimana Q(Di ) matriks laplacian untuk komponen ke-i,sehingga     µI − Q =    



µI − Q (D1 ) 0 .. . 0



···



0



µI − Q (D2 ) · · ·



0 .. .



0



··· 0



···



       



µI − Q (Ds )



diperoleh det (µI − Q) = det (µI − Q (D1 )) det (µI − Q (D2 )) · · · det (µI − Q (Ds ))       σ (Γ; µ) = σ1 Γ(1) ; µ σ2 Γ(2) ; µ · · · σs Γ(s) ; µ
dimana σi Γ(i) ; µ adala fungsi σ untuk komponen ke-i dari Γ. (2) Misalkan Γ adalah graf k−regular dan A adalah matriks ketetanggaannya, diperoleh Q = kI − A µI − Q = µI − (kI − A) = (µ − k) I − A = −1 (k − µ) I + A µI − Q = −1 ((k − µ) I − A) det (µI − Q) = det (−1 ((k − µ) I − A)) = (−1)n det ((k − µ) I − A) det (µI − Q) = (−1)n χ (Γ; (k − µ)) σ (Γ; µ) = (−1)n χ (Γ; (k − µ)) (3) Misalkan Γc adalah graf komplemen dari Γ, Jika Qc matriks Laplacian untuk Γc



BAB 6. THE TREE NUMBER



84



maka Q + Qc = nI−J. Berdasarkan proposisi 6.4 didapatkan κ (Γ) = n−2 det (J + Q) = n−2 det (nI − Qc ) = n−2 σ (Γc ; n) Misalkan graf multipartite lengkap Ka1 ,a2 ,...,as dimana a1 + a2 + · · · + as = n. Komplemen dari Ka1 ,a2 ,...,as memuat s komponen yang isomorfik dengan Ka1 , Ka2 , . . . , Kas dan (ai − 1) −regular. Berdasarkan proposisi 6.6 bagian (2) diperoleh σ (Ka ; µ) = (−1)a χ (Ka ; a − 1 − µ) h i = (−1)a ((a − 1 − µ) − (a − 1)) ((a − 1 − µ) − 1)a−1 h i = (−1)a (−µ) (a − µ)a−1 = (−1)a−1 µ (a − µ)a−1 σ (Ka ; µ) = µ (a − µ)a−1 Berdasarkan proposisi 6.6 bagian (1) dan (3) diperoleh κ (Ka1 ,a2 ,...,as ) = n−2 σ (Γc ; n) = n−2 (n) (n − a1 )a1 −1 · · · (n) (n − as )as −1 = ns−2 (n − a1 )a1 −1 · · · (n − as )as −1 Bilangan pohon graf bipartite lengkap Ka,b adalah κ (Ka,b ) = (a + b)2−2 (a + b − a)a−1 (a + b − b)b−1 = ba−1 ab−1 Graf hyperoctahedral Hs dengan jumlah titik 2s merupakan graf s−partite lengkap sehingga κ (Hs ) = (2s)s−2 (2s − 2)2−1 (2s − 2)2−1 · · · (2s − 2)2−1 = (2s)s−2 (2s − 2)s = 2s−2 ss−2 2s (s − 1)s = 22s−2 ss−2 (s − 1)s



Bab 7



Ekspansi Determinan Dalam bab ini akan dibahas mengenai polinom karakteristik χ, dan polinom σ yang diperkenalkan di Bab 6, dengan menggunakan ekspansi determinan. Diawali dengan memandang determinan matriks ketetanggaan A dari graf Γ. Misalkan V Γ = {v1 , v2 , · · · vn } dan baris-baris dan kolom-kolom dari A dilabeli sesuai dengan notasi tersebut. Ekspansi yang digunakan disini adalah definisi biasa dari determinan, yaitu: jika A = (aij ), maka X det(A) = sgn(π)a1,π1 a2,π2 · · · an,πn , dimana penjumlahannya atas semua permutasi π dari himpunan {1, 2, · · · n}.



Untuk menyatakan nilai yang muncul dalam ekspansi di atas dalam bentuk graf secara teoritik, akan diperkenalkan definisi baru. Definisi 7.1. Suatu graf elementer adalah graf sederhana, dimana setiap komponennya regular dan berderajat 1 atau 2. Dengan kata lain, setiap komponennya adalah sisi tunggal (K2 ) atau sikel (C2 ). Subgraf elementer pembangun dari Γ adalah subgraf elementer yang memuat semua titik di Γ. Misalkan Λ adalah graf elementer, x adalah banyaknya komponen yang berupa K2 , dan y banyaknya komponen yang berupa sikel, maka co-rank dari Λ adalah s (Λ) = m − n + c. Karena pada komponen yang berupa sikel banyaknya titik dan sisi sama, maka cukup dihitung jumlah titik dan sisi pada komponen yang berupa K2 . Banyaknya sisi pada K2 adalah 1 dan banyaknya titik adalah 2, sehingga s (Λ) = m − n + c = x − 2x + (x + y) = −x + x + y = y, yaitu banyaknya komponen yang berupa sikel.



85



BAB 7. EKSPANSI DETERMINAN



86



Proposisi 7.2. (Harary 1962) Misalkan A suatu matriks ketetanggaan dari graf Γ.



det(A) =



X



−1r(Λ) 2s(Λ) ,



dimana penjumlahannya atas semua subgraf elementer pembangun Λ dari Γ. Bukti. Diketahui: det(A) =



X



sgn(π)a1,π1 a2,π2 · · · an,πn ,



Bentuk sgn(π)a1,π1 a2,π2 · · · an,πn bernilai 0 jika terdapat i ∈ {1, 2, · · · n} sedemikian hingga a1,π1 = 0, yaitu jika {vi , vπi } bukan sisi dari Γ. Selanjutnya, jika sgn(π)a1,π1 a2,π2 · · · an,πn yang berkorespondensi ke permutasi π tidak nol maka π dapat disajikan secara tunggal sebagai komposisi sikel-sikel dengan panjang ≥ 2 yang tak saling beririsan, dimana (i). setiap sikel (ij) dengan panjang 2 berkorespondensi dengan faktor aij aji dan menyatakan sisi tunggal {vi , vj } di Γ (ii). setiap sikel (pqr · · · t) dengan panjang > 2 berkorespondensi dengan faktor apq aqr ars · · · atp dan menyatakan sikel {vp , vq , vr , · · · vt } di Γ. Akibatnya, setiap sgn(π)a1,π1 a2,π2 · · · an,πn yang tidak hilang di ekspansi determinan berupa subgraf elementer Λ dari Γ, dengan V Λ = V Γ Selanjutnya, tanda dari permutasi π adalah (−1)Ne , dengan Ne adalah jumlah sikel genap di π. Jika ada cl sikel dengan panjang l, X maka lcl = n menunjukkan bahwa jumlah N0 dari sikel ganjil kongruen ke n modulo 2. Sehingga, r(Λ) = n − (N0 + Ne ) = Ne mod2 Jadi tanda π = (−1)r(Λ) . Setiap subgraf elementer Λ dengan n titik memunculkan beberapa permutasi π yang berkorespondensi dengan ekspansi determinan yang tidak hilang. Jumlah π yang muncul dari Λ adalah 2s(Λ) karena untuk setiap komponen sikel di Λ ada dua cara memilih sikel yang berkorespondensi di π, sehingga



det(A) =



X



−1r(Λ) 2s(Λ) .



Contoh 7.3. Misalkan Γ = K4 . Subgraf-subgraf elementer pembangun dari K4 adalah



BAB 7. EKSPANSI DETERMINAN



87



C4 dan sepasang sisi yang tak beririsan sebagai berikut:



Gambar 7.1: K4 dan subgraf-subgraf elementer pembangunnya det(A) =



P



−1r(Λ) 2s(Λ) = 3((−1)3 21 ) + 3((−1)2 20 ) = −3.



Pada Proposisi 2.3 telah diperoleh beberapa koefisien pertama polinom karakteristik dari Γ. Proposisi berikut menyajikan perluasan dari hasil tersebut untuk seluruh koefisien polinom karakteristik dari Γ. Misalkan polinom karakteristik dari Γ adalah χ (Γ; λ) = λn + c1 λn−1 + c2 λn−2 + ... + cn . Proposisi 7.4. Koefisien dari polinom karakteristik diberikan oleh



(−1)i ci =



X



−1r(Λ) 2s(Λ) ,



dimana penjumlahannya atas semua subgraf elementer Λ dari Γ dengan i titik. Bukti. Pada Bab 2 telah dibahas bahwa (−1)i ci adalah jumlah dari determinan semua submatriks utama dari A dengan orde i, dengan i = 1, 2, · · · n. Tiap submatriks tersebut adalah deteminan matriks ketetanggaan dari subgraf yang diinduksi dari Γ. Tiap subgraf elementer dengan i titik termuat dalam tepat satu subgraf induksi tersebut, sehingga



BAB 7. EKSPANSI DETERMINAN



88



dengan menggunakan Proposisi 7. 1 diperoleh (−1)i ci =



X



−1r(Λ) 2s(Λ) ,



dengan Λ adalah subgraf elementer berorde i. Berdasarkan Proposisi 2.3, c1 = 0, −c2 = EΓ, dan −c3 merupakan dua kali banyaknya segitiga pada Γ akan dihitung dengan menggunakan Proposisi 7.3. Tidak ada subgraf elementer dengan 1 titik, sehingga c1 = 0. Subgraf elementer dengan 2 titik hanya berupa P2 yang memliki r (Λ) = 2 − 1 = 1 dan s (Λ) = 1 − 2 + 1 = 0 dan banyaknya subgraf P (−1)2 c2 = (−1)r(Λ) 2s(Λ)



elementer berupa P2 adalah EΛ = m, sehingga



⇔



1.c2



=



m (−1)1 20



⇔



c2



=



m. − 1.1



=



−m



=



m



⇔



−c2



= EΓ. Subgraf elementer dengan 3 titik hanya berupa K3 (segitiga) yang memiliki r (Λ) = 3 − 1 = 2 dan s (Λ) = 3 − 3 + 1 = 1. Misalkan banyaknya segitiga pada graf Γ adalah t, maka (−1)3 c3 =



P



(−1)r(Λ) 2s(Λ)



⇔



−1.c3



=



t (−1)2 21



⇔



−c3



=



t.1.2



= 2t yaitu dua kali banyaknya segitiga pada graf Γ. Untuk i = 4, subgraf elementer dengan 4 titik dapat berupa sepasang P2 yang disjoint memiliki r (Λ) = 4−2 = 2 dan s (Λ) = 2−4+2 = 0 atau C4 yang memiliki r (Λ) = 4−1 = 3 dan s (Λ) = 4 − 4 + 1 = 1. Misalkan na banyaknya pasangan sisi yang disjoint dan nb banyaknya C4 pada graf Γ, maka P (−1)4 c4 = (−1)r(Λ) 2s(Λ) ⇔



1.c4



⇔



c4



= na (−1)2 20 + nb (−1)3 21 =



na .1.1 + nb . − 1.2



=



na − 2nb



Selain ekspansi determinan matriks ketetanggaan A, akan dilakukan juga ekspansi fungsi karakteristik dari matriks Laplacian Q, yaitu σ (Γ; µ) = det (µI − Q). Walaupun



BAB 7. EKSPANSI DETERMINAN



89



entri-entri nondiagonal dari Q adalah entri dari matriks −A, tetapi ekspansi yang dilakukan pada A tidak dapat dilakukan pada Q karena entri-entri pada diagonal Q merupakan derajat dari masing-masing titik, sehingga submatriks utama dari Q bukan merupakan matriks Laplacian dari subgraf terinduksi dari Γ. Tulis σ (Γ; µ) = det (µI − Q) = µn + q1 µn−1 + ... + qn−1 µ + qn , dengan (−1)i qi merupakan jumlah dari determinan semua submatriks utama dari Q yang berukuran i × i. Karena entri-entri diagonal pada Q adalah derajat dari masing-masing titik pada Γ, maka (−1)1 q1 =



P



(Q)ii



⇔



−1.q1



=



2 |EΓ|



⇔



−q1



=



2 |EΓ|



⇔ q1 = −2 |EΓ| . Berdasarkan Teorema 6.3, setiap kofaktor dari Q sama dengan bilangan pohon dari Γ, yaitu κ (Γ). Kofaktor dari Q adalah determinan dari submatriks Q yang berukuran (n − 1) × (n − 1). Submatriks Q yang berukuran (n − 1) × (n − 1) ada sebanyak n buah, sehingga (−1)n−1 qn−1 =



nκ (Γ)



⇔ qn−1 = (−1)n−1 nκ (Γ) Karena rank (Q) < n − 1 < n, maka det (Q) = 0. Akibatnya, (−1)n qn = det (Q)



⇔



qn



=



0



=



0



Misalkan X, Y 6= ∅, X ⊆ V (Γ), dan Y ⊆ E(Γ). D(X, Y ) adalah submatriks dari matriks insidensi D dari Γ, didefinisikan oleh (i) baris-baris D(X, Y ) berkorespondensi dengan titik-titik di X (ii) kolom-kolom D(X, Y ) berkorespondensi dengan sisi-sisi di Y



Lema 7.5. Misalkan X, Y 6= ∅, X ⊆ V (Γ), dan Y ⊆ E(Γ), dengan |X| = |Y |. Misalkan V0 menyatakan himpunan titik dari hY i. D(X, Y ) dapat dibalik jika dan hanya jika pernyataan berikut berlaku: (1) X ⊆ V0 (2) hY i tidak memuat sikel



BAB 7. EKSPANSI DETERMINAN



90



(3) V0 \ X memuat tepat satu titik dari setiap komponen di hY i. Bukti. Misalkan D(X, Y ) dapat dibalik. (1)Andaikan X * V0 maka D(X, Y ) memuat baris nol sehingga D(X, Y ) tidak dapat dibalik. Kontradiksi dengan pernyataan bahwa D(X, Y ) dapat dibalik, jadi haruslah X ⊆ V0 . (2) Andaikan hY i memuat cycle, maka terdapat vektor z 6= ¯0 yang merepresentasikan cycle tersebut sedemikian sehingga D (V0 , Y ) z = 0. Karena z 6= ¯0, maka D (V0 , Y ) tidak dapat dibalik. Kontradiksi dengan pernyataan bahwa D (X, Y ) tidak dapat dibalik. Jadi, haruslah hY i tidak memuat cycle. Berdasarkan (1), X ⊆ V0 sehingga D(X, Y )z = 0 dan D(X, Y ) tidak dapat dibalik. Jadi haruslah tidak memuat sikel. (3) dari (2) diperoleh co-rankhY i = 0, yaitu s (hY i)



=



0



m−n+c



=



0



⇔ |Y | − |V0 | + c =



0



⇔ |X| − |V0 | + c =



0



⇔



⇔



c



= |V0 | − |X|



= |V0 \ X| Andaikan X memuat semua titik dari beberapa komponen dari hY i maka baris-baris di D(X, Y ) yang berkorespondensi akan berjumlah nol dan(X, Y ) tidak dapat dibalik. Karena V0 /X memuat beberapa titik dari tiap komponen di hY i dan |V0 \ X| = c , haruslah tepat satu titik dari tiap komponen.



Suatu graf Φ yang co-ranknya nol disebut hutan, yaitu gabungan komponen-komponen yang berupa pohon. Misalkan p(Φ) menyatakan hasil dari jumlah titik-titik komponen-komponen dari Φ. Secara khusus, jika Φ terhubung, Φ adalah pohon dan p(Φ) = |V Φ| Teorema 7.6. Koefisien qi dari polinom σ(Γ; µ) diberikan oleh



(−1)i qi =



X



p(Φ), (1 ≤ i ≤ n),



BAB 7. EKSPANSI DETERMINAN



91



dimana penjumlahannya atas semua subhutan Φ dari Γ yang memiliki i titik.



Bukti. Misalkan QX menyatakan submatkriks utama dari Q yang baris-baris dan kolomP kolomnya berkorespondensi dengan titik-titik di X, maka qi = detQX , dengan penjumlahannya atas semua X dengan |X| = i QX = D(X, Y )D(X, Y )t Berdasarkan Teorema Chaucy-Binet, diperoleh detQX = det(D(X, Y )D(X, Y )t ) X detQX = det(D(X, Y )detD(X, Y )t ) detQX =



Y X



(det(D(X, Y ))2



Y



qi =



X



(det(D(X, Y ))2



X,Y



dari Proposisi 5.3, (det(D(X, Y ))2 adalah 0 atau 1, dimana nilai 1 terpenuhi jika dan hanya jika berlaku 3 kondisi pada Lema 7.1. Untuk setiap hutan Φ ada p(Φ) cara untu menghilangkan satu titik dari tiap komponen dari Φ dan mengakibatkan ada sebanyak p(Φ) bernilai 1 di qi . Akibat 7.7. Bilangan pohon dari graf Γ diberikan



κ(Γ) = nn−2



X



p(Φ)(−n)−|EΦ| ,



Bukti. Berdasarkan hasil dari Proposisi 6.6 bagian 3, κ (Γ) = n−2 σ (Γc ; n). Misalkan P P P σ (Γc ; n) = qi nn−i = qi nn n−i = nn qi n−i , maka P P κ (Γ) = n−2 σ (Γc ; n) = n−2 nn qi n−i = nn−2 (−1)i p (Φ) n−i P P = nn−2 (−1)−i p (Φ) n−i = nn−2 p (Φ) (−1.n)−i P P = nn−2 p (Φ) (−n)−i = nn−2 p (Φ) (−n)−|EΦ| . Proposisi 7.8. Misalkan Γ suatu graf regular berderajat k, dan misalkan χ( i)(1 ≤ i ≤ n), menyatakan turunan ke-i polinom karakteristik dari Γ.



χ(i) (Γ; k) = i!



X



p(Φ),



BAB 7. EKSPANSI DETERMINAN



92



Bukti. Berdasarkan hasil dari Proposisi 6.6 bagian (2), σ(Γ; µ) = (−1)n−1 χ(Γ; κ − µ) n X n−1 σ(Γ; µ) = (−1) χ(i) (Γ; κ)(−µ)i /i! i=1



Karena σ(Γ; µ) = det(µI − Q) = n X



µn + q



1



µn−1 + · · · + q



n−1 µ + qn



i=1



n X



qn−i µi = (−1)n−1 χ(i) (Γ; κ)(−µ)i /i! i=1 X i=1 i Karena (−1) qi = p(Φ), (1 ≤ i ≤ n), diperoleh n n n X X X ((−1)n−i p(Φ))µi = (−1)n−1 χ(i) (Γ; κ)(−µ)i /i! i=1



i=1



i=1



n n n X X X i n−1 n (−1) (−µ) ( p(Φ)) = (−1) χ(i) (Γ; κ)(−µ)i /i! n X



i=1



i=1



=



n X



i=1



p(Φ) = χ(i) (Γ; κ)/i! i=1 X χ(i) (Γ; k) = i! p(Φ),



Untuk kasus i = 1, χ0 (Γ; κ) = (−1)n−1 qn−1 = nκ(Γ).



qn−i µi , dapat ditulis



Bab 8



Partisi-Titik dan Spektrum Pewarnaan-titik adalah salah satu masalah tertua dalam teori graf, yakni berupa pemberian warna pada titik sedemikian sehingga titik yang bertetangga berbeda warna. Hal ini dapat dipandang sebagai masalah mempartisi himpunan titik, seperti dijelaskan pada definisi berikut. Definisi 8.1. Partisi-warna dari graf umum Γ adalah partisi dari V Γ menjadi subhimpunansubhimpunan, disebut kelas-kelas-warna, V Γ = V1 ∪ V2 ∪ ... ∪ Vl , sehingga setiap Vi (1 ≤ i ≤ l) tidak memuat titik-titik yang bertetangga. Dengan kata lain, subgraf-terinduksi hVi i tidak memiliki sisi. Bilangan kromatik dari Γ, ditulis ν(Γ), adalah bilangan l terkecil sehingga partisi dengan syarat diatas terpenuhi. Definisikan pewarnaan-titik dari Γ adalah pemberian warna pada titik-titik, dengan sifat titik yang bertetangga berbeda warna. Sehingga sebuah perwarnaan-titik dengan l warna memberikan partisi-warna sebanyak l kelas-warna. Perhatikan graf Γ1 pada Gambar 8.1. Himpunan titik graf Γ1 adalah V Γ1 = {v1 , v2 , ..., v5 } yang bisa dipartisi menjadi 4 kelas-warna yaitu V1 = {v1 , v3 }, V2 = {v2 }, V3 = {v4 }, V4 = {v5 } dimana tiap kelas-warna tidak memuat titik yang bertetangga. Bilangan kromatik dari graf Γ1 adalah 3. Perhatikan graf Γ2 yang memuat loop pada Gambar 8.2(a). Graf tersebut memiliki titik yang bertetangga dengan dirinya sendiri, yaitu v1 , sehingga Γ2 tidak memiliki partisiwarna. 93



BAB 8. PARTISI-TITIK DAN SPEKTRUM



94



Gambar 8.1: Graf Γ1 .



(a) Graf Γ2 memuat loop



(b) Graf Γ3



Gambar 8.2: Bukan graf sederhana Jika graf memiliki beberapa sisi terkait pada dua titik yang bertetangga maka hanya satu sisi yang relevan dengan definisi partisi-warna, karena definisi hanya bergantung pada apakah titik-titik bertetangga atau tidak. Contohnya graf Γ3 pada Gambar 8.2(b), terdapat 4 sisi yang terkait pada titik v1 dan v2 . Kita dapat memilih salah satu sisi tersebut, misalnya e1 sebagai sisi yang relevan dengan definisi partisi-warna. Jadi untuk sementara ini kita lanjutkan dengan berhadapan dengan graf yang sederhana. Jika ν(Γ) = 1, maka Γ tidak memiliki sisi (perhatikan graf Γ4 pada Gambar 8.3). Jika ν(Γ) = 2, maka Γ graf bipartit(sebaliknya tidak berlaku). Perhatikan graf bipartit lengkap K3,3 pada Gambar 8.4, bilangan kromatiknya 2. Karena siklus dengan panjang ganjil tidak dapat diwarnai dengan 2 warna, maka graf bipartit tidak memuat siklus ganjil.



BAB 8. PARTISI-TITIK DAN SPEKTRUM



95



Gambar 8.3: Graf Γ4 (graf tidak memuat sisi).



Gambar 8.4: Graf Bipartit Lengkap K3,3



Proposisi 8.2. Misal graf bipartit Γ memiliki nilai karakteristik λ dengan multisiplitas m(λ) maka −λ juga nilai karakteristik dari Γ dan m(λ) = m(−λ). Bukti. Polinom karakteristik dari graf Γ adalah χ(Γ; λ) = λn + c1 λn−1 + c2 λn−2 + ... P dengan koefisiennya adalah (−1)i ci = (−1)r(Λ) 2s(Λ) (-berdasarkan Proposisi 7.3) dimana penjumlahannya atas seluruh subgraf elementer Λ dari graf Γ dengan i titik. Jika Γ graf bipartit maka Γ tidak memiliki siklus ganjil, sehingga tidak ada subgraf elementernya yang memiliki jumlah titik ganjil. Oleh karena itu, polinom karakteristiknya berbentuk χ(Γ; λ) = λn + c2 λn−2 + c4 λn−4 + .... Untuk n ganjil, tulis n = 2k + 1 untuk suatu k. χ(Γ; λ) = λ(λn−1 + c2 λn−3 + c4 λn−5 + ...) = λ(λ(2k+1)−1 + c2 λ(2k+1)−3 + c4 λ(2k+1)−5 + ...) = λ(λ2k + c2 λ2k−2 + c4 λ2k−4 + ...) = λ((λ2 )k + c2 (λ2 )k−1 + c4 (λ2 )k−2 + ...) = λp(λ2 )



BAB 8. PARTISI-TITIK DAN SPEKTRUM



96



Untuk n genap, tulis n = 2k untuk untuk suatu k. χ(Γ; λ) = λn + c2 λn−2 + c4 λn−4 + ... = λ(2k) + c2 λ(2k)−2 + c4 λ(2k)−4 + ... = (λ2 )k + c2 (λ2 )k−1 + c4 (λ2 )k−2 + ... = λ0 ((λ2 )k + c2 (λ2 )k−1 + c4 (λ2 )k−2 + ...) = λ0 p(λ2 )   0, n genap; Dengan demikian, diperoleh χ(Γ; λ) = λδ p(λ2 ) dengan δ = .  1, n ganjil. Jadi nilai karakteristiknya (yaitu saat χ(Γ; λ) = 0) memiliki sifat yang diinginkan. Spektrum dari graf lengkap Ka,b dapat dicari dengan cara berikut. Kita misalkan titik-titik pada Ka,b dilabeli sedemikian sehingga matriks ketetanggaannya adalah  A=



0



J



Jt



0



 ,



dengan J adalah matiks a × b dengan entri-entri +1. Matriks A hanya memiliki dua baris yang bebas linier, sehingga memiliki rank 2. Akibatnya 0 adalah nilai eigen dari A dengan multiplisitas a + b − 2. Jadi polinom karakteristik berbentuk λa+b−2 (λ2 + c2 ). Dengan Proposisi 2.3, −c2 adalah banyaknya sisi dari Ka,b , yakni ab. Oleh karena itu,



SpecKa,b



 √ √  ab 0 ab . = 1 a+b−2 1



Selanjutnya kita akan melihat hasil-hasil tentang bilangan kromatik dari pengetahuan kita akan nilai eigen. Untuk sebarang matriks simetri M, definisikan λmax (M) sebagai nilai karakteristik terbesar dan λmin (M) sebagai nilai karakteristik terkecil dari M. Jika M matriks ketetanggaan dari Γ maka kita notasikan λmax (M) = λmax (Γ) dan λmin (M) = λmin (Γ). Dari Proposisi 8.2, untuk graf bipartit Γ, λmin (Γ) = −λmax (Γ). Sebagai contoh, perhatikan graf bipartit lengkap K2,2 pada Gambar 8.5. Akan dicari nilai karakteristik, multisiplitas nilai karakteristik, nilai karakteristik minimum, dan nilai



BAB 8. PARTISI-TITIK DAN SPEKTRUM



97



Gambar 8.5: Graf Bipartit Lengkap K2,2



karakteristik maksimumnya. Matriks ketetanggaan dari graf K2,2 tersebut adalah   0 0 1 1      0 0 1 1  . A=    1 1 0 0    1 1 0 0 Persamaan karakteristik graf K2,2 adalah χ(K2,2 ; λ) = λ2 (λ2 − 4), maka nilai karakteristik dan multiplisitas nilai karakteristik graf K2,2 yaitu λ1 = 2, m(λ1 ) = 1 λ2 = 0, m(λ2 ) = 2 λ3 = −2, m(λ3 ) = 1 Sehingga diperoleh, λmax (K2,2 ) = −λmin (K2,2 ). Misal (x, y) menotasikan hasil kali dalam dari vektor kolom x dan y. Untuk sebarang matriks real simetri berukuran n×n dan vektor kolom real taknol berukuran n×1, bilangan (z,Xz) (z,z)



disebut kuosien Rayleigh dan ditulis R(X; z). Dalam teori matriks terbukti bahwa



λmax (X) ≥ R(X, z) ≥ λmin (X) untuk setiap z 6= 0. Proposisi 8.3. 1. Jika Λ adalah subgraf-terinduksi dari Γ maka λmax (Λ) ≤ λmax (Γ); λmin (Λ) ≥ λmin (Γ). 2. Jika kmax (Γ) adalah derajat terbesar titik Γ, kmin (Γ) adalah derajat terkecil titik Γ, dan kave (Γ) adalah derajat rata-rata maka kmax (Γ) ≥ λmax (Γ) ≥ kave (Γ) ≥ kmin (Γ).



BAB 8. PARTISI-TITIK DAN SPEKTRUM



98



Bukti. 1. Titik-titik dari Γ dilabeli sedemikian sehingga matriks ketetanggaan A dari Γ mempunyai submatriks utama pemuka A0 , yaitu matriks ketetanggaan dari Λ. Pilih z0 sehingga A0 z0 = λmax (A0 )z0 dan (z0 , z0 ) = 1. Selanjutnya, misalkan z vektor kolom dengan |V Γ| baris yang dibentuk dengan menambahkan entri bernilai nol ke z0 . Sehingga λmax (A0 )z0



= A 0 z0



(z0 , λmax (A0 )z0 ) = (z0 , A0 z0 ) (z0 , A0 z0 ) (z0 ,λmax (A0 )z0 ) = (z0 ,z0 ) (z0 , z0 ) λmax (A0 ) = R(A0 z0 ) Karena z adalah vektor kolom dengan |V Γ| baris yang dibentuk dengan menambahkan entri bernilai nol ke z0 maka λmax (Λ) = R(A0 ; z0 ) =



(z0 , A0 z0 ) (z, Az) = = R(A; z) ≤ λmax (A) = λmax (Γ). (z0 , z0 ) (z, z)



Dengan cara yang sama diperoleh, λmin (Γ) ≤ λmin (Λ). 2. Misal u adalah vektor kolom yang setiap entrinya bernilai +1. Maka, jika n = |V Γ| dan k (i) adalah derajat dari titik vi , diperoleh R(A; u) =



(u, Au) 1X 1 X (i) = aij = k = kave (Λ). (u, u) n n i,j



i



Sehingga diperoleh, λmax (Γ) = λmax (A) ≥ R(A, u) = kave (Γ) ≥ kmin (Γ). Sekarang, misalkan x adalah vektor karakteristik yang berkorespondensi dengan nilai karakteristik λ0 = λmax (Γ) dan xj adalah entri positif terbesar dari x. Dengan P0 argumen yang sama di Proposisi 3.1, diperoleh λ0 xj = (λ0 x)j = xi ≤ k (j) xj ≤ P0 kmax (Γ)xj , dimana penjumlahan dihitung berdasarkan titik vi yang bertetangga



BAB 8. PARTISI-TITIK DAN SPEKTRUM



99



dengan vj . Sehingga diperoleh, λ0 ≤ kmax (Γ). Maka, terbukti bahwa jika kmax (Γ) adalah derajat terbesar titik Γ, kmin (Γ) adalah derajat terkecil titik Γ, dan kave (Γ) adalah derajat rata-rata maka kmax (Γ) ≥ λmax (Γ) ≥ kave (Γ) ≥ kmin (Γ).



Selanjutnya kita membatasi bilangan kromatik dari Γ melalui bentuk λmax (Γ) dan λmin (Γ). Sebuah graf Γ disebut l − kritikal jika ν(Γ) = l dan untuk setiap subgrafterinduksi Λ 6= Γ berlaku ν(Γ) < l. Lema 8.4. Misalkan Γ graf dengan bilangan kromatik l ≥ 2. Maka Γ memuat sebuah subgraf-terinduksi l-kritikal Λ, dan setiap titik dari Λ berderajat setidaknya l − 1 di Λ. Bukti. Himpunan subgraf-terinduksi dari Γ tidak kosong. Himpunan ini memuat graf dengan bilangan kromatik l (graf Γ) dan graf dengan bilangan kromatik bukan l (graf dengan satu titik). Misal Λ adalah subgraf-terinduksi dengan bilangan kromatik l, yang minimal terhadap banyaknya titik, maka Λ l-kritikal. Jika v sebarang titik dari Λ, maka hV Λ\vi adalah subgraf-terinduksi dari Λ dan memiliki pewarnaan-titik dengan l−1 warna. Jika derajat dari v di Λ kurang dari l − 1, maka pewarnaan-titik ini dapat juga dilakukan pada graf Λ, kontradiksi dengan ν(Λ) = l. Haruslah derajat dari setiap titik di graf Λ setidaknya l − 1. Proposisi 8.5. (Wilf 1967) Untuk sebarang graf Γ diperoleh ν(Γ) ≤ 1 + λmax (Γ). Bukti. Berdasarkan Lema 8.4 diperoleh bahwa terdapat subgraf terinduksi Λ dari graf Γ sehingga ν(Λ) = ν(Γ) dan kmin (Λ) ≥ ν(Γ) − 1. Menggunakan pertidaksamaan pada Proposisi 8.3 diperoleh ν(Γ) ≤ kmin (Λ) + 1 ≤ λmax (Λ) + 1 ≤ λmax (Γ) + 1



Lema 8.6. Misal X matriks real simetri yang dipartisi menjadi   P Q , X= Qt R



BAB 8. PARTISI-TITIK DAN SPEKTRUM



100



dimana P dan R adalah matriks simetri. Maka λmax (X) + λmin (X) ≤ λmax (P) + λmax (R). Bukti. Misalkan λ = λmin (X) dan  > 0. Maka X∗ = X − (λ − )I sebuah matriks simetri yang definit-positif. Matriks X∗ dipartisi dengan cara seperti X menjadi P∗ = P−(λ−)I, Q∗ = Q, dan R∗ = R − (λ − )I. Dengan mengaplikasikan metode kuosien Rayleigh ke matriks X∗ , bisa ditunjukkan bahwa λmax (X∗ ) ≤ λmax (P∗ ) + λmax (R∗ ). Maka, dalam bentuk X, P, dan R menjadi λmax (X∗ ) = λmax (X − (λ − )I) = λmax (X) − (λ − ) ≤ λmax (P∗ ) + λmax (R∗ ) = λmax (P − (λ − )I) + λmax (R − (λ − )I) = λmax (P) − (λ − ) + λmax (R) − (λ − ) Diperoleh, λmax (X) − (λ − ) ≤ λmax (P) − (λ − ) + λmax (R) − (λ − ). Karena  sangat kecil dan λ = λmin (X), maka λmax (X) − λ



≤ λmax (P) − λ + λmax (R) − λ



λmax (X) + λ



≤ λmax (P) + λmax (R)



λmax (X) + λmin (X) ≤ λmax (P) + λmax (R)



Akibat 8.7. Misal A matriks real simetris yang dipartisi menjadi t2 submatriks Aij sedemikian sehingga partisi baris dan kolomnya sama; dengan kata lain, setiap submatriks diagonal Aii (1 ≤ i ≤ t) adalah matriks persegi. Maka λmax (A) + (t − 1)λmin (A) ≤



t X



λmax (Aii ).



i=1



Bukti. Pembuktian melalui induksi pada t. Saat t = 2, λmax (A) + λmin (A) ≤ λmax (A11 ) + λmax (A22 ) (sesuai dengan Lema 8.6). Asumsikan benar untuk t = T −1. Akan ditunjukkan



BAB 8. PARTISI-TITIK DAN SPEKTRUM



101



benar untuk t = T . Misal A dipartisi menjadi T 2 submatriks. Misal B adalah matriks A yang baris dan kolom terakhirnya dihapus. Berdasarkan Lemma 8.6, λmax (A)+λmin (A) ≤ λmax (B) + λmax (AT T ). Berdasarkan asumsi hipotesis, λmax (B) + (T − 2)λmin (B) ≤ PT −1 i=1 λmax (Aii ). Berdasarkan Proposisi 8.3, λmin (B)



≥ λmin (A)



⇔ (T − 2)λmin (B) ≥ (T − 2)λmin (A). Dari dua pertaksamaan tersebut diperoleh, λmax (B) + (T − 2)λmin (A) ≤ λmax (B) + (T − 2)λmin (B) ≤



T −1 X



λmax (Aii )



i=1



Sehingga diperoleh, λmax (B) ≤



T −1 X



λmax (Aii ) − (T − 2)λmin (A).



i=1



Oleh karena itu, λmax (A) + λmin (A) ≤ λmax (B) + λmax (AT T ) ≤



=



T −1 X i=1 T X



λmax (Aii ) − (T − 2)λmin (A) + λmax (AT T ) λmax (Aii ) − (T − 2)λmin (A)



i=1



Akhirnya diperoleh, λmax (A) + λmin (A) + (T − 2)λmin (A) ≤ λmax (A) + (T − 1)λmin (A)



≤



T X i=1 T X



λmax (Aii )



λmax (Aii )



i=1



Teorema 8.8. Untuk sebarang graf Γ yang himpunan sisinya tidak kosong, ν(Γ) ≥ 1 + λmax (Γ) −λmin (Γ)



BAB 8. PARTISI-TITIK DAN SPEKTRUM



102



Bukti. Himpunan V Γ dapat dipartisi menjadi ν = ν(Γ) kelas warna, konsekuensinya matriks ketetanggaan A dari Γ dapat dipartisi menjadi ν 2 submatriks (seperti pada Akibat 8.7). Dalam hal ini, Aii (1 ≤ i ≤ ν) bernilai nol, maka λmax (Aii ) = 0(1 ≤ i ≤ ν). Dengan mengaplikasikan Akibat 8.7, diperoleh λmax (A) + (ν − 1)λmin (A) ≤



ν X



λmax (Aii )



i=1



=0 Tetapi, jika Γ memiliki setidaknya satu sisi, maka λmin (A) = λmin (Γ) < 0. Sehingga diperoleh, λmax (A) + (ν − 1)λmin (A)



≤0



λmax (A) + νλmin (A) − λmin (A) ≤ 0 λmax (A) − λmin (A)



≤ −νλmin (A) −νλmin (A) ≤ −λmin (A)



λmax (A)−λmin (A) −λmin (A) λmax (A) −λmin (A)



≤ν



+1



Jadi, terbukti bahwa untuk sebarang graf Γ yang himpunan sisinya tidak kosong, ν(Γ) ≥ 1 +



λΓ −λmin (Γ)



.



Bab 9



Graf Automorfisma 9.1



Pendahuluan



Dalam bab ini akan dibahas mengenai beberapa istilah yang berhubungan dengan Automorfisma Graf. Definisi 9.1. Misalkan G dan G adalah graf sederhana dengan himpunan titik berturutturut adalah V (G) dan V (G0 ), dan himpunan garis berturut-turut adalah E(G) dan E(G0 ). G dikatakan isomorfik dengan G0 jika dan hanya jika terdapat pemetaan 1−1 dan pada dari V (G) ke V (G0 ), ϕ : V (G) → V (G0 ), dengan xy ∈ E (G) ⇔ ϕ (x) ϕ (y) ∈ E (G0 ) ∀x, y ∈ V (G).



Dengan kata lain Ismorfisma Graf mengawetkan keteteanggaan dari graf G, yaitu jika dua titik, misal u dan v, bertetangga pada G maka ϕ (x) dan ϕ (y) akan bertetangga di G0 . Contoh 9.2. Misalkan graf G dan G0 adalah graf seperti yang digambarkan pada gambar 15.1. Graf G isomorfik dengan G0 karena terdapat ϕ : V (G) → V (G0 ) yang 1-1 dan pada. Pemetaan tersebut seperrti terlihat pada gambar 15.2. Contoh 9.3. Misalkan Graf X dan X 0 adalah graf seperti pada gambar 15.3. Graf X isomorfik dengan X 0 karena terdapat g : V (G) → V (G0 ) yang 1-1 dan pada. Pemetaan tersebut seperti terlihat pada gambar di bawah ini



103



BAB 9. GRAF AUTOMORFISMA



104



Gambar 9.1: Graf G isomorfik dengan G0



Gambar 9.2: Pemetaan 1-1 dan pada dari V (G) ke V (G0 ) dan E (G) ke E (G0 )



Gambar 9.3: Graf G dan G0 Definisi 9.4. Matriks P ∈ C n×n disebut matriks permutasi jika setiap barisnya hanya mengandung satu komponen tak nol yang sama dengan 1 dan juga kolomnya hanya mengandung satu komponen yang sama dengan 1.



BAB 9. GRAF AUTOMORFISMA



105



Gambar 9.4: Pemetaan 1-1 dan pada dari V (G) ke V (G0 ) Contoh 9.5. 



1 0 0 0







     0 0 1 0    P =   0 1 0 0    1 0 0 0 Definisi 9.6. Misalkan λ0 > λ1 > · · · > λs−1 adalah nilai eigen yang berbeda. Misalkan χ(A; λ) = (λ − λ0 )m0 (λ − λ1 )m1 · · · (λ − λs−1 )ms−1 . Maka mi adalah multiplisitas aljabar dari λi untuk setiap i ∈ {0, 1, · · · , s − 1}. Ketika nilai mi = 1 , maka λi disebut nilai eigen sederhana Definisi 9.7. Graf Ladder Lh (h ≥ 3) adalah graf regular berderajat 3 dengan 2h titiktitik u1 , u2 , . . . , uh , v1 , v2 , . . . , vh ; dengan titik-titik u1 , u2 , . . . , uh dari lingkaran dengan panjang h, titik-titik v1 , v2 , . . . , vh juga dari lingkaran dengan panjang h, dan sisi sisanya berasal dari bentuk {ui , vi } , 1 ≤ i ≤ h.



Berikut ini adalah gambaran dari graf Ladder L3 Definisi 9.8. Graf Mobius Ladder adalah graf regular berderajat 3 dengan titik-titik 2h, (h ≥ 3).



BAB 9. GRAF AUTOMORFISMA



106



Gambar 9.5: Ladder Graph L3



9.2



Graf Automorfisma



Definisi 9.9. Automorfisma dari suatu graf (sederhana) G adalah suatu permutasi π dari V G yang mempunyai sifat {u, v} adalah sisi pada G jika dan hanya jika {π(u), π(v)} adalah sisi di G. Dengan kata lain graf automorfisma adalah graf yang isomorfik dengan dirinya sendiri. Himpunan semua automorfisma di G, dinotasikan Auth (G).



Gambar 9.6: Graf G



Contoh 9.10. Misal G adalah graf yang digambarkan seperti pada gambar 15.6. Himpunan semua automorfisma dari graf G adalah Auth (G) = {π1 , π2 , π3 , π4 } di mana π1 = (1) (2) (3) (4) (5) (6), π2 = (1) (2) (3) (4) (56), π3 = (14) (23) (5) (6), dan π4 = (14) (23) (56). Definisi 9.11. Dua titik x dan y dikatakan berada dalam orbit yang sama jika terdapat suatu automorfisma α sedemikian sehingga α(x) = y. Akibatnya x dan y mempunyai derajat yang sama.



BAB 9. GRAF AUTOMORFISMA



107



Gambar 9.7: Automorfisma-automorfisma dari graf G Definisi 9.12. Graf G dikataan transitif titik jika Auth (G) beraksi secara transitif di V G, yaitu, jika hanya terdapat satu orbit. Ini berarti bahwa jika diberikan 2 buah titik u dan v maka terdapat suatu automorfisma π di Auth (G) sedemikian sehingga π (u) = v. Definisi 9.13. Graf G dikataan transitif-sisi jika aksi V G pada EG dengan aturan π {x, y} = {π (x) , π (y)}. Dengan kata lain, jika diberikan sebarang pasangan sisi maka terdapat suatu automorfisma yang mentransformasikan satu ke yang lainnya. Graf tangga (ladder graph) L3 adalah salah satu contoh graf yang transitif-titik tapi tidak transitif-sisi, graf tangga (ladder graph) L3 . Proposisi 9.14. Jika suatu graf terhubung adalah transitif-sisi tapi tidak transitif titik, maka graf tersebut bipartite. Bukti. Misal {x, y} adalah sisi pada graf G, dan misalkan X dan Y menotasikan orbit-orbit yang memuat x dan y berturut-turut di bawah aksi Auth (G) pada titik-titik. Berdasarkan definisi dari suatu orbit bahwa X dan Y adalah disjoin atau identik. Karena G graf terhubung, setiap titik z ada dalam suatu sisi {z, w}, dan karena graf G adalah transitifsisi, z berada di X atau Y . Sehingga X ∪ Y = V G. Jika X = Y = V G maka G akan menjadi transitif-titik, kontradiksi dengan hipotesis; akibatnya X ∩ Y kosong. Setiap sisi di G punya satu titik ujung di X dan satu titik ujung di Y , jadi G bipartite. Graf bipartite lengkap Ka,b dengan a 6= b adalah suatu contoh yang jelas dari graf yang transitif-sisi tapi tidak transitif-titik. Dalam hal ini graf nya bukan graf regular, dan tidak



BAB 9. GRAF AUTOMORFISMA



108



transitif-titik untuk alasan tersebut, karena jelas bahwa suatu dalam suatu graf transitif titik setiap titik harus mempunyai derajat yang sama.



Proposisi selanjutnya membuat suatu hubungan antara spektrum dari suatu graf dengan grup automorfismanya. Kita bisa menganggap bahwa V G adalah himpunan {v1 , v2 , ..., vn }, dan bahwa baris dan kolom dari matriks ketetanggan dari G di labeli sesuai cara yang biasa. Suatu permutasi π dari graf V G dapat direpresentasikan (digambarkan) dengan matriks permutasi P = (pij ), di mana pij = 1 jika vi = π (vj ), dan pij = 0 untuk selainnya. Proposisi 9.15. Misal A adalah matriks ketetanggaan dari suatu graf G, dan π adalah permutasi dari V G. Maka π adalah suatu automorfisma dari G jika dan hanya jika P A = AP , di mana P adalah matriks permutasi yang menggambarkan π. Bukti. Misal vh = π (vi ) dan vk = π(vj ). Maka kita punya P (P A)hj = phl alj = aij ; P (AP )hj = ahl plj = ahk Akibatnya, AP = P A jika dan hanya jika vi dan vj bertetangga ketika vh dan vk bertetangga; yaitu, jika dan hanya jika π adalah suatu automorfisma dari G. Konsekuensi dari hasil ini adalah bahwa automorfisma menghasilkan kelipatan dari vektor eigen yang terkait dengan nilai eigen yang diberikan. Tepatnya, misal x adalah vektor eigen dari A yang terkait dengan nilai eigen λ. Maka kita mempunyai AP x = P Ax = P λx = λP x ini berarti bahwa P x juga adalah vektor eigen dari A yang terkait dengan nilai eigen λ. Jika x dan P x bebas linear kita simpulkan bahwa λ bukan nilai eigen sederhana.Lemma berikut ini memberikan gambaran yang lengkap tentang apa yang terjadi ketika λ sederhana. Lema 9.16. Misal λ adalah nilai eigen sederhana dari G, dan misal x adalah vektor eigen yang terkait dengan λ, dengan komponen-komponen real. Jika matriks permutasi P merepresentasikan suatu automorfisma dari G maka P x = ±x. Bukti. Jika λ mempunyai multiplisitas 1, x dan P x bebas linear; yaitu P x = µx untuk suatu bilangan kompleks µ. Karena x dan P real, µ real, dan karena P n = I untuk



BAB 9. GRAF AUTOMORFISMA



109



suatu bilangan asli s ≥ 1, ini mengikuti bahwa µ adalah suatu akar ke-s dari kesatuan. Akibatnya µ = ±1 dan lemma terbukti. Teorema 9.17. (Mowshowitz 1969, Petetrsdorf dan Sachs 1969) Jika semua nilai eigen dari graf G adalah nilai eigen sederhana,setiap automorfisma dari G (lepas dari identitas) mempunyai order 2. Bukti. Misal setiap nilai eigen dari graf G mempunyai multiplisitas 1. Maka untuk sembarang matriks permutasi P merepresentasikan suatu automorfisma dari graf G, dan sembarang vektor eigen x, kita punya P 2 x = x. Ruang yang direntangkan oleh vektor eigen adalah seluruh ruang dari vektor-vektor kolom, dan juga P 2 = I. Definisi 9.18. Misal G graf dengan automorfisma grup Auth (G) . Graf G adalah simetri jika untuk setiap titik-titik u, v, x, y di G sedemikian sehingga titik u dan v bertetangga, titik x dan y bertetangga, terdapat suatu automorfisma α di Auth(G) dimana α (u) = x dan α (v) = y. Graf G dikatakan transitif-jarak jika,untuk semua titik u, v, x, y di G sedemikian sehingga δ (u, v) = δ (x, y), ada suatu automorfisma αdi Auth(G) yang memenuhi α (u) = x dan α (v) = y.



Sehingga jelas kita mempunyai kondisi Kita sebut bahwa G adalah jarak-transitif jika untuk semua titik u, v, x, y di G sedemikian sehingga δ (u, v) = δ (x, y), ada suatu automorfisma αdi Auth(G) yang memenuhi α (u) = x dan α (v) = y. Ini jelas bahwa kita mempunyai suatu kondisi hirarki:



transitif-jarak ⇒ Simetri ⇒ transitif-titik



Bab 10



Vertex-transitive Graphs Pada bab ini, kita akan mempelajari tentang graf Γ dimana grup automorfismanya beraksi transitif pada V Γ. Sebelum kita melangkah pada pembahasan dalam bab ini, ingat kembali beberapa definisi berikut. Misalkan S himpunan tak kosong. Permutasi ϕ pada S adalah pemetaan dari S ke S yang bersifat satu-satu dan pada. Himpunan semua permutasi pada S membentuk grup terhadap operasi komposisi dan kita namakan grup simetri pada S. Kita notasikan grup ini dengan Sim(S). Jika |S| = n, kita gunakan notasi Sn untuk Sim(S). Sebagai contoh, misalkan S = {1, 2, 3, 4} maka pemetaan τ yang memetakan 1 ke 2, 2 ke 4, 3 ke 1, dan 4 ke 3 adalah suatu permutasi pada S. Pemetaan τ ini juga dapat kita representasikan sebagai suatu matriks dengan dua baris. Pada baris pertama kita tuliskan 1, 2, 3, 4 dan pada baris kedua kita tuliskan τ (1), τ (2), τ (3), τ (4) sehingga τ dapat dituliskan seperti berikut.   1 2 3 4  . 2 4 1 3 Suatu automorfisma dari graf sederhana Γ adalah suatu permutasi π pada V Γ yang memenuhi untuk setiap u, v ∈ V Γ, {u, v} adalah sisi di Γ jika dan hanya jika {π(u), π(v)} adalah sisi di Γ. Himpunan semua operasi komposisi membentuk grup dan kita namakan grup automorfisma dari Γ dan ditulis Aut(Γ). Sebagai contoh, kita ambil graf K3 dan misalkan V K3 = {v1 , v2 , v3 }. Definisikan permutasi π pada K3 oleh π(v1 ) = v3 , π(v2 ) = v1 , dan π(v3 ) = v2 maka jelas bahwa π adalah suatu automorfisma pada K3 . Misalkan G suatu grup dan Ω adalah himpunan tak kosong. Asumsikan untuk setiap g ∈ G dan α ∈ Ω terdapat secara tunggal g · α ∈ Ω. Grup G dikatakan beraksi pada Ω 110



BAB 10. VERTEX-TRANSITIVE GRAPHS



111



jika memenuhi sifat berikut. 1. 1 · α = α untuk semua α ∈ Ω 2. g · (h · α) = (gh) · α untuk semua α ∈ Ω dan g, h ∈ G. Dalam hal ini, · adalah aksi dari G pada Ω. Jika G beraksi pada Ω, himpunan yang berbentuk {g · α|g ∈ G} kita namakan orbit dari Ω. Misalkan Γ adalah suatu graf, kita dapat mendefinisikan aksi ∗ dari Aut(Γ) pada V Γ melalui π ∗ u = π(u), untuk setiap π ∈ Aut(Γ) dan u ∈ V Γ. Aksi dari G pada Ω dikatakan transitif jika setiap dua unsur α, β ∈ Ω terdapat g ∈ G sehingga g · α = β. Ini berarti, hanya ada satu orbit pada aksi yang transitif. Graf Γ dikatakan vertex-transitive jika aksi ∗ dari Aut(Γ) pada V Γ bersifat transitif. Sebagaimana telah kita bahas pada bab sebelumnya, sifat vertex-transitivity mengakibatkan setiap titik mempunyai derajat yang sama, sehingga Γ adalah graf reguler. Berikut ini diberikan beberapa hasil standar pada grup-grup permutasi transitif yang akan kita gunakan. Misal G = Aut(Γ) dan Gv menotasikan subgrup stabilizer untuk titik v, yaitu subgrup dari G yang memuat automorfisma dengan titik tetap v. Dalam kasus vertex-transitive, semua subgrup stabilizer Gv (v ∈ V Γ) adalah conjugate pada G, dan akibatnya isomorphic. Indeks dari Gv pada G diberikan oleh persamaan berikut |G : Gv | = |G| / |Gv | = |V Γ| . Jika setiap stabilizer Gv adalah grup identitas, maka setiap elemen dari G (kecuali identitasnya) tidak memasangkan setiap titik ke dirinya sendiri, dan kita katakan bahwa G beraksi reguler pada V Γ. Dalam kasus ini, order dari G sama dengan jumlah titiknya. Terdapat suatu konstruksi standar, diberikan oleh Cayley (1878), yang memungkinkan kita untuk mengkonstruksi beberapa vertex-transitive graphs. Kita akan memberikan suatu versi singkat yang telah dibuktikan menjadi sangat sesuai untuk kebutuhan dalam teori graf aljabar. Misalkan G suatu grup berhingga abstrak dengan identitas 1 dan andaikan Ω adalah himpunan pembangun untuk G yang memenuhi sifat: (i) x ∈ Ω ⇒ x−1 ∈ Ω dan (ii) 1 ∈ / Ω. Definisi 10.1. Graf Cayley Γ = Γ(G, Ω) adalah graf sederhana dengan himpunan titik V Γ = G dan himpunan sisi EΓ = {{g, h}|g −1 h ∈ Ω}.



BAB 10. VERTEX-TRANSITIVE GRAPHS



112



Verifikasi sederhana menunjukkan bahwa EΓ terdefinisi dengan baik dan Γ(G, Ω) adalah suatu graf terhubung. Sebagai contoh, jika G adalah grup simetris S3 dan Ω = {(12), (23), (13)}, maka graf Cayley Γ(G, Ω) isomorphic dengan K3,3 (Gambar 16.1).



Gambar 10.1: K3,3 sebagai graph Cayley untuk S3



Proposisi 10.2. (1) Graf Cayley Γ(G, Ω) merupakan vertex-transitive. (2) Andaikan π adalah suatu automorfisma dari grup G sehingga π(Ω) = Ω, maka π adalah suatu automorfisma graf dengan titik tetap 1. Dalam hal ini, π dipandang sebagai suatu permutasi dari titik-titik Γ(G, Ω). Bukti. (1) Untuk setiap g di G, definisikan suatu permutasi g dari V Γ = G dengan aturan g(h) = gh (h ∈ G). Permutasi ini adalah automorfisma dari Γ. Untuk {h, k} ∈ EΓ berlaku h−1 k ∈ Ω ⇒ (gh)−1 gk ∈ Ω ⇒ {g(h), g(k)} ∈ EΓ. Himpunan dari semua g (g ∈ G) merupakan suatu grup G (isomorphik dengan G) dengan suatu subgrup dari grup lengkap dari automorfisma-automorfisma Γ(G, Ω) dan beraksi transitif pada titik. (2) Karena π adalah suatu grup automorfisma, π harus memasangkan 1 ke 1. Lebih jauh, π adalah suatu graf automorfisma karena untuk setiap {h, k} ∈ EΓ berlaku h−1 k ∈ Ω ⇒ π(h−1 k) ∈ Ω ⇒ π(h)−1 π(k) ∈ Ω ⇒ (π(h), π(k)} ∈ EΓ. Bagian kedua dari proposisi ini mengakibatkan grup automorfisma dari graf Cayley Γ(G, Ω) sering lebih besar daripada G. Pada contoh yang diilustrasikan di Gambar 16.1, setiap grup automorfisma dari S3 memasangkan Ω satu sama lain dan hal ini menyebabkan stabilizer dari titik 1 mempunyai order paling sedikit 6. Faktanya, order dari stabilizer tersebut adalah 12, dan |Aut(K3,3 )| = 72.



BAB 10. VERTEX-TRANSITIVE GRAPHS Tidak setiap graf dengan titik-transitif adalah graf Cayley.



113 Sebagai contoh, graf



Petersen O3 bukan merupakan graf Cayley karens tidak mungkin hanya terdapat dua grup berorder 10 yang mempunyai beberapa himpunan pembangun berukuran tiga yang memenuhi kondisi pada Definisi 16.1. Dengan memeriksa semua kemungkinan, dapat dibuktikan bahwa graf Petersen tidak membentuk graf Cayley. Kita mulai pembahasan ini dengan mempelajari hirarki dari konsisi simetri saat Aut(Γ) beraksi reguler pada V (Γ). Lema 10.3. Misalkan Γ suatu graf terhubung. Subgraf H dari Aut(Γ) beraksi reguler pada titik jika dan hanya jika Γ isomorphic dengan suatu graf Cayley Γ(H, Ω), untuk beberapa himpunan Ω dengan pembangun H. Bukti. Andaikan V Γ = {v1 , v2 , ..., vn } dan H adalah subgrup dari Aut(Γ) yang beraksi reguler pada V Γ. Akibatnya, untuk 1 ≤ i ≤ n, terdapat hi ∈ H yang unik sehingga hi (vi ) = vi . Misalkan Ω = {hi ∈ H|vi bertetangga ke v1 di Γ}. Dapat ditunjukkan bahwa Ω memenuhi dua kondisi pada Definisi 16.1 dan bijeksi vi ↔ hi adalah isomorphism dari Γ ke Γ(H, Ω). Sebaliknya, jika Γ = Γ(H, Ω), maka grup H yang didefinisikan pada bukti dari Proposisi 16.2 beraksi reguler pada V Γ dan H ≈ H Lema 16.3 menunjukkan bahwa jika Aut(Γ) beraksi regular pada V Γ, maka Γ adalah graph Cayley Γ(Aut(Γ), Ω). Definisi 10.4. G grup abstrak berhingga memuat Graphical Regular Representation (GRR) jika terdapat graph Γ sehingga G isomorphic dengan Aut(Γ) dan Aut(Γ) beraksi regular pada V Γ. Pertanyaan mengenai grup-grup abstrak yang memuat GRR terjawab pada akhir tahun 1970. Hal ini menyebabkan pernyataan pada bagian kedua dari Proposisi 16.2 merupakan satu-satunya hal utama yang menyangkal keberadaan GRR untuk G. Dengan perkataan lain, grup G tidak mempunyai GRR jika dan hanya jika setiap himpunan pembangun Ω untuk G memenuhi (i) dan (ii) sehingga ada suatu automofisma dari G yang memasangkan Ω satu sama lain. Sebagai contoh, grup S3 tidak memuat GRR. Jika terdapat graf Γ yang sesuai, maka graf tersebut pastilah suatu graf Cayley Γ(S3 , Ω). Sekarang dengan mudah dapat diperiksa



BAB 10. VERTEX-TRANSITIVE GRAPHS



114



bahwa untuk setiap himpunan pembangun Ω yang memenuhi (i) dan (ii), terdapat beberapa automorfisma S3 yang memasangkan Ω satu sama lain. Dengan demikian, berdasarkan bagian (2) Proposisi 16.2, grup automorfisma dari suatu graf Cayley Γ(S3 , Ω) lebih besar dari S3 . Pada kasus grup abelian transitif, informasi yang tepat disajikan oleh proposisi berikut. Proposisi 10.5. Misalkan Γ vertex-transitive graph yang grup automorfismanya G = Aut(Γ) merupakan grup abelian. Maka G beraksi reguler pada V Γ dan G adalah grup abelian berorde 2. Bukti. Ambil sebarang g, h ∈ G dengan g(v) = v (v titik tetap pada g), maka gh(v) = hg(v) = h(v) (h(v) juga titik tetap pada g). Jika G transitif, setiap v ∈ V Γ berbentuk h(v) untuk beberapa h ∈ G, sehingga g memasangkan semua titik ke dirinya sendiri, yaitu g(vi ) = vi untuk setiap vi ∈ V Γ. Jadi g = 1. Karena g = 1, maka G beraksi reguler pada V Γ. Karena G beraksi reguler pada V Γ, maka dari Lema 16.3, Γ adalah graph Cayley Γ(G, Ω). Karena G abelian, fungsi φ : g → g −1 adalah suatu automorfisma dari G dan memasangkan Ω satu sama lain. Jika automorfisma ini tidak trivial, maka berdasarkan bagian (2) Proposisi 16.2, G tidak reguler. Dengan demikian, g = g −1 untuk setiap g ∈ G. Karena g 2 = g × g = g × g −1 = 1, setiap g ∈ G berorde 2. Diskusi selanjutnya membahas sifat-sifat spektral dari vertex-transitif graph. Suatu vertex-transitif graph Γ adalah graph reguler maka spektrumnya mempunyai sifat-sifat yang dinyatakan pada Proposisi 3.1. Secara khusus, jika Γ adalah graf terhubung dan reguler dengan derajat k, maka k adalah nilai eigen dari Γ. Dengan demikian, kita dapat menggunakan sifat vertex-transitif untuk mengkarakterisasi nilai eigen dari Γ. Proposisi 10.6. (Petersdorf and Sachs 1969) Misalkan Γ adalah vertex-transitif graph yang berderajat k dan λ adalah nilai eigen dari Γ. Jika |V Γ| ganjil, maka λ = k. Jika |V Γ| genap, maka λ = 2α − k untuk suatu 0 ≤ α ≤ k Bukti. Misalkan x adalah vektor eigen real yang bersesuaian dengan nilai eigen Λ dan P adalah matriks permutasi yang memrepresentasikan suatu automorfisma π dari Γ. Jika π(vi ) = vj , maka berdasarkan Lema 15.3, xi = (Px)j = ±xj . Karena Γ adalah vertextransitive graph, setiap unsur di x mempunyai nilai mutlak yang sama. Selanjutnya, perhatikan bahwa u = [1, 1, ..., 1]t adalah vektor eigen yang bersesuaian dengan nilai eigen



BAB 10. VERTEX-TRANSITIVE GRAPHS k. Akibatnya, jika k 6= λ, maka ut x = 0, yaitu



115 P



xi = 0. Hal ini tidak mungkin. Jadi



haruslah k = λ. Jika Γ mempunyai titik yang banyaknya genap, pilih sebarang vi ∈ V Γ dan misalkan vi bertetangga dengan vj . Akibatnya, untuk setiap α dengan (0 ≤ α ≤ k), xi = xj dan P0 P0 untuk setiap k − α, xj = −xi . Karena (Ax)i = λxi , xj = λxi (dengan xj meliputi seluruh vertex yang bertetangga dengan vi ). Akibatnya, αxi − (k − α)xi = λxi dan λ = 2α − k. Sebagai contoh, bilangan yang mungkin menjadi nilai eigen dari vertex-transitive graph Γ yang 3-reguler hanyalah 3, 1, -1, dan -3. Hal ini dapat dijelaskan sebagai berikut. Jika kita ambil α = 0, maka λ1 = 2α − k = 2.0 − 3 = −3. Jika α = 1, maka λ2 = −1. Jika α = 2, maka λ3 = 1. Proposisi berikut memberikan informasi mengenai nilai eigen dari Γ yang simetris. Proposisi 10.7. Misalkan Γ adalah graf simetris berderajat k dan λ adalah nilai eigen dari Γ. Maka λ = ±k. Bukti. Misalkan vj dan vl adalah titik-titik yang bertetangga dengan vi .



Karena Γ



simetris, terdapat automorfisma π dari Γ sehingga π(vi ) = vi dan π(vj ) = vl . Jika P adalah matriks permutasi yang memrepresentasikan π dan π(vi ) = vi , maka Px=x sehingga xj = xl . Akibatnya, α = 0 atau α = k. Dari Proposisi 16.3 diperoleh bahwa λ = ±k. Kita simpulkan bahwa nilai eigen −k ada jika dan hanya jika Γ adalah graf bipartit.



Bab 11



Graf Simetris Pada bab sebelumya telah dipelajari mengenai vertex-transitivity.Dari sifat-sifat yang dimiliki vertex-transitivity bahwa kita dapat mengkonstruksi paling sedikit satu graf vertextransitive dari setiap grup hingga(konstruksi graf Cayley), graf vertex-transitivity simetris jika dan hanya jika setiap vertex-stabilizer Gv transitif pada himpunan titik yang bertetangga dengan v. Namun kondisi vertex-transitivity tersebut tidak terlalu kuat untuk menyatakan graf simetris. Maka akan kita bahas lebih lanjut properti untuk graf simetri.



Kita akan mulai dengan mendefinisikan t-arc [a] pada graf Γ. Definisi 11.1. Misalkan Γ graf. t-arcs [a] adalah barisan titik (a0 , a2 , ..., at ) di Γ dengan {ai−1 , ai } ∈ EΓ, 1 ≤ i ≤ t dan ai−1 6= ai+1 , 1 ≤ i ≤ t − 1. Contoh yang paling mudah dari arc adalah lintasan, akan tetapi, perlu diperhatikan bahwa arc ini memperbolehkan kita melakukan pengulangan titik di dalamnya. Definisi 11.2. Graf Γ disebut t-transitif (t ≥ 1) jika grup otomorfismanya transitif pada himpunan t-arcs di Γ tapi tidak transitif pada himpunan (t + 1)-arcs di Γ. Proposisi 11.3. Misalkan Γ graf t-transitif dengan derajat paling sedikit 3 dan dengan girth g, maka t ≤ 1/2(g + 2). Bukti. Γ memuat siklus dengan panjang g, dimana siklus tersebut sebuah g-arcs. Karena derajat paling sedikit 3, maka kita bisa mengganti satu sisi pada g-arc dengan sisi lain sehingga ujung g-arc yang pertama tidak sama dengan g-arc yang kedua. Karena g-arc 116



BAB 11. GRAF SIMETRIS



117



yang kedua bukan lagi siklus, maka tidak ada otomorfisma diantara keduanya, sehingga t < g. Akibatnya, jika memilih siklus dengan panjang g di Γ , maka terdapat t-arc [a] dengan tidak ada titik yang sama yang termuat di siklus tersebut. Misalkan [b] adalah (g − t)arc yang berawal di at dan berakhir di a0 . Misalkan v titik yang bertetangga dengan a(t−1) tetapi tidak dengan a(t−2) dan a(t) . Karena Γ adalah t-transitif, maka terdapat otomorfisma dari t-arc [a] ke t-arc (a0 , a1 , ..., at−1 , v) yang memetakan (g − t + 1)-arc [at−1 .b] ke (g − t + 1)-arc [at−1 .c] dengan c0 = v dan cg−t = a0 . Arc [at−1 .b] dan [at−1 .c] mungkin saling bertumpuk di beberapa sisi, tapi keduanya memberikan siklus dengan panjang kurang atau sama dengan 2(g − t + 1). Karena g ≤ 2(g − t + 1), jadi diperoleh g ≥ 2t − 2. Proposisi di atas diperlukan karena pada bagian berikutnya dari bab ini, yang dimaksud dengan graf adalah graf regular terhubung dengan derajat paling sedikit 3. Kita meninjau hanya untuk graf regular terhubung berderajat tidak kurang dari 3 karena satusatunya graf regular terhubung berderajat 1 adalah K2 , yang merupakan graf 1-transitif. Sedangkan untuk graf regular berderajat 2, satu-satunya yang memenuhi adalah Cn yang merupakan graf t-transitif, t ≥ 1. Definisi 11.4. Misalkan [a], [b] sebarang s-arc di graf Γ. [b] disebut suksesor dari [a] jika bi = ai+1 , (0 ≤ i ≤ s − 1). Perhatikan bahwa definisi di atas dapat dipandang sebagai penggeseran t-arc. Lema di bawah memberikan suatu jaminan bahwa diantara dua t-arc, kita bisa membuat suatu barisan suksesor yang menghubungkan kedua t-arc tersebut. Lema 11.5. Misalkan Γ graf terhubung dengan derajat paling sedikit 3. Jika s ≥ 1 dan [a], [b] sebarang s-arc di Γ maka terdapat barisan hingga [a(i) ] (1 ≤ i ≤ l) s-arc di Γ dengan [a1 ] = [a] dan [al ] = [b] dan [ai+1 ] suksesor dari [ai ], 1 ≤ i ≤ l − 1. Kita tidak membuktikan lema ini karena terlalu panjang dan di luar konteks bab ini untuk dibahas, bukti lengkapnya bisa dilihat pada Connectivity in Graphs karangan Tutte tahun 1966. Berikutnya, misalkan kita mempunyai sebuah t-arc [a], dengan titik yang bertetangga dengan at adalah at−1 , v (1) , v (2) , ..., v (l) . Akibatnya, kita bisa memperoleh suksesor dari



BAB 11. GRAF SIMETRIS



118



[a] yaitu [b(i) ] = (a1 , a2 , ..., at , v (i) ). Untuk kasus seperti ini, kita mempunyai teorema berikut: Teorema 11.6. Misalkan Γ graf k-regular dan terhubung dengan l = k − 1 ≥ 3, dan [a] tarc di Γ. Aut(Γ) transitif di t-arc [a] jika dan hanya jika Aut(Γ) memuat automorfisma g1 , g2 , ..., gl yang memenuhi gi [a] = [b(i) ] (1 ≤ i ≤ l). Bukti. Jika Aut(Γ) transitif di t-arc, kita bisa memilih otomorfisma g1 , g2 , ..., gl yang akan memetakan [a] ke suatu t-arc yang lain. Akibatnya, untuk 1 ≤ i ≤ l kita bisa memilih [b(i) ] sehingga gi [a] = [b(i) ]. Selanjutnya misalkan Aut(Γ) memuat automorfisma g1 , g2 , ..., gl yang memenuhi gi [a] = [b(i) ] (1 ≤ i ≤ l). Misalkan H = hg1 , g2 , ..., gl i. Kita akan tunjukkan H transitif di t-arc. Misalkan [c] sebuah t-arc anggota orbit [a] dengan aksi grup H, maka [c] = h[a] untuk suatu h ∈ H.Misalkan [d] sebarang suksesor dari[c], maka h−1 [d] juga merupakan suksesor dari [a]. Akibatnya, kita peroleh [d] = hgi [a], untuk suatu i. Lema sebelumnya memberikan kita jaminan bahwa setiap t-arc dapat diperoleh dari [a] dengan mengambil suksesornya secara berturut-turut. Kita peroleh setiap t-arc anggota orbit dari [a] dengan aksi grup H.



Gambar 11.1: Graf Petersen Contoh 11.7. Misalkan graf Petersen (atau O3 ) di atas dengan himpunan titiknya adalah pasangan tak terurut dari {1, 2, 3, 4, 5} dengan pasangan yang saling lepas bertetangga.



BAB 11. GRAF SIMETRIS



119



Permutasi pada himpunan {1, 2, 3, 4, 5} memberikan kita juga otomorfisma pada graf tersebut, karena permutasi merupakan pemetaan satu-satu pada. Karena girth dari O3 adalah 5, proposisi pertama dari bab ini memberikan kita batasan t ≤ 3. Karena 3-arc [a] = (12, 34, 15, 23) mempunyai 2 suksesor yaitu [b] = (34, 15, 23, 14), [c] = (34, 15, 23, 45) dan permutasi (13)(245) memetakan [a] ke [b], (13524) memetakan [a] ke [c], maka O3 merupakan graf 3-transitif. Definisi 11.8. Barisan stabiliser dari [a] adalah barisan Aut(Γ) = G > Ft > ... > F1 > F0 subgrup dari Aut(Γ) dengan Fi (0 ≤ i ≤ t) adalah stabiliser titik demi titik dari {a0 , a1 , ..., at−1 }. Untuk graf yang sama dengan contoh sebelumnya, kita perhatikan 3-arc (12, 34, 15, 23). Kita peroleh F0 = 1, F1 = h(34)i, F2 = h(34), (12)i, F3 = h(34), (12), (345)i.



Untuk menghitung orde dari subgrup stabiliser seperti pada definisi di atas, kita dapat menyatakannya dalam orde dari F0 . Berikut cara penghitungannya. Karena Ft adalah stabiliser dari satu titik a0 pada G grup transitif-titik maka |G : Ft | = n = |V Γ|. Karena G transisitf pada 1-arc dan Ft transitif pada k titik yang bertetangga dengan a0 dan Ft−1 stabiliser titik a1 , maka |Ft : Ft−1 | = k. Untuk 2 ≤ s ≤ t, G s-transitif, akibatnya Ft−s+1 transitif pada k − 1 titik yang bertetangga dengan as−1 selain as−2 dan Ft−s stabiliser dari as , jadi |Ft−s+1 : Ft−s | = k − 1 untuk 2 ≤ s ≤ t. Kita peroleh |Fs | = (k − 1)s |F0 | (0 ≤ s ≤ t − 1), |Ft | = k(k − 1)t−1 |F0 | dan |G| = nk(k − 1)t−1 |F0 | seperti yang terlihat pada contoh graf Petersen di atas. Proposisi 11.9. Misalkan Γ graf dan Aut(Γ) grup otomorfismanya. Misalkan barisan {1} ⊆ Y1 ⊆ Y2 ⊆ ..., dengan Yi = {ga−j gbj |a, b ∈ {1, 2, ..., l}dan1 ≤ j ≤ i}. Kondisi di bawah terpenuhi: 1. Jika 1 ≤ i ≤ t, maka Yi ⊆ Fi , Yi bukan subhimpunan dari Fi−1 2. Jika 0 ≤ i ≤ t, maka Fi subgrup dari G yang dibangun oeh Yi dan F0 . Bukti.



1. Untuk 1 ≤ a ≤ l, gar (αj ) = αj+r jika j, j + r diantara 0 dan t. Karena



gat−j+1 (αj ) = v (a) maka ga−j gbj memetakan α1 , α2 , ..., αt−1 ke dirinya sendiri untuk



BAB 11. GRAF SIMETRIS



120



j ≤ i. Kita peroleh Yi ⊆ Fi . Misalkan Yi ⊆ Fi−1 , maka ga−i gbi memetakan αt−i+1 ke dirinya sendiri sehingga gai (αt−i+1 ) = gbi (αt−i+1 ) yang bertentangan untuk a 6= b. Haruslah Yi bukan subhimpunan dari Fi−1 . 2. Karena Yi dan F0 termuat di Fi maka hYi , F0 i ⊆ Fi . Selanjutnya misalkan f ∈ Fi dan f [α] = (α0 , α1 , ..., αt−1 , γ1 , ..., γi ). Ambil sebarang gb . Karena γ1 bertetangga dengan αt−i ,gbi (γ1 ) bertetangga dengan gbi (αt − i) maka gb−i (γ1 ) = v(a), ∃a. Kita dapat memisalkan ga−i gbi f [α] = (α0 , α1 , ..., αt−i+1 , δ2 , ..., δi ). Dengan melakukan langkah yang sama tetapi mengganti i dengan i − 1 kita bisa −(i−1) i−1 gd



memperoleh gc



yang merupakan anggota Yi dan Yi−1 dan memetakan δ2



ke αt−i+2 tetapi memetakan α0 , α1 , ..., αt−i+1 ke dirinya sendiri. Dengan melakukan langkah yang sama kita peroleh g ∈ Yi dengan gf [α] = [α], sehingga gf ∈ F0 . Jadi, f ∈ hYi , F0 i. Jadi Fi ⊆ hYi , F0 i.



Setiap anggota dari Y0 , Y1 , ..., Yt memetakan α0 ke dirinya sendiri yang mengakibatkan Y0 , Y1 , ..., Yt ⊆ Ft . Sedangkan Yt+1 memuat otomorfisma yang bukan stabiliser dari α0 . Proposisi di bawah memberikan jaminan kepada kita bahwa F0 dan Yt+1 membangun G tetapi tidak untuk Γ graf bipartit. Hal tersebut terjadi karena jika Γ graf bipartit simetris dengan V1 dan V2 adalah partisi-warna dari V Γ maka otomorfisma yang merupakan stabiliser dari tepat salah satu V1 atau V2 membentuk subgrup dari Aut(Γ) yang berindeks 2. Subgrup terbeut dikatakan mengawetkan bipartisi. Proposisi 11.10. Misalkan Γ t-transitif dengan t ≥ 2 dan girth lebih besar dari 3. Misalkan G∗ adalah subgrup dari G = Aut(Γ) yang dibangun oleh Yt+1 dan F0 . 2 diantara kondisi di bawah ini berlaku: 1. G∗ = G 2. Γ bipartit, |G : G∗ | = 2 dan G∗ subgrup dari G yang mengawetkan bipartisi.



BAB 11. GRAF SIMETRIS



121



Bukti. Karena jelas bahwa G∗ ⊆ G, cukup dibuktikan bahwa |G∗ | = |G|. Ambil u sebarang titik di Γ dengan ∂(u, α0 ) = 2. Akan dibuktikan terdapat g ∗ ∈ G∗ sehingga g ∗ (α0 ) = u. Karena girth Γ lebih besar dari 3, maka v (a) = gat+1 (α0 ), v (b) = −(t+1) t+1 gb (α0 ))



gbt+1 (α0 ) memenuhi ∂(v (a) , v (b) ) = 2. Jadi, ∂(α0 , ga



= 2. Karena Ft =



hYt i ⊆ Yt+1 ⊆ G∗ dan Ft transitif di 2-arc yang berawal dari α0 (dari definisi), kita per−(t+1) t+1 gb (α0 )



oleh f ∈ G∗ sehingga f (α0 ) = α0 dan ga



−(t+1) t+1 gb f (α0 )



= u. Jadi ga



= α0 .



Misalkan U orbit dari α0 dengan aksi oleh G∗ . U memuat semua titik yang berjarak 2 dari α0 . Sehingga U memuat titik yang berjarak genap dari α0 . Jika U = V Γ, G∗ transitif di V Γ yang mengakibatkan stabilizer dari α0 adalah Ft (Ft ⊆ G∗ ). Kita peroleh |G∗ | = |V Γ|.|Ft | = |G|. Jadi G∗ = G.



Misalkan U 6= V Γ, maka U hanya memuat titik-titik yang berjarak genap dari α0 . Akibatnya, Γ bipartit dengan partisi U dan V Γ\U .



Daftar Pustaka [1] Bill Jacob, 1990 Linear Algebra, W.H. Freeman and Company, New York. [2] Fuzhen Zhang, 1999, Matrix Theory, Springer, New York. [3] Roger A. Horn dan Charles A. Johnson, 1985 Matrix Analysis, Cambridge University Press, New York. [4] Thomas W. Hungerford, 1974, Algebra, Graduate Texts in Mathematics, Springer, New york. [5] I. Martin Isaacs, 1993 Algebra, A Graduate Course, Brooks/Cole Publishing Company, California. [6] Reinhard Diestel, 2000 Graph Theory 2ed , Graduate Texts in Mathematics, Springer, New York. [7] J. A. Bondy dan U. S. R. Murty, 1976, Graph Theory With Applications, The Macmillan Press Ltd., Great Britain. [8] Norman Biggs, 1993, Algebraic Graph Theory 2ed , Cambridge University Press, Cambridge.



122