POLINOMIAL KARAKTERISTIK BEBERAPA KELAS GRAF BERARAH

POLINOMIAL KARAKTERISTIK BEBERAPA KELAS GRAF BERARAH Nuri Wardani1, I Ketut Budayasa2 Jurusan Matematika, Matematika dan Ilmu Pengetahuan Alam, Universitas Negeri Surabaya, 60931 2 Jurusan Matematika, Matematika dan Ilmu Pengetahuan Alam, Universitas Negeri Surabaya, 60931 email :[email protected], [email protected] 1

ABSTRAK Persamaan figuratif adalah metode untuk mengkontruksi polynomial karakteristik graf berarah 𝐷 dengan 𝑛 titik (𝑋 𝐷 ) tanpa menggunakan matrik berhubungan langsung. Pada skripsi ini akan dipelajari bagaimana persamaan figuratif digunakan dalam mengkaji formula untuk menghitung setiap koefisien 𝑡𝑖 dengan 1 ≤ 𝑖 ≤ 𝑛 dari suatu𝑋 𝐷 = 𝑥 𝑛 + 𝑡1 𝑥 𝑛−1 + 𝑡2 𝑥 𝑛−2 + ⋯ + 𝑡𝑛−1 𝑥 + 𝑡𝑛 . Graf linier, graf siklik dan graf tangga adalah tiga graf komplek yang akan dikaji polinomial karakteristiknya. Akan dibuktikan bahwa setiap koefisien 𝑡𝑖 untuk 𝑖 ganjil pada graf linier dengan 𝑛 titik adalah sama dengan nol, dan 𝑖

𝑡𝑖 = (−1)2

𝑖 2

𝑛− 𝑖 2

untuk 𝑖 genap. Pada graf siklik

dengan 𝑛 titik juga akan dibuktikan bahwa koefisien 𝑡𝑖 = 0 jika 𝑖 ganjil dan 𝑖 < 𝑛, sedangkan koefisien 𝑡𝑖 untuk 𝑖 genap dan 𝑖 < 𝑛 adalah (−1)

𝑖 2

𝑖

𝑛 𝑖 2

𝑛−

𝑛−2 𝑖

. Koefisien ganjil pada graf

2

tangga dengan 𝑛 titik adalah nol sedangkan untuk setiap 𝑙𝑖 dengan 𝑖genap, 𝑙𝑖 = (−1)

𝑖 2

𝑖

𝑛+1−2 𝑖

.

2

Kata kunci : graf linier, graf siklik, graftangga, polinomialkarakteristik, persamaanfiguratif

matrik berhubungan langsung (adjacency matrix) yang merupakan matrik persegi berordo 𝑛𝑥𝑛. Polinomial karakteristik adalah suatu persamaan polinom (suku banyak) yang didapat dari suatu matrik persegi dengan mencari nilai eigen dari matrik tersebut. Jika diberikan suatu matrik persegi berordo 𝑛𝑥𝑛 dapat dikontruksi polinomial karakteristiknya dengan pangkat tertinggi 𝑛. Polinomial karakteristik dari suatu graf berarah dengan jumlah tititk berhingga dapat dikontruksi dengan mencari nilai eigen matrik berhubungan langsungnya. Persamaanfiguratif (FigureEquation) adalah metode yang dapat digunakan untuk mengkontruksi polinomial karakteristik suatu graf tanpa menggunakan matrik berhubungan langsung (adjacency matrix) tetapi dengan menghitung setiap koefisien dari polinomial karakteristik secara umum. Polinomial karakteristik dari sebarang graf berarah D dengan 𝑛 titik adalah 𝑋 𝐷 = 𝑥 𝑛 + 𝑐1 𝑥 𝑛−1 + 𝑐2 𝑥 𝑛−2 + ⋯ + 𝑐𝑛−1 𝑥 + 𝑐𝑛 , setiap koefisien 𝑐𝑖 untuk 1 ≤ 𝑖 ≤ 𝑛 dapat dihitung dengan memeriksa ℒ 𝑖 yaitu himpunan subgraf berarah dengan panjang 𝑖. Untuk beberapa kelas graf berarah yang lebih komplek dan memiliki banyak titik, kontruksi polinomial karakteristik dengan menggunakan definisi persamaan figuratif cukup sulit dilakukan. Oleh karena itu dapat diturunkan suatu formula untuk menghitung koefisien dari beberapa kelas graf berarah dengan menggunakan dasar definisi persamaan figuratif.

PENDAHULUAN Graf berarah (digraph) adalah salah satu kajian dalam teori graf yang merupakan pasangan berurutan dari dua himpunan V(D) yaitu himpunan berhingga tak kosong yang anggota-anggotanya disebut titik dan𝜏 𝐷 yaitu himpunan berhingga (boleh kosong) yang anggota-anggotanya disebut busur,sedemikianhinggasetiapbusurmerupakanpasa nganberurutandariduatitik di 𝑉 𝐷 . Setiap graf berarah dengan jumlah titik berhingga dapat direpresentasikan dalam bentuk gambar (diagram) dan dalam bentuk matrik, salah satunya adalah

KAJIAN TEORI 2.1

Graf

Definisi 2.1 Sebuah graf G berisikan dua himpunan yaitu himpunan berhingga tak kosong V(G) dari obyek-obyek yang disebut titik dan himpunan berhingga (mungkin kosong) E(G) yang elemenelemennyadisebut sisi sedemikian hingga setiap elemen e dalam E(G) merupakan pasangan tak berurutan dari titik-titik di V(G). HimpunanV(G)

© 2009 ICTS

disebut himpunan titik G dan himpunan E(G) disebut himpunan sisi G. Definisi 2.2 Graf berarah D adalah suatu pasangan berurutan dari dua himpunan V(D) yaitu himpunan berhingga tak kosong yang anggota-anggotanya disebut titik dan 𝜏 𝐷 yaitu himpunan berhingga (boleh kosong) yang anggota-anggotanya disebut busur sedemikian hingga setiap busur merupakan pasangan berurutan dari dua titik di V(D). Jika 𝑣1 dan 𝑣2 adalah dua titik pada graf berarah D dan 𝑒 = (𝑣1 , 𝑣2 )sebuah busur D, maka e disebut busurkeluar (outdegree) darititik𝑣1 dan e disebut busur – menuju (indegree) titik𝑣2 . Definisi 2.3 Matrik berhubungan langsung dari sebuah graf berarah D adalah A(D) yaitu sebuah matrik bilangan bulat berordo 𝑛𝑥𝑛 dimana banyaknya baris dan kolom sama dengan banyaknya titik dari graf berarah D, matrik e-𝑢𝑣 sama dengan 1 jika terdapat busur dari titik 𝑢 ke 𝑣 dan 0 jika tidak terdapat busur dari titik 𝑢 ke 𝑣. Definisi 2.4 Sebuah graf H dikatakan sub graf berarah dari graf berarah D dinotasikan dengan𝐻 ⊆ 𝐷 jika 𝑉(𝐻) ⊆ 𝑉 𝐷 dan 𝜏 𝐻 ⊆ 𝜏 𝐷 . Definisi 2.5 Sub graf berarah linier dari suatu graf berarah D adalah suatu graf baru K dengan 𝑉 𝐾 ⊆ 𝑉(𝐺) dan 𝜏 𝐾 ⊆ 𝜏(𝐺) sedemikian hingga setiap titik pada graf berarah K memiliki indegree dan outdegree sama dengan 1. Sub graf berarah linier dengan panjang𝑖 terdiri dari 𝑖 titik dan 𝑖 sisi sedemikian hingga setiap titik memiliki indegree dan outdegree sama dengan 1. 2.2

Grup

Definisi 2.7 Diketahuihimpunantakkosong B denganoperasi *.Himpunan B disebutgrupterhadapoperasi * jikamemenuhiaksioma-aksiomaberikut : Memenuhisifatketertutupan ( ∀ 𝑎, 𝑏 𝜖 𝐵 berlaku 𝑎 ∗ 𝑏 𝜖𝐵) Asosiatif (∀ 𝑎, 𝑏, 𝑐 𝜖 𝐵 berlaku 𝑎 ∗ 𝑏 ∗ 𝑐 = 𝑎 ∗ (𝑏 ∗ 𝑐)) Memuatelemenidentitas (∃𝑒𝜖𝐵 ,∀ 𝑎𝜖𝐵 berlaku 𝑒 ∗ 𝑎 = 𝑎 ∗ 𝑒 = 𝑎) Setiapelemen B Memiliki Invers (∀ 𝑎𝜖𝐵, ∃𝑎−1 𝜖𝐵 sedemikian hingga 𝑎 ∗ 𝑎 −1 = 𝑎 −1 ∗ 𝑎 = 𝑒)

Definisi 2.8 Suatu grup (B,*) disebut grup siklik jika terdapat 𝑏𝜖𝐵 sedemikian hingga untuk setiap 𝑎𝜖𝐵 dapat dinyatakan sebagai 𝑎 = 𝑏𝑛 untuk suatu 𝑛𝜖𝑍. 𝑏 disebut elemen pembangun atau generator dari B dan B merupakan grup siklik yang dibangun oleh 𝑏, dapatdinotasikan𝐵 = 𝑏 , dapat juga dinyatakan sebagai 𝑏 = {𝑏𝑛 |𝑛𝜖𝑍}. Definisi 2.9 Sebuah subset (S,*) darisuatugrup (B,*) disebut himpunan generator (generating set) jika hanya jika setiap elemen di B dapat dinyatakan sebagai hasil operasi elemen-elemen S dan inversnya. 2.3

Graf Cayley

Definisi 2.10 : Missal 𝐵,∗ adalah grup berhingga dan 𝑆 adalah himpunan generator maka graf cayley dari 𝐵,∗ dengan himpunan generator 𝑆 dapat ditulis 𝐶 𝐵, 𝑆 adalah graf sedemikian hingga :  Setiapelemen di 𝐵,∗ merupakan titik di graf cayley 𝐶(𝐵, 𝑆) sehingga order dari grup B (banyaknya elemen B) sama dengan banyaknya titik pada graf cayley 𝐶 𝐵, 𝑆 .  (𝑎, 𝑏)merupakan busur graf cayley jika dan hanya jika 𝑎 ∗ 𝑠 = 𝑏, dari 𝑎 ke 𝑏 untuk 𝑠 ∈ 𝑆. 2.4

PolinomialKarakteristik

Definisi 2.11 Misalkan diketahui sebuah matrik persegi A berordo 𝑛𝑥𝑛, nilai eigen dari matrik A adalah sebuah skalar 𝑥 dimana terdapat matrik tak nol W berordo 𝑛𝑥1 sedemikian hingga 𝐴𝑊 = 𝑥𝑊...(1). Matrik kolom 𝑊 disebut vector eigen yang bersesuaian dengan 𝑥. Nilai eigen juga disebut sebagai nilai asli atau karakteristik. Untuk mendapatkan nilai eigen 𝑥 dari matrik A persamaan (1) dapat dituliskan kembali menjadi : 𝑥𝑊 − 𝐴𝑊 = 0 𝑥−𝐴 𝑊 =0 𝑥𝐼 − 𝐴 𝑊 = 0 𝐼 adalah matrik identitas berordo 𝑛𝑥𝑛. W adalah vektor tak nol, agar 𝑥 menjadi nilai eigen harus terdapat solusi tak nol dari persamaan 𝑥𝐼 − 𝐴 𝑊 = 0.Solusi tak nol diperoleh jika 𝑑𝑒𝑡 𝑥𝐼 − 𝐴 = 0, persamaan tersebut berupa suatu persamaan polinom dengan pangkat tertinggi 𝑛 dan disebut polynomial karakteristik dari matrik A.

2.5

PolinomialKarakteristik Graf Berarah

Definisi 2.12 Suatu graf berarah D dengan 𝑛 titik dapat direpresentasikan ke dalam suatu matrik berhubungan langsung 𝐴(𝐷) yang merupakan matrik persegi berordo 𝑛𝑥𝑛. Berdasarkan Definisi 2.11 nilai eigen 𝑥 dari matrik 𝐴(𝐷) diperoleh dari persamaann karakteristik sebagai berikut : 𝑥𝐼 − 𝐴(𝐷) 𝑊 = 0 𝑊 adalah suatu vektor tak nol, agar 𝑥 menjadi nilai eigen maka : 𝑑𝑒𝑡 𝑥𝐼 − 𝐴(𝐷) = 0 Ruas kiri dari persamaan diatas merupakan polinomial karakteristik berderajat 𝑛 dari suatu graf berarah D dengan 𝑛 titik. Secara umum direpresentasikan sebagai berikut :

Definisi 2.15 Graf tangga(𝑅2𝑛 ) adalah graf berarah dengan himpunan titik {𝑣1 , 𝑣2 , … , 𝑣2𝑛 }, untuk setiap 𝑣𝑖 𝜖 {𝑣1 , 𝑣2 , … , 𝑣𝑛−1 } adalah sumber (source) dari Sebuah busur dengan tujuan 𝑣𝑖+1 , dan untuk setiap 𝑣𝑗 𝜖 {𝑣𝑛+2 , 𝑣𝑛+3 , … , 𝑣2𝑛 } adalah sumber dari sebuah busur dengan tujuan 𝑣𝑗 −1 .

𝑋 𝐷 = 𝑥 𝑛 + 𝑡1 𝑥 𝑛−1 + 𝑡2 𝑥 𝑛−2 + ⋯ + 𝑡𝑛 −1 𝑥 + 𝑡𝑛 2.6

Graf Komplek

Definisi 2.13 Graf linier (𝑇𝑛 ) adalah graf berarah dengan 𝑛 titik sehingga setiap titik 𝑣𝑖 𝜖 adalah sumber (source) dari busur dengan tujuan 𝑣𝑖−1 dan 𝑣𝑖+1 sedangkan 𝑣1 dan 𝑣𝑛 adalah sumber (source) dari sebuah busur secara berturut-turut dengan target 𝑣2 dan 𝑣𝑛−1 .

Definisi 2.14 Graf Siklik adalah graf cayley dari sebuah grup siklik dengan order 𝑛 dan himpunan generator 1, −1 atau dapat ditulis 𝐶(𝑍𝑛 , 1, −1 ). Graf siklik juga dapat di bentuk dari sebuah graf linier dengan 𝑛 titik dengan menghubungkan titik 𝑣1 dan 𝑣𝑛 . Pelabelan titik pada graf siklik adalah dengan mengkorespondensikan 𝑍𝑛 = {0,1,2, … , 𝑛 − 1} dengan {𝑣1, 𝑣2 , … , 𝑣𝑛 }.

2.7

PersamaanFiguratif (Figure Equation)

Teorema 2.1 Polinomialkarakteristiksebaranggrafberara h D dengan𝑛 tititk secara umum adalah : 𝑋 𝐷 = 𝑥 𝑛 + 𝑡1 𝑥 𝑛−1 + 𝑡2 𝑥 𝑛−2 + ⋯ + 𝑡𝑛 −1 𝑥 + 𝑡𝑛 Koefisien𝑡𝑖 untuk 1 ≤ 𝑖 ≤ 𝑛 dapat dihitung dengan menggunakan persamaan figuratif sebagai berikut : (−1)𝑝(𝐿)

𝑡𝑖 = 𝐿∈ℒ𝑖

ℒ 𝑖 adalah himpunan semua sugraf berarah linier 𝐿 dari graf berarah D dengan tepat 𝑖 titik, sedangkan 𝑃(𝐿)adalahbanyaknyakomponendari𝐿 (banyaknya sikel berarah linier ).

PEMBAHASAN 3.1

PolinomialKarakteristik Graf Linier

Lemma 3.1 Jika𝑋 𝑇𝑛 = 𝑥 𝑛 + 𝑡1 𝑥 𝑛−1 + 𝑡2 𝑥 𝑛−2 + ⋯ + 𝑡𝑛−1 𝑥 + 𝑡𝑛 adalahpolinomialkarakteristikdarigraf linier dengan𝑛 titik maka koefisien 𝑡𝑖 = 0 untuk 𝑖 ganjil dan 𝑖 ≤ 𝑛. Bukti :

Langkah pertama untuk membuktikan Lemma diatas adalah dengan menunjukkan bahwa, 𝑖 setiap 𝐿𝜖ℒ𝑖 terdiri dari 2 sikel berbeda dengan panjang dua. Diketahui sebuah graf 𝑇𝑛 dengan 𝑉 𝑇𝑛 = {𝑣1 , 𝑣2 , … , 𝑣𝑛 }, misal diambil sebarang titik 𝑣𝑘 dimana 𝑘 adalah indek titik terkecil pada 𝐿𝜖ℒ 𝑖 untuk 1 ≤ 𝑘 ≤ 𝑛, artinya jika 𝑣𝑘 𝜖𝐿 maka {𝑣1 , 𝑣2 , … , 𝑣𝑘−1 } ∉ 𝐿, karena 𝐿 subgraf berarah linier maka berdasarkan Definisi 2.5 dan Definisi 2.13, Diperoleh : 𝑣𝑘 𝜖 𝐿 → 𝑣𝑘+1 ∈ 𝐿 Titik 𝑣𝑘+1 memiliki sebuah busur yang berasal dan menuju titik 𝑣𝑘 sehingga titik 𝑣𝑘 dan 𝑣𝑘+1 membentuk subgraf berarah linier denganpanjangdua, akibatnya𝑣𝑘+1 tidak terhubung dengan 𝑣𝑘+2 pada 𝐿. Dengan langkah yang sama, dapat diambil sebarang titik terdekat dengan 𝑣𝑘+1 misal titik 𝑣𝑠 𝜖 𝐿𝜖ℒ𝑖 untuk setiap 𝑘 + 1 ≤ 𝑠 ≤ 𝑛. Karena𝐿 subgraf berarah linier maka berdasarkan Definisi 2.5 dan Definisi 2.13, diperoleh : 𝑣𝑠 𝜖 𝐿 → 𝑣𝑠+1 𝜖𝐿 Titik𝑣𝑠+1 memiliki sebuah busur yang berasal danmenujutitik𝑣𝑠 , akibatnya 𝑣𝑠+1 tidak terhubung dengan titik 𝑣𝑠+2 pada 𝐿, sehingga 𝑣𝑠 dan 𝑣𝑠+1 membentuk subgraf berarah linier dengan panjang dua. Hal ini menunjukkan bahwa, setiap titik 𝑣𝑖 𝜖𝐿 hanya memiliki sebuah busur yang berasal dan menuju ke tepat satu titik yang terhubung langsung, yaitu 𝑣𝑖+1 𝜖𝐿 sehingga membentuk subgraf berarah linier dengan panjang 2 atau dengan kata lain setiap 𝑖 𝐿𝜖ℒ𝑖 terdiri dari 2 sikel berbeda dengan panjang dua. Langkah selanjutnya adalah menghitung 𝑛 −1 koefisien𝑡 2𝑗 +1 untuk setiap 0 ≤ 𝑗 ≤ 2 dengan memeriksa ℒ2𝑗 +1 . Berdasarkan langkah pembuktian diatas, diperoleh bahwa setiap 𝐿𝜖ℒ2𝑗 +1 terdiri dari

2𝑗 +1

2𝑗 +1

2

sikel berbeda dengan panjang dua.

Untuk menghitung setiap koefisien 𝑡𝑖 dengan 𝑖 genap dapat dilakukan dengan mencari kardinalitas ℒ 𝑖 = ℒ 2𝑚 ( ℒ 2𝑚 ) untuk 1 ≤ 𝑚 ≤ 𝑛 terlebih dahulu .Langkah pertama adalah melabel 2 subgrafberarah dengan panjang dua dengan indektitik terendahnya. Setiap𝐿𝜖ℒ 2𝑚 dengan 2𝑚 2𝑚 titik, terdiri dari 2 sikel berbeda dengan panjang dua, sehinggan ℒ2𝑚 = banyaknya cara menempatkan 𝑚 pias yang tidak berurutan dari sebanyak 𝑛 − 1 pias yang tersedia. ℒ 2𝑚 ekivalen dengan banyaknya cara memilih 𝑚 bilangan dari {1,2, … , 𝑛 − 1} sedemikian hingga tidak ada dua bilangan yang berurutan. Misal bilangan-bilangan tersebut adalah 𝑛1 , 𝑛2 , … , 𝑛𝑚 Sedemikian hingga1 ≤ 𝑛1 < 𝑛2 < ⋯ < 𝑛𝑚 ≤ 𝑚 − 1. Misal : 𝑥1 = 𝑛1 ≥ 1, 𝑥2 = 𝑛2 − 𝑛1 > 2 karena 𝑛1 tidak berdekatan dengan 𝑛2 . 𝑥 3 = 𝑛3 − 𝑛 2 > 2 karena 𝑛3 tidak berdekatan dengan 𝑛2 , terdapat sebanyak 𝑚, sehingga 𝑥𝑚 = 𝑛𝑚 +1 − 𝑛𝑚 > 2karena𝑛𝑚 tidak berdekatan dengan 𝑛𝑚 +1 dan 𝑥𝑚 +1 = 𝑛 − 1 − 𝑛𝑚 ≥ 0 ....................................(*) Karenater dapat sebanyak𝑛 − 1 bilangan, maka berakibat : 𝑥1 + 𝑥2 + ⋯ + 𝑥𝑚+1 = 𝑛 − 1............................(**) Penjelasan diatas ekivalen dengan permasalahan mencari banyaknya solusi bulat dari persamaan (**) dengan syarat-syarat yang diberikan pada persamaan (*), dengan fungsi pembangkit sebagai berikut : 𝑃 𝑥 = 𝑥 + 𝑥 2 + ⋯ 𝑥 2 + 𝑥 3 + ⋯ 𝑚 −1 1 + 𝑥 + 𝑥2 + ⋯ 1 𝑚 +1 𝑃 𝑥 = 𝑥 2𝑚 −1 1−𝑥 ∼ 𝑚 +1+𝑡−1 𝑡 𝑃 𝑥 = 𝑥 2𝑚 −1 𝑥 𝑡 ∼

𝑡=0

𝑃 𝑥 = 𝑡=0

𝑚 + 𝑡 𝑡+2𝑚 −1 𝑥 𝑡

Karena 2 bukan bilangan bulat maka ℒ2𝑗 +1 = ∅. Sehingga berdasarkan Teorema 2.1, 𝑡2𝑗 +1 = 𝑝(𝐿) =0 untuksetiap 0≤ 𝑗 ≤ 𝐿∈ℒ2𝑗 +1 (−1)

Misal𝑡 + 2𝑚 − 1 = 𝑘, maka :

.∎ 2 Lemma 3.2 : Jika 𝑋 𝑇𝑛 = 𝑥 𝑛 + 𝑡1 𝑥 𝑛−1 + 𝑡2 𝑥 𝑛−2 + ⋯ + 𝑡𝑛−1 𝑥 + 𝑡𝑛 adalah polinomial karakteristik dari graf linier dengan 𝑛 titik maka koefisien 𝑡𝑖 adalah : 𝑛−𝑚 𝑡𝑖 = 𝑡2𝑚 = (−1)𝑚 untuk𝑖genapdan𝑖 ≤ 𝑛. 𝑚

Kofisiendari𝑥 𝑛−1 adalah 𝑎𝑛−1 dimana 𝑘 = 𝑛 − 1, maka : 𝑛−𝑚 𝑚 + 𝑛 − 1 − 2𝑚 + 1 𝑎𝑛−1 = = 𝑛 − 2𝑚 𝑛 − 𝑚 − 2𝑚 + 1 𝑛−𝑚 𝑎𝑛−1 = 𝑚 𝑛−𝑚 Sehingga ℒ 2𝑚 = 𝑎𝑛−1 = . 𝑚 Setiap 𝐿𝜖ℒ2𝑚 dibentuk oleh 𝑚 sikel berarah dengan panjang dua, sehingga 𝑃 𝐿 = 2.

𝑛−1

Bukti :

∼

𝑃(𝑥) = 𝑘−2𝑚 −1

𝑚 + 𝑘 − 2𝑚 + 1 𝑘 𝑥 𝑘 − 2𝑚 + 1

Berdasarkan Teorema 2.1 didapat koefisien 𝑡𝑖 untuk 𝑖 = 2𝑚 sebagai berikut. (−1)𝑃(𝐿) = (−1)𝑚 ℒ2𝑚

𝑡𝑖 = 𝑡2𝑚 = 𝐿𝜖ℒ2𝑚

= (−1)𝑚

𝑛−𝑚 .∎ 𝑚

Teorema 3.1 Misaldiberikangraf linier dengan𝑛 titik dengan polinomial karakteristik, 𝑋 𝑇𝑛 = 𝑥 𝑛 + 𝑡1 𝑥 𝑛−1 + 𝑡2 𝑥 𝑛−2 + ⋯ + 𝑡𝑛−1 𝑥 + 𝑡𝑛 makakoefisien𝑡𝑖 dari graf linier dengan 𝑛 titik adalah sebagai berikut : 𝑡𝑖 = 0 untuk 𝑖 ganjil dan 𝑖 ≤ 𝑛 𝑖

𝑡𝑖 = (−1)2 3.2

𝑖 2

𝑛− 𝑖 2

untuk 𝑖 genap dan 𝑖 ≤ 𝑛

PolinomialKarakteristik Graf Siklik

Lemma 3.3 Jika𝑋 𝐶(𝑍𝑛 , 1, −1 ) = 𝑥 𝑛 + 𝑡1 𝑥 𝑛−1 + 𝑛−2 𝑡2 𝑥 + ⋯ + 𝑡𝑛−1 𝑥 + 𝑡𝑛 adalahpolinomialkarakteristikgrafsiklikdengan order 𝑛, maka koefisien 𝑡𝑖 = 0 untuk 𝑖 ganjil dan 𝑖 ≤ 𝑛. Bukti : BerdasarkanDefinisi 2.14 yang merupakandefinisidarigrafsiklik, sertadenganmembandingkanstrukturgraf linier dengangrafsiklikdapatdiketahuibahwauntuk𝑖 ganjil dan 𝑖 < 𝑛, ℒ𝑖 = ∅. DenganmenggunakanTeorema 2.1, diperoleh, 𝑡𝑖 = 𝐿𝜖ℒ𝑖 (−1)𝑃(𝐿) = 0 .∎ Lemma 3.4 Jika𝑋 𝐶(𝑍𝑛 , 1, −1 ) = 𝑥 𝑛 + 𝑡1 𝑥 𝑛−1 + 𝑛−2 𝑡2 𝑥 + ⋯ + 𝑡𝑛−1 𝑥 + 𝑡𝑛 adalahpolinomialkarakteristikgrafsiklikdengan order 𝑛, maka koefisien 𝑛−𝑚 𝑛 𝑡𝑖 = 𝑡2𝑚 = (−1)𝑚 𝑛−𝑚 untuk 𝑖 genap dan 𝑚 𝑖 < 𝑛. Bukti : Menghitungkoefisien𝑡2𝑚 untuk 2 ≤ 2𝑚 < 𝑛 dapat dilakukan dengan mencari ℒ2𝑚 . Pada graf siklik ℒ2𝑚 dapat dibagi menjadi dua himpunan bagian yaitu himpunan 𝐴 dan 𝐵. 𝐴 adalah himpunan bagian dari ℒ2𝑚 tanpamenggunakansikeldenganpanjangduamisa l(𝑣1 , 𝑣1 , 𝑣2 , 𝑣2 , 𝑣2 , 𝑣1 , 𝑣1 ) atau dapat ditulis (1 ⟷ 2). 𝐵adalah himpunan bagian dari ℒ 2𝑚 yang memuat sikel (1 ⟷ 2).ℒ 2𝑚 = 𝐴 ∪ 𝐵sehingga ℒ2𝑚 = 𝐴 + 𝐵 .............(*)

𝐶(𝑍𝑛 , 1, −1 ) dengan menghapus busur dari sikel (1 ⟷ 2) merupakan graf linier dengan 𝑛 titik 𝑇𝑛 sehingga, 𝑛−𝑚 𝐴 = ℒ 2𝑚 pada graf 𝑇𝑛 = ...............(**) 𝑚 𝐵 adalah himpunan bagian dari ℒ 2𝑚 yang memuat sikel (1 ⟷ 2) maka 𝐵 adalah banyaknya cara memilih 𝑚−1 sikel denganpanjangduapadagraf𝐶 𝑍𝑛 , 1, −1 − (1 ⟷ 2)) dengan menghapus titik-titik pada sikel tersebut, dengan kata lain 𝐵 adalah banyaknya cara memilih 𝑚 − 1 sikel berbeda dengan panjang dua pada graf 𝑇𝑛−2 . Analog denganpembuktian Lemma 3.2, 𝐵 = 𝑛−2− 𝑚−1 𝑚−1 𝑛−𝑚−1 𝐵 = ............(***) 𝑚−1 Berdasarkanpersamaan (*),(**) dan (***) didapat : ℒ2𝑚 = 𝐴 + 𝐵 𝑛−𝑚 𝑛−𝑚−1 ℒ 2𝑚 = + 𝑚 𝑚−1 𝑛 𝑛−𝑚 ℒ 2𝑚 = 𝑚 𝑛−𝑚 Selanjutnyauntuksetiap𝐿𝜖ℒ 2𝑚 𝑃 𝐿 = 𝑚 untuk 2 ≤ 2𝑚 < 𝑛, sehingga berdasarkan Teorema 2.1, didapat : 𝑡𝑖 = 𝑡2𝑚 =

𝐿𝜖 ℒ2𝑚

(−1)𝑃(𝐿) = (−1)𝑚 ℒ 2𝑚

= (−1)𝑚

𝑛 𝑛−𝑚 𝑚 𝑛−𝑚

untuk𝑖 < 𝑛.∎ Lemma 3.5 : Jika𝑋 𝐶(𝑍𝑛 , 1, −1 ) adalah polinomial karakteristik graf siklik dengan order 𝑛 maka koefisien 𝑡𝑖 untuk 𝑖 = 𝑛 adalah : 𝑛

𝑡𝑖 = −2 untuk 𝑛 ganjil dan 𝑡𝑛 = −2 + 2 −1 2 untuk 𝑛 genap. Bukti : Padagraf𝐶(𝑍𝑛 , 1, −1 ) terdapat dua sikel dengan panjang 𝑛, yaitu sikel dengan arah positif dan sikeldenganarahnegatif.SehinggaberdasarkanTeore ma 2.1, untuk 𝑛 ganjil didapat : (−1)𝑃(𝐿) = (−1)1 + (−1)1 = −2

𝑡𝑛 = 𝐿𝜖ℒ𝑛

Untuk𝑛genap, BerdasarkanTeorema 2.1, didapat : 𝑡𝑛 =

−1 𝐿𝜖ℒ𝑛

𝑃 𝐿 𝑛

= −1

1

+ −1

1

+ −1

𝑛 2

𝑡𝑛 = −2 + (−1)2 .∎ Berdasarkan Lemma 3.3 dan Lemma 3.4 didapatTeoremasebagaiberikut :

Teorema 3.2 Jika𝐶(𝑍𝑛 , 1, −1 ) adalah sebuah graf siklik yang memiliki order 𝑛 dengan polinomial karakteristik, 𝑋 𝐶(𝑍𝑛 , 1, −1 = 𝑥 𝑛 + 𝑡1 𝑥 𝑛−1 + 𝑡2 𝑥 𝑛−2 + ⋯ + 𝑡𝑛−1 𝑥 + 𝑡𝑛 Makakoefisien𝑡𝑖 adalah sebagai berikut : 𝑡𝑖 = 0 untuk 𝑖 ganjil dan 𝑖 < 𝑛 𝑡𝑖 = −2 untuk 𝑖ganjil dan 𝑖 = 𝑛 𝑡𝑖 = (−1)

𝑖 2

𝑖

𝑛 𝑖 2

𝑖

𝑛−

𝑡𝑖 = −2 + 2 −1 3.4

𝑛−2 𝑛 2

untuk 𝑖genap dan 𝑖 < 𝑛

2

untuk 𝑖 genap dan 𝑖 = 𝑛

PolinomialKarakteristik Graf Tangga

Definisi 3.4 Secaraumumpolinomialkarakteristikdarigr aftanggadengan2𝑛 titik adalah : 𝑋 𝑅2𝑛 = 𝑥 2𝑛 + 𝑙1 𝑥 2𝑛−1 + 𝑙2 𝑥 2𝑛−2 + ⋯ 𝑙2𝑛−1 𝑥 + 𝑙2𝑛 Lemma 3.6 Misaldiberikangraftanggadengan2𝑛 titik, dengan polinomial karakteristik , 𝑋 𝑅2𝑛 = 𝑥 2𝑛 + 𝑙1 𝑥 2𝑛−1 + 𝑙2 𝑥 2𝑛−2 + ⋯ + 𝑙2𝑛 −1 𝑥 + 𝑙2𝑛 = 0 maka 2𝑛−1 koefisien 𝑙2𝑗 +1 = 0 untuk setiap 𝑗 ≤ 2 . Bukti : Untukmembuktikan Lemma diatas, terlebihdahuluharusditunjukkanbahwauntuksetiap 𝐿𝜖ℒ𝑗 dari graf 𝑅2𝑛 , dan 𝐶𝑘 adalah sebarang sikel berarah linier dengan panjang 𝑘 sedemikian hingga 𝐶𝑘 ⊆ 𝐿 maka 𝑘 selalu genap. Misaldiambiltitik𝑣𝑎 𝜖𝐶𝑘 ⊆ 𝐿𝜖ℒ𝑗 sebagai titik dengan indek terkecil dari 2𝑛 dan termasuk titik dalam 𝐶𝑘 , sehingga 1 ≤ 𝑎 ≤ 𝑛 dan 𝑣𝑎−1 ∉ 𝐶𝑘 . Sebuah busur dengan sumber titik 𝑣𝑎 hanya memiliki sebuahtitiktujuanyaitu𝑣𝑛−𝑎 , tapi hal ini kontradiksi dengan 𝑣𝑎 sebagai titik dengan indek terkecil, Begitu juga dengan 𝑣𝑏 untuk 𝑛 + 1 ≤ 𝑏 ≤ 2𝑛. Setiaptitikdalam𝐶𝑘 pastimemilikiindegreed anoutdegreesamadengansatu, karena𝑣𝑎−1 ∉ 𝐶𝑘 , sebuah busur yang menujutitik𝑣𝑎 hanya memiliki sebuah titik sumber yaitu 𝑣𝑛+𝑎 Sehingga : 𝑣𝑎 𝜖𝐶𝑘 ⟺ 𝑣𝑛+𝑎 𝜖𝐶𝑘 Sebuahbusur yang menujutitik𝑣𝑛+𝑎 hanya memiliki sebuah titik sumber yaitu 𝑣𝑎 . Akibatnya 𝐶𝑘 adalah sebuah sikel berarah yang memiliki panjang dua. Sejalandenganlangkahdiatas, sebuahbusurdengantitiksumber𝑣𝑎 memiliki titik tujuan 𝑣𝑎+1 𝜖𝐶𝑘 dan busur dengan tujuan 𝑣𝑛+𝑎 harus memiliki titik sumber 𝑣𝑛+𝑎 +1 , maka 𝑣𝑎+1 𝜖𝐶𝑘 ⟺ 𝑣𝑛+𝑎+1 𝜖𝐶𝑘

Sehingga{𝑣𝑎 , 𝑣𝑎+1 , 𝑣𝑛+𝑎 , 𝑣𝑛+𝑎 +1 } ⊆ 𝐶𝑘 , jika sebuah busur dengan titik sumber 𝑣𝑎+1 dan tiik tujuan 𝑣𝑛+𝑎+1 , akan membentuk sikel dengan panjang empat (𝐶4 ). Begitujugadenganbusur yang memilikititiktujuan𝑣𝑎+2 𝜖𝐶𝑘 dan sebuah busur dengan titik tujuan 𝑣𝑛+𝑎+1 memilikititiksumber𝑣𝑛+𝑎 +2 . Sehingga, 𝑣𝑎+2 𝜖𝐶𝑘 ⟺ 𝑣𝑛+𝑎 +2 𝜖𝐶𝑘 Analog denganlangkahdiatasdapatditunjukkanbahwa 𝑣𝑐 𝜖𝐶𝑘 ⟺ 𝑣𝑛+𝑐 𝜖𝐶𝑘 Sikeltersebutakanberhenti di titik𝑣𝑏 , sebuah busur dengan sumber titik 𝑣𝑏 hanya memiliki sebuah titik target yaitu titik 𝑣𝑏−𝑛 , dimana 𝑣𝑏 adalah titik dengan indek terbesar pada sikel tersebut. Sehingga 𝐶𝑘 terdiri dari himpunan pasangan berurutan titik 𝑣𝑐 , 𝑣𝑛+𝑐 sehingga 𝑘 genap. Karenasetiap 𝐶𝑘 pada graf 𝑅2𝑛 merupakan sikel dengan panjang genap maka 𝐿𝜖ℒ 2𝑗 +1 merupakan penjumlahan sikel-sikel dengan panjang genap. Sehingga ℒ 2𝑗 +1 = ∅, berdasarkan 2𝑛−1

Teorema 2.1, 𝑙2𝑗 +1 = 0 untuk setiap 𝑗 ≤ 2 .∎ Koefisien𝑙2𝑚 diperoleh dengan memeriksa himpunan ℒ 2𝑚 .dengan memperhatikan Å ⊆ ℒ 2𝑚 dimana, Å = {𝐿𝜖ℒ 2𝑚 |𝐿 terdiri dari 𝑚 sikel berbeda dengan panjang dua} Untuksetiap0 ≤ 𝑐 ≤ 𝑚, 𝐿𝑐 𝜖 Å ⊆ ℒ 2𝑚 terdiri dari sebuah rantai dari sikel dengan panjang dua yang berhubungan langsung dan 𝑚 − 𝑐 sikel dengan panjangdua yang tidakberhubunganlangsung. Dapatdidefinisikansikeldenganpanjangdua(𝑣𝑖 ↔ 𝑣𝑛+𝑖 ) berhubungan langsung dengan sikel yang memiliki panjang dua yaitu (𝑣𝑖−1 ↔ 𝑣𝑛+𝑖−1 ) dan (𝑣𝑖+1 ↔ 𝑣𝑛+𝑖+1 ). Sebuah rantai dari 𝑐 sikel berbeda dengan panjangdua yang berhubunganlangsugadalah :{ 𝑣𝑖 ↔ 𝑣𝑛+𝑖 , 𝑣𝑖+1 ↔ 𝑣𝑛+𝑖+1 , … , 𝑣𝑖+𝑐−1 ↔ 𝑣𝑛+𝑖+𝑐−1 } Selanjutnyaadalahmemeriksahimpunan ℬ ⊆ ℒ 2𝑚 dimana, ℬ = {𝐿𝜖ℒ 2𝑚 |𝐿 menggunakan 2𝑚 titik yang sama dengan 𝐿𝑐 } Lemma 3.7 ℬ = {𝐿𝜖ℒ 2𝑚 |𝐿 menggunakan 2𝑚 titik yang sama dengan 𝐿𝑐 }, ℬ ⊆ ℒ 2𝑚 maka, 𝐿𝜖ℬ (−1)𝑃(𝐿) = 0 Untukmembuktikan Lemma diatas, yang harusdiperhatikanadalah𝑃(𝐿) untuk setiap 𝐿𝜖ℬ. Sebagai contoh misal 𝑐 = 2, maka ℬ memiliki dua elemen, yang pertama adalah terdiri dari 𝑚pias, menggunakan𝑚 sikel sikel berbeda dengan panjang dua, dan yang kedua adalah 𝑚 − 1 pias

menggunakan 𝑚 − 2 sikel berbeda dengan panjang dua serta sebuah sikel dengan panjang empat. Untuksetiap𝐿𝜖ℬ, 𝑚 − 𝑐 yang merupakan sikel dengan panjang dua yang tidak berhubungan langsung dan selalu menghasilkan 𝑚 − 𝑐 pias. Dengan memperhatikan himpunan 𝐶 ⊆ 𝐿 yang merupakan rantai dari pasangan titik yang berdekatan dimana 1 ≤ 𝑃 𝐶 ≤ 𝑐. Misal diandaikan 𝑐−1 terdapat caraberbedauntukmenggambar𝐶 𝑘−1 dalam 𝑘 pias. Pengandaian tersebut akan dibuktikan kebenarannya dengan menggunakan induksi matematika. Untuk𝑃 𝐶 = 1, hanya terdapat sebuah pilihan yaitu sikel dengan panjang 2𝑐. 𝑐−1 1= . 0 Untuk𝑃 𝐶 = 2, dapat dilakukan dengan menetapkan sebuah pilihan untuk menjadi sikel yang pertama dan menjadikan sisa titik menjadi sikel yang kedua. Sehingga 𝑐−1 terdapat pilihan. 1 Untuk𝑃 𝐶 = 𝑘 − 1, diasumsikan 𝑐−1 terdapat cara utuk membentuk 2𝑐 𝑘−2 titik menjadi 𝑘 − 1 sikel berbeda. Makauntuk𝑃 𝐶 = 𝑘, dapat dipilih sikel yang pertama dan menjumlahkan setiap cara untuk membentuk titik-titik yang tersisa menjadi 𝑘 − 2 sikel berbeda. Jumlahdarikemungkinankemungkinantersebutadalahsebagaiberikut : 𝑐−1−1 𝑐−1−2 𝑐−1−3 + + +⋯ 𝑘−2 𝑘−2 𝑘−2 𝑐−1− 𝑐−𝑘+1 + 𝑘−2 𝑐−1 = 𝑘−1 Berdasarkanpembuktiandiatasdapatdisimp 𝑐−1 ulkanbahwaterdapat cara berbeda untuk 𝑘−1 menggambar 𝐶 dalam 𝑘 pias. Sehingga untuk 𝐿𝜖ℒ 𝐵 , 𝑃 𝐿 = 𝑘 + (𝑚 + 𝑐), dan 𝑐

𝐿𝜖𝐵

−1

𝑃 𝐿

= −1

𝑚 −𝑐

−1 𝑘=1

𝑘

𝑐−1 𝑘−1

−1 𝑃 𝐿 = 0.∎ Pada Lemma diatas𝐿𝑐 memiliki sebuah rantai dari sikel dengan panjang dua yang berhubungan langsung, tetapi Å memuat elemenelemen dengan rantai yang lebih dari satu. Dengan mempertimbangkan 𝐿{𝑐} 𝜖Å dengan 𝑐 = {𝑐1 , 𝑐2 , … , 𝑐𝑖 } yang 𝐿𝜖𝐵

merupakanhimpunanrantaidenganpanjang𝑖, dan 𝑚 − {𝑐} adalah sikel dengan panjang dua yang tidak berhubungan langsung. 𝐶 = 𝐿𝜖ℒ 2𝑚 𝐿menggunakan2𝑚 titik yang sama dengan 𝐿{𝑐} }, 𝐶 dapat dipartisi menjadi penjumlahandarijumlahmasing-masingrantainya, sebagaiberikut : (−1)𝑃(𝐿) 𝐿𝜖𝐶

= (−1)𝑚 −𝑐

(−1)𝑃(𝐶1 )

…

(−1)𝑃(𝐶𝑖 )

Berdasarkan Lemma 3.7 setiappiaspadaruaskanandaripersamaandiatassamad engannol, sehinggahasilpenjumlahannyajugasamadengan nol. Olehkarenaelemenelemendariℒ2𝑚 hanyadibangunolehsikeldenganpanja ngdua yang tidakberhubunganlangsung. Misalℛ ⊆ ℒ 2𝑚 adalah himpunan semua sikel dengan panjang dua yang tidak berhubungan langsung, 𝑙2𝑚 = 𝐿𝜖ℛ2𝑚 (−1)𝑃(𝐿) , 𝑃 𝐿 =𝑚 sehingga 𝑙2𝑚 = (−1)𝑚 ℛ2𝑚 . Lemma 3.8 Misaldiberikangraftanggadengan2𝑛 titik, dengan polinomial karakteristik , 𝑋 𝑅2𝑛 = 𝑥 2𝑛 + 𝑙1 𝑥 2𝑛−1 + 𝑙2 𝑥 2𝑛−2 + ⋯ + 𝑙2𝑛 −1 𝑥 + 𝑙2𝑛 maka 𝑚 𝑛+1−𝑚 koefisien 𝑙2𝑚 = (−1) utuk1 ≤ 𝑚 ≤ 𝑚 𝑛. Bukti : Untukmembuktikan Lemma diatas, langkah yang harusdilakukanadalahmencarikardinalitasdariℛ2𝑚 . Setiap sikel dengan panjang dua pada ℛ2𝑚 dapat dilabel dengan indek titik terendahnya misal sebuah sikel (𝑣𝑖 , 𝑣𝑖 , 𝑣𝑛+𝑖 , 𝑣𝑛+𝑖 ) atau dapat ditulis (𝑣𝑖 ⟷ 𝑣𝑛+𝑖 ) dilabel dengan 𝑖. ℛ2𝑚 merupakanbanyaknyacaramenempatkan𝑚 sikel berbeda dengan panjang dua yang tidak berhubungan langsung hal ini ekivalen dengan banyaknyacaramemilih𝑚 bilangan dari {1,2, … , 𝑛} sedemikian hingga tidak ada dua bilangan yang berurutan. Analog dengan langkah pembuktian pada 𝑛+1−𝑚 Lemma 3.2 didapat ℛ2𝑚 = . 𝑚 Setiap𝐿𝜖ℛ2𝑚 terdiri dari 𝑚 sikel berbeda dengan panjang dua sehingga 𝑃 𝐿 = 𝑚, berdasarkan Teorema 3.2 diperoleh : 𝑙2𝑚 =

𝐿𝜖 ℛ2𝑚

−1

ℛ2𝑚 = (−1)𝑚 utuk1 ≤ 𝑚 ≤ 𝑛.∎

𝑃 𝐿

= −1

𝑛+1−𝑚 𝑚

𝑚

8

DAFTAR PUSTAKA Berdasarkan Lemma 3.7 dan Lemma 3.8 diperoleh teorema berikut,

Teorema 3.3 Misal diberikan graf tangga dengan 2𝑛 titik, jika polinomial karakteristik graf 𝑅2𝑛 adalah 𝑋 𝑅2𝑛 = 𝑥 2𝑛 + 𝑙1 𝑥 2𝑛−1 + 𝑙2 𝑥 2𝑛−2 + ⋯ + 𝑙2𝑛−1 𝑥 + 𝑙2𝑛 maka koefisien 𝑙𝑖 adalah sebagai berikut: 𝑙𝑖 = 0 untuk 𝑖 ganjil dan 𝑖 ≤ 𝑛 𝑙𝑖 = (−1)

𝑖 2

𝑛+1− 𝑖

𝑖

2

untuk 𝑖 ganjil dan 𝑖 ≤ 𝑛

2

KESIMPULAN Berdasarkan pembahasan pada BAB III dan sejalan dengan rumusan masalah pada BAB I dapat disimpulkan beberapa hal sebagai berikut : 

Dengan menggunakan persamaan figuratif, setiap koefisien dari graf linier adalah : 𝑡𝑖 = 0 untuk 𝑖 ganjil dan 𝑖 ≤ 𝑛 𝑖

𝑡𝑖 = (−1)2 

𝑖 2

𝑛− 𝑖 2

untuk 𝑖 ganjil dan 𝑖 ≤ 𝑛

Dengan menggunakan persamaan figuratif, setiap koefisien dari graf siklik adalah : 𝑡𝑖 = 0untuk 𝑖 ganjil dan 𝑖 < 𝑛 𝑡𝑖 = −2untuk 𝑖 ganjil dan 𝑖 = 𝑛 𝑡𝑖 = (−1)

𝑖 2

𝑖<𝑛

𝑖

𝑛 𝑖 2

𝑛−2 𝑖

𝑛−

untuk 𝑖 genap dan

2 𝑛

𝑡𝑖 = −2 + 2 −1 2 untuk 𝑖genap dan 𝑖 = 𝑛 

Dengan menggunakan persamaan figuratif, setiap koefisien dari graf tangga adalah : 𝑙𝑖 = 0 untuk 𝑖 ganjil dan 𝑖 ≤ 𝑛 𝑙𝑖 = (−1) 𝑖≤𝑛

f

𝑖 2

𝑖

𝑛+1−2 𝑖

2

untuk 𝑖 genap dan

[1]

Budayasa, I Ketut. 2007. Teori Graph dan Aplikasinya. Surabaya:University Press UNESA. [2] Chartrand, G dan Lesniak, L. 1996. Graphs and Digraphs [third editions]. USA: Chapman & Hall/CRC. [3] Cvetkovic, M Dragos, Doob Michael dan Sachs,Horst. 1979. Spectra of graphs. New York : Academic Press,Inc. [4] Diestel,Reinhard. 2000. Graph Teory Electronic Edition 2000. New York : Springer-Verlag,inc. [5] Godsil,Chris dan Royle,Gordon.2001.Algebraic Graph Theory. New York : Springer-Verlag,inc. [6] Gross, L. Jonathan dan Tucker, W. Thomas.1987. Topological Graph Theory. United States of America. [7] Gallian, A, Joseph. 2010. Contemporary Abstact Algebra Seventh Edition. United States of America : Brooks/Cole, Cengage Learning. [8] Coon, E. Taylor.2006.Combinatoric of The Figure Equation on Directed Graph.