POLINOMIAL KARAKTERISTIK PADA GRAF KINCIR ANGIN BERARAH

Faktor Exacta 10 (2): 111-117, 2017 p-ISSN: 1979-276X e- ISSN: 2502-339X Andrari – Polinomial Karakteristik Pada Graf....

POLINOMIAL KARAKTERISTIK PADA GRAF KINCIR ANGIN BERARAH FINATA RASTIC ANDRARI [email protected] Program Studi Teknik Informatika Fakultas Teknik, Matematika dan Ilmu Pengetahuan Alam Universitas Indraprasta PGRI Abstrak. Misalkan G suatu graf berarah dengan V(G) = {1, 2, …, n}. Matriks adjacency dari graf berarah G adalah matriks A = [aij] yang berukuran n x n yang didefinisikan dengan aij = 1, untuk i ≠ j jika terdapat busur berarah dari i ke j dan aij = 0 untuk selainnya. Pada tulisan ini akan dicari bentuk umum polinomial karakteristik dari matriks adjacency graf kincir angin berarah Qk, yaitu modifikasi dari suatu kelas graf Dutch Windmill yang ditambahkan satu simpul dan busur yang bertetangga dengan titik pusat kincir serta diberi orientasi untuk semua busurnya yaitu menuju ke titik pusat kincir, dengan k adalah banyak kincir dari graf tersebut. Kata kunci : graf kincir angin berarah, graf Dutch Windmill polinomial karakteristik, spectrum

, matriks adjacency,

Abstract. Let G be a directed graph with V (G) = {1, 2, ..., n}. The adjacency matrix of a directed graph G is a matrix A = [aij] size n x n defined by aij = 1, for i ≠ j if there is a directed arc from i to j, and aij = 0 for the other kind. In this paper look for common forms characteristic polynomial of the adjacency matrix of directed windmill graph Qk, which is a modification of Dutch Windmill graph ( ). That is added one node and arc that adjacent with central point windmill and were given an orientation for all bow toward the center point of mill , where k is a lot of wheel of the graph. Keyword : directed windmill graph, Dutch Windmill characteristic polynomial, spectrum

graph, adjacency matrix,

PENDAHULUAN Teori graf merupakan salah satu cabang ilmu matematika yang berkembang sangat pesat karena masih banyak sifat-sifat dari suatu graf yang belum diteliti lebih lanjut, salah satunya adalah matriks adjacency dari graf berarah. Graf G didefinisikan sebagai pasangan himpunan (V,E), yang dalam hal ini V adalah himpunan tak kosong dari simpul-simpul dan E adalah himpunan sisi yang menghubungkan sepasang simpul (Munir, 2014). Berdasarkan orientasi arah pada sisinya, graf dibedakan atas dua jenis yaitu graf tak-berarah dan graf berarah. Pada graf tak-berarah urutan pasangan simpul yang dihubungkan oleh sisi tidak diperhatikan, jadi (u,v) = (v, u). Pada graf berarah, sisi biasa disebut busur. Busur (u,v) dan (v, u) menyatakan dua buah busur yang berbeda, dengan kata lain (u,v) ≠ (v, u). (Munir, 2014) Graf yang tidak mengandung gelang (loop) atau sisi ganda disebut graf sederhana. Salah satu graf sederhana khusus yang dijumpai pada banyak aplikasi adalah graf siklik. Graf siklik adalah graf sederhana yang setiap simpulnya berderajat dua. Graf

- 111 -


siklik dengan n simpul dilambangkan dengan Cn. Jika simpul-simpul pada Cn adalah v1, v2, ..., vn, maka sisi-sisinya adalah (v1, v2), (v2, v3), ..., (vn-1, vn), dan (vn, v1). Dengan kata lain, ada sisi dari simpul terakhir, vn, ke simpul pertama, v1. (Munir, 2014). Graf Dutch Windmill yang dinotasikan adalah graf yang diperoleh dari mengambil graf siklik Cn dengan sebuah simpul berimpitan (lihat Gambar 1). Graf Dutch Windmill memuat simpul dan sisi (Kanna, 2016). Dalam artikel ini akan dibahas suatu kelas graf berarah yaitu graf kincir angin berarah yang dilambangkan dengan Qk. Graf kincir angin berarah Qk merupakan modifikasi dari graf Dutch Windmill yang ditambahkan satu simpul dan sebuah busur yang bertetangga dengan titik pusat kincir serta diberi orientasi yaitu untuk semua busurnya menuju ke titik pusat kincir. Dari graf tersebut akan dicari bentuk umum dari polinomial karekteristik serta nilai eigen dari matriks adjacency-nya. Graf Qk memiliki simpul sebanyak 3k + 2 dan busur sebanyak 4k + 1 untuk k ≥ 1.

Gambar 1. Graf Dutch Windmill Sumber : http://mathworld.wolfram.com/WindmillGraph.html METODE Penelitian ini dilakukan melalui studi literatur dengan mempelajari makalah dan buku-buku yang berkaitan dengan topik penelitian. Selanjutnya hasil studi literatur tersebut digunakan sebagai landasan teori untuk mendapatkan sifat-sifat polinomial karakteristik matriks adjacency dan menentukan spektrum matriks adjacency dari graf kincir angin berarah (Qk). HASIL DAN PEMBAHASAN Sebelum diberikan pembahasan lebih lanjut tentang graf Qk, berikut ini akan diberikan beberapa definisi yang diperlukan untuk pembahasan selanjutnya. Definisi 1. Misalkan adalah suatu matriks berukuran , skalar adalah nilai eigen dari matriks jika terdapat vektor yang memenuhi persamaan . Vektor yang memenuhi kesamaan tersebut dinamakan vektor eigen yang bersesuaian dengan nilai

- 112 -


eigen . Polinomial karakteristik dari adalah bentuk polinom dari akar polinomial karakteristik tersebut merupakan nilai eigen dari matriks 2000)

. Akar. (Meyer,

Definisi 2. Misalkan G suatu graf berarah dengan V(G) = {1, 2, …, n}. Matriks adjacency dari graf berarah G adalah matriks A = [aij] yang berukuran n x n yang didefinisikan

Definisi 3. Spektrum dari suatu graf G adalah himpunan nilai eigen dari matriks adjacency A dengan λ0 > λ1 > … > λs-1 , beserta masing-masing multiplisitasnya adalah m(λ0), m(λ1), …, m(λs-1), maka spektrum graf G dapat dituliskan

Graf kincir angin berarah Qk merupakan modifikasi dari graf yang ditambahkan satu simpul dan busur yang bertetangga dengan titik pusat kincir. Pada graf ini juga diberi orientasi yang semua sisinya berarah menuju ke titik pusat kincir (lihat Gambar 2).

Gambar 2. Graf kincir angin berarah Qk Selanjutnya dicari polinomial karakteristik dari graf Qk, untuk . Untuk mendapatkan polinomial karakteristik dari suatu graf, terlebih dahulu tentukan matriks adjacency dari graf tersebut sesuai Definisi 2. Matriks adjacency dari graf Qk  untuk Graf Qk untuk k = 1 memiliki jumlah simpul sebanyak Dan memiliki jumlah sisi sebanyak Matriks adjacency-nya adalah sebagai berikut

- 113 -


Berdasarkan Definisi 1, polinomial karakteristik dari sehingga akan diperoleh

adalah det

,

 untuk Graf Qk untuk k = 2 memiliki jumlah simpul sebanyak Dan memiliki jumlah sisi sebanyak Matriks adjacency-nya adalah sebagai berikut

Dengan cara yang sama akan diperoleh polinomial karakteristik dari matriks adjacency adalah

 untuk Graf Qk untuk k = 2 memiliki jumlah simpul sebanyak

- 114 -


dan memiliki jumlah sisi sebanyak Matriks adjacency-nya adalah sebagai berikut

Dari matriks adjacency

diperoleh polinomial karakteristik

Hasil polinomial karakteristik dari graf untuk diringkas dalam Tabel 1. Pada Tabel 1 juga ditampilkan hasil polinomial karakteristik serta nilai eigen dari graf untuk . Tabel 1. menampilkan bentuk graf kincir angin berarah beserta polinomial karakteristik dan nilai eigen dari matriks adjacency untuk nilai k = 1, 2, …, 6. Berdasarkan tabel tersebut, terlihat bahwa untuk nilai k = 1,2, …, 6 polinomial karakteristiknya adalah λn, dimana n adalah banyak simpul dari grafnya. Hal tersebut jelas mengakibatkan nilai eigen dari matriks adjacency-nya adalah 0. Bentuk ini akan dibuktikan pada Teorema 1 yang menunjukkan bahwa hal tersebut berlaku secara umum.

k 1 2

Tabel 1. Polinomial karakteristik dan nilai eigen dari Graf untuk Banyak Polinomial Vektor Eigen Simpul Karakteristik 5 8

- 115 -


3 4 5 6

11 14 17 20

Teorema 1. Misalkan adalah graf kincir angin berarah dengan k ≥ 1. Misalkan adalah matriks adjacency dari yang berukuran n x n. Maka polinomial matriks adjacency adalah Bukti Secara umum, matriks adjacency dari graf

dapat dituliskan

Maka bentuk polinomial karakteristik dari matriks

, adalah

Lemma 2. Misalkan adalah graf kincir angin berarah dengan k ≥ 1. Misalkan adalah matriks adjacency dari yang berukuran n x n.Maka spektrum matriks adjacency adalah

- 116 -


Bukti Berdasarkan Teorema 2.1 didapatkan bahwa polinomial karakteristik matriks adjacency dari graf kincir angin berarah dengan k ≥ 1 adalah . Maka Sehingga nilai karakteristik dari adalah 0 dengan multiplisitas n. Jadi spektrum matriks adjacency dari graf kincir angin berarah dengan k ≥ 1 adalah

□.

PENUTUP Simpulan Polinomial karakteristik matriks adjacency dari graf kincir angin berarah adalah , dengan spektrumnya yaitu

DAFTAR PUSTAKA Bapat, R. B. (2010). Graphs and Matrices. India : Hindustan Book Agency. Biggs, N. (1993). Algebaric Graph Theory (2nd ed). New York : Cambridge Mathematical Library. Kanna, M. R., Kumar, R. P., dan Jagadessh, R. (2016). Computation of Topological Indices of Dutch Windmill Graph. Open Journal of Discrete Mathematics. 6 : 74-81. Meyer, Carl D. (2000). Matrix Analysis and Applied Linier Algebra. New Jersey: SIAM. Munir, R. (2014). Matematika Diskrit. Bandung : Informatika Bandung.

- 117 -

POLINOMIAL KARAKTERISTIK PADA GRAF KINCIR ANGIN BERARAH

Recommend Documents