Ki_risti Dwi Rahayu_dekomposisi Graf Bunga Matahari

Dekomposisi Graf Bunga Matahari Risti Dwi Rahayu1, Putri Rizqi Musthofa2 1

Mahasiswa Prodi Pendidikan Matematika, FKIP, UNS Mahasiswa Prodi Pendidikan Matematika, FKIP, UNS E-mail: [email protected]

2

Abstrak

H i  dari subgraf G sedemikian sehingga E (G ) dan Ei  adalah partisi dari E (G ) . Jika H i 

Dekomposisi dari graf G adalah koleksi

Hi  Ei untuk suatu Ei subset

adalah sebuah dekomposisi dari G maka G dapat ditulis sebagai penjumlahan sisi

H1  H 2  H 3  ...  H n (sama pada faktorisasi) dan G didekomposisikan ke dalam H1 , H 2 , H 3 ,..., H n , subgraf dimana Dengan kata lain n | Hi  | . G  H1  H 2  H3  ...  H n adalah dekomposisi dari graf G . Graf bunga matahari adalah graf yang diperoleh dari sebuah graf roda

, yang vertex-vertex terminalnya

v1 , v2 , v3 ,..., vn dan vertex pusatnya v2 n1 , serta penambahan n buah titik yaitu vn1 , vn 2 , vn3 ,..., vn n , dimana vn i merupakan vertex yang terhubung langsung dengan vi dan vi 1 , untuk setiap i  1, 2,3,..., n . Graf bunga matahari mempunyai | V ( H n ) | 2n  1 dan | E ( H n ) | 4n . Graf bunga matahari SFn , dengan n  3 , dapat di adalah

partisi

menjadi

subgraf

Ai  Ei

yang

berupa

2K2

dimana

SFn  A1  A2  A3  ...  A2 n . Sehingga graf bunga matahari SFn dengan n  3

2K2 - dekomposisi. Graf bunga matahari SFn , dengan n  5 dapat di partisi menjadi subgraf Ai  Ei yang berupa 4K 2 dimana SFn  A1  A2  A3  ...  An . merupakan

Sehingga graf bunga matahari bunga matahari

SFn dengan n  5 merupakan 4K2 - dekomposisi. Graf

SFn , dengan n  3 dapat di partisi menjadi subgraf Ai  Ei yang

berupa P3 dimana SFn  A1  A2  A3  ...  A2 n . Sehingga graf bunga matahari dengan n  3 merupakan dapat

di

partisi

SFn

P3 - dekomposisi. Graf bunga matahari SFn , dengan n  3

menjadi

subgraf

Ai  Ei

yang

berupa

2P3

dimana

SFn  A1  A2  A3  ...  An . Sehingga graf bunga matahari SFn dengan n  3 merupakan

2P3 - dekomposisi.

Kata kunci: Dekomposisi, Graf Bunga Matahari

A. Pendahuluan Teori graf adalah salah satu ilmu matematika yang terus mengalami perkembangan baik dari segi teori maupun terapannya. Permasalahan jembatan

1

Konigsberg merupakan masalah yang pertama kali diselesaikan menggunakan graf oleh seorang matematikawan Swiss, Leonard Euler. Graf sendiri didefinisikan sebagai pasangan himpunan (V, E), dimana V adalah himpunan tak kosong dari elemen-elemen yang disebut titik (vertices atau node) dan E adalah himpunan yang mungkin kosong dari elemen-elemen yang disebut sisi (edges atau arcs), sedemikian sehingga setiap elemen dalam E menghubungkan sepasang vertex (Munir, 2012: 356). Sampai saat ini, teori graf sudah banyak digunakan untuk menyelesaikan masalah sehari-hari, seperti masalah jaringan di bidang ilmu komputer, riset operasi, komunikasi, transportasi, dan ilmu-ilmu sosial atau ilmu pengetahuan alam. Salah satu kajian tentang graf yang sudah berkembang adalah tentang dekomposisi graf. Dekomposisi dari graf G didefinisikan sebagai koleksi H i  dari subgraf G sedemikian sehingga H i  Ei

untuk suatu Ei subset E (G ) dan

Ei  adalah partisi dari E (G ) . Jika H i  adalah sebuah dekomposisi dari G, maka G dapat ditulis sebagai penjumlahan sisi H1  H 2  ...  H n , dimana n | Hi  | (Chartrand dan Lesniak, 1986: 239). Penelitian tentang dekomposisi graf memang telah banyak dibahas di beberapa artikel maupun skripsi. Akan tetapi, banyaknya jenis graf yang berkembang hingga sekarang membuat pembahasan tentang dekomposisi masih bisa dilanjutkan pada graf-graf lain yang belum pernah dikaji sebelumnya. Salah satu jenis graf yang terkenal adalah graf bunga matahari atau Sunflower Graph. Graf bunga matahari sebuah graf roda vertex

pusatnya

adalah graf yang diperoleh dari

, yang vertex-vertex terminalnya adalah v1 , v2 , v3 ,..., vn dan

v2 n 1 ,

serta

penambahan

n

buah

titik

yaitu

vn1 , vn 2 , vn3 ,..., vn n dimana vn i merupakan vertex yang terhubung langsung dengan vi dan vi 1 , untuk setiap i  1, 2,3,..., n . Berdasarkan hal tersebut, maka dalam makalah ini akan dibahas tentang Dekomposisi Graf Bunga Matahari.

2

B. Landasan Teori Definisi 1 Graf G didefinisikan sebagai pasangan himpunan (V(G), E(G)), ditulis dengan notasi G = (V(G), E(G)), dimana V(G) adalah himpunan tak kosong dari elemenelemen yang disebut titik (vertices atau node) dan E(G) adalah himpunan yang mungkin kosong dari elemen-elemen yang disebut sisi (edges atau arcs), sedemikian sehingga setiap elemen dalam E(G) menghubungkan sepasang vertex. (Rinaldi Munir, 2012: 356)

Definisi 2 Dua buah vertex pada graf tak berarah G dikatakan bertetangga bila keduanya terhubung langsung oleh sebuah sisi. Dengan kata lain, u bertetangga dengan v jika (u, v)  (v, u ) adalah sebuah sisi pada graf G. (Rinaldi Munir, 2012: 365)

Definisi 3 Untuk sembarang sisi e  (u, v)  (v, u ) , sisi e dikatakan bersisian dengan vertex u dan vertex v. (Rinaldi Munir, 2012: 365)

Definisi 4 Derajat suatu vertex pada graf tak berarah adalah jumlah sisi yang bersisian dengan simpul tersebut. Derajat vertex v dapat dinotasikan dengan d(v). (Rinaldi Munir, 2012: 366)

Definisi 5 Sebuah graf H disebut subgraf dari graf G jika tiap-tiap vertex dalam H merupakan anggota himpunan V(G) dan tiap-tiap sisi dalam H merupakan anggota himpunan E(G). Atau dapat ditulis V(H)

V(G) dan E(H)

E(G).

Subgraf H = (V(H), E(H)) disebut subgraf merentang dari graf G = (V(G), E(G)), apabila V(H) = V(G), yaitu H mengandung semua vertex dari G. (Rinaldi Munir, 2012: 372 & 374)

3

Definisi 6 Graf sederhana adalah graf yang tidak mempunyai loop dan sisi rangkap. Sisi rangkap dari suatu graf adalah jika dua titik yang dihubungkan oleh lebih dari satu sisi. Sedangkan yang disebut dengan loop adalah suatu sisi yang menghubungkan suatu titik dengan dirinya sendiri. (Fatkhiyah, 2010: 10)

Definisi 7 Graf

komplit adalah

graf

dengan

setiap

pasang

titik

yang

berbeda

dihubungkan oleh satu sisi. Graf komplit dengan n titik dinotasikan sebagai Kn. (Mandailina, 2009:18) Contoh :

Gambar 1. Graf Komplit

Definisi 8 Untuk suatu bilangan bulat banyak vertex n dan ukuran

, lintasan

adalah suatu graf yang memiliki

yang vertexnya dapat dinotasikan dengan

v1 , v2 , v3 ,..., vn sedangkan sisinya dinotasikan dengan ei  (vi , vi 1 ) , untuk setiap i  1, 2,3,..., n  1 . (Addinnitya, 2012: 8) Contoh :

Gambar 2. Graf Lintasan

Definisi 9 Graf sikel (Cycle graph) merupakan sebuah graf sederhana yang setiap vertex-nya berderajat dua. Banyaknya vertex minimal pada graf sikel adalah 3. Graf sikel

4

dengan n vertex dilambangkan dengan Cn . Banyaknya sisi sebuah graf sikel yang memiliki n buah vertex adalah n . (Rahmawati dan Rahajeng, 2014: 65) Contoh :

Gambar 3. Graf Sikel

Definisi 10 Graf roda Wn (Wheels graph) merupakan graf yang diperoleh dengan cara menambahkan satu vertex baru pada graf sikel Cn , sedemikian hingga setiap vertex pada graf sikel Cn berhubungan langsung dengan vertex baru tersebut. Banyaknya vertex pada graf roda adalah n  1 , sedangkan banyak sisinya adalah 2n (Rahmawati dan Rahajeng, 2014: 65). Dalam makalah ini, aturan pemberian

nama vertex pada graf roda adalah dimulai dari salah satu vertex terminalnya yaitu dari v1 , kemudian v2 , v3 , v4 , dan seterusnya hingga vn , dengan aturan searah jarum jam. Kemudian untuk vertex pusatnya diberi nama vn 1 . Contoh :

Gambar 4. Graf Roda

W6

Definisi 11 Khunti Qonaah dkk (dalam Inayah, 2013) mendefinisikan graf bunga matahari adalah graf yang diperoleh dari sebuah graf roda

, yang vertex-vertex

terminalnya adalah v1 , v2 , v3 ,..., vn dan vertex pusatnya v2 n 1 , serta penambahan

5

n buah titik yaitu vn1 , vn 2 , vn3 ,..., vn n , dimana vn  i merupakan vertex yang terhubung langsung dengan vi dan vi 1 , untuk setiap i  1, 2,3,..., n . Graf bunga matahari

mempunyai | V ( H n ) | 2n  1 dan | E ( H n ) | 4n .

Contoh :

Gambar 5. Graf Roda

SF6

Definisi 12 Graf G1 dan G2 dikatakan isomorfis ( G1  G2 ), jika terdapat korespondensi satusatu antara titik-titik pada G1 dan titik-titik pada G2 , serta antara sisi-sisi pada G1 dan sisi-sisi pada G2 , sedemikian sehingga jika sisi e bersisian dengan titik u dan v di G1 , maka sisi e ' yang berkorespondensi di G2 juga harus bersisian dengan titik

u ' dan v ' di G2 . (Rinaldi Munir, 2012: 386)

Definisi 13 Dekomposisi dari graf G adalah koleksi sehingga Hi  Ei

H i 

dari subgraf G sedemikian

untuk suatu Ei subset E (G ) dan

Ei  adalah

partisi dari

E (G ) . Jika H i  adalah sebuah dekomposisi dari G maka G dapat ditulis sebagai penjumlahan sisi H1  H 2  H 3  ...  H n dan G didekomposisikan ke dalam subgraf

H1 , H 2 , H 3 ,..., H n ,

dimana

n | Hi  | .

Dengan

kata

lain

G  H1  H 2  H3  ...  H n adalah dekomposisi dari graf G .

6

Jika H i  adalah dekomposisi graf G sedemikian hingga H i  H untuk sebuah graf H dan untuk setiap

i (1  i  n) ,

maka G dikatakan H -dekomposisi. Jika G

merupakan graf H -dekomposisi, maka dinotasikan H│G sehingga H dapat dikatakan pembagi banyaknya sisi di G dan G merupakan kelipatan dari H dan untuk setiap graf (tak kosong dan terhubung) merupakan K 2 -dekomposisi. (Rahmawati dan Rahajeng, 2014: 65-66) Contoh :

Gambar 6. Graf

G

Partisi sisi-sisi dari graf komplit G ditunjukkan sebagai berikut.

Gambar 7. Partisi dari Graf G

Dari gambar tersebut, dapat dilihat bahwa diperoleh 5 partisi dengan masingmasing terdiri dari 2 sisi. Jika G  H1  H 2  H 3  H 4  H 5 maka graf G dapat

7

di dekomposisi. Karena subgraf

Hi  2K2 , maka graf G adalah 2K2 -

dekomposisi.

C. Hasil dan Pembahasan Sebuah graf G dapat di dekomposisikan ke dalam subgraf A1 , A2 , A3 ,..., An , jika setiap subgraf A1 , A2 , A3 ,..., An tidak mempunyai sisi-sisi yang sama dan setiap subgrafnya tersebut saling isomorfis serta penjumlahan sisi semua subgraf

A1 , A2 , A3 ,..., An adalah graf G atau dapat ditulis G  A1  A2  A3  ...  An . Dekomposisi Graf Bunga Matahari 1. Misalkan diambil graf bunga matahari SFn dengan n  3 , kemudian graf bunga matahari SFn dipartisi menjadi subgraf Ai berupa 2K2 . Tabel 1. Dekomposisi dari graf bunga matahari Graf Bunga

Dekomposisi

A-dekomposisi

SF3  A1  A2  A3  A4 

Ai  2 K 2

Matahari

SF3

SFn Banyaknya titik dan sisi

| V ( Ai ) | 4 | E ( Ai ) | 2

A5  A6 (6 partisi)

SF4

SF4  A1  A2  A3  A4 

Ai  2 K 2

| V ( Ai ) | 4 | E ( Ai ) | 2

A5  A6  A7  A8 (8 partisi)

SF5

SF5  A1  A2  A3  A4 

Ai  2 K 2

| V ( Ai ) | 4 | E ( Ai ) | 2

A5  A6  A7  ...  A10 (10 partisi)

SF6

SF6  A1  A2  A3  A4 

Ai  2 K 2

| V ( Ai ) | 4 | E ( Ai ) | 2

A5  A6  A7  ...  A12 (12 partisi)

SF7

SF7  A1  A2  A3  A4 

Ai  2 K 2

| V ( Ai ) | 4 | E ( Ai ) | 2

A5  A6  A7  ...  A14 (14 partisi)

SF8

SF8  A1  A2  A3  A4  A5  A6  A7  ...  A16

Ai  2 K 2

| V ( Ai ) | 4 | E ( Ai ) | 2

(16 partisi)

8

SF9

SF9  A1  A2  A3  A4 

Ai  2 K 2

| V ( Ai ) | 4 | E ( Ai ) | 2

A5  A6  A7  ...  A18 (18 partisi) :

:

:

:

:

:

:

:

Ai  2 K 2

| V ( Ai ) | 4

SFn

SFn  A1  A2  A3  A4  A5  A6  A7  ...  A2 n

| E ( Ai ) | 2

(2n partisi)

Berdasarkan Tabel 1 maka diperoleh teorema sebagai berikut : Teorema: Graf bunga matahari SFn , dengan n  3 dan SFn  A1  A2  A3  ...  A2 n merupakan 2K 2 - dekomposisi. Bukti Ambil sebarang graf bunga matahari SFn Misal V (SFn )  v1 , v2 , v3 ,..., v2n1 , v2n , v2n1 E (SFn )  e1 , e2 , e3 ,..., e3n1 , e4 n 

Partisi graf bunga matahari SFn menjadi subgraf Ai  Ei

yang berupa 2K2 ,

dimana i  j maka Ai  Aj   . Misalkan SFn  A1  A2  A3  ...  A2 n . Partisi graf bunga matahari SFn sebagai berikut :  Untuk i  1, 2,3,..., n . Subgraf Ai  (vi , vi  n ), (vi 1 , v2 n 1 ) , dimana setiap i  1  n . Jika i  1  n , maka i  1 dinyatakan sebagai bilangan bulat 1, 2,3,..., n(mod n) . Akan ditunjukkan bahwa setiap subgraf tersebut saling lepas. Setiap subgraf dikatakan saling lepas jika i  j maka Ai  Aj   , dimana

i  1, 2,3,..., n dan j  1, 2,3,..., n . Akan dibuktikan melalui kontraposisinya.

9

Pernyataan jika i  j maka Ai  Aj   ekuivalen dengan mengatakan jika

Ai  Aj   maka i  j , dimana i  1, 2,3,..., n dan j  1, 2,3,..., n . Diketahui Ai  Aj   , maka ek  Ai  Aj , k  N . Hal ini berarti bahwa ek  Ai dan ek  Aj . Berdasarkan definisi, jika ek  Ai maka ek   vi , vi n  atau  vi 1 , v2 n1  . Begitu pula jika ek  Aj maka ek   v j , v j  n  atau  v j 1 , v2 n 1  Akibatnya,  vi , vi  n  =  v j , v j  n  dan  vi 1 , v2 n1  =  v j 1 , v2 n 1  . Sehingga diperoleh i  j . Jadi, terbukti bahwa jika Ai  Aj   maka i  j , dimana i  1, 2,3,..., n dan

j  1, 2,3,..., n . Hal ini juga membuktikkan bahwa, pernyataan jika i  j maka Ai  Aj   , dimana i  1, 2,3,..., n dan j  1, 2,3,..., n bernilai benar. Karena dapat dibuktikan jika i  j maka Ai  Aj   , berarti tidak ada sisi yang sama pada setiap subgraf.  Untuk i  n  1, n  2, n  3,..., 2n . Subgraf Ai  (vi , vi 1 n ), (vi  2 n , vi 3 n ) , dimana setiap i  1  n, i  2  n, i  3  n  n . Jika i  1  n, i  2  n, i  3  n  n , maka i  1  n , i  2  n , dan i  3  n dinyatakan sebagai bilangan bulat 1, 2,3,..., n(mod n) . Akan ditunjukkan bahwa setiap subgraf tersebut saling lepas. Setiap subgraf dikatakan saling lepas jika i  j maka Ai  Aj   , dimana

i  n  1, n  2, n  3,..., 2n dan j  n  1, n  2, n  3,..., 2n . Akan dibuktikan melalui kontraposisinya. Pernyataan jika i  j maka Ai  Aj   ekuivalen dengan mengatakan jika

Ai  Aj  

maka

i  j,

dimana

i  n  1, n  2, n  3,..., 2n

dan

j  n  1, n  2, n  3,..., 2n .

10

Diketahui Ai  Aj   , maka ek  Ai  Aj , k  N . Hal ini berarti bahwa ek  Ai dan ek  Aj . Berdasarkan definisi, jika ek  Ai maka ek   vi , vi 1n  atau  vi  2n , vi 3n  . Begitu pula jika ek  Aj maka ek   v j , v j 1 n  atau  v j  2 n , v j  3 n  Akibatnya,  vi , vi 1n  =  v j , v j 1n  dan  vi  2n , vi 3n  =  v j  2 n , v j  3 n  . Sehingga diperoleh i  j . Jadi,

terbukti

bahwa

jika

Ai  Aj  

i  j,

maka

dimana

i  n  1, n  2, n  3,..., 2n dan j  n  1, n  2, n  3,..., 2n . Hal ini juga membuktikkan bahwa, pernyataan jika i  j maka Ai  Aj   , dimana i  n  1, n  2, n  3,..., 2n dan

j  n  1, n  2, n  3,..., 2n bernilai

benar. Karena dapat dibuktikan jika i  j maka Ai  Aj   , berarti tidak ada sisi yang sama pada setiap subgraf. Dengan

demikian,

terbukti

bahwa

untuk

setiap

i  1, 2,3,..., 2n , dan

SFn  A1  A2  A3  ...  A2 n dimana n  3 , maka graf bunga matahari SFn merupakan 2K 2 - dekomposisi. 2. Misalkan diambil graf bunga matahari SFn dengan n  3 , kemudian graf bunga matahari SFn dipartisi menjadi subgraf Ai berupa 4K2 . Tabel 2. Dekomposisi dari graf bunga matahari Graf Bunga

Dekomposisi

A-dekomposisi

SF3  A1  A2  A3  A4 

Ai  K2

Matahari

SF3

SFn Banyaknya titik dan sisi

| V ( Ai ) | 2 | E ( Ai ) | 1

A5  A6  A7  A8  A9  ...  A12 (12 partisi)

SF4

SF4  A1  A2  A3  A4  A5  A6  A7  A8  A9 

Ai  K2

| V ( Ai ) | 2 | E ( Ai ) | 1

...  H16 (16 partisi)

11

SF5

SF5  A1  A2  A3  A4 

Ai  4 K 2

| V ( Ai ) | 8 | E ( Ai ) | 4

A5 (5 partisi)

SF6

SF6  A1  A2  A3  A4 

Ai  4 K 2

A5  A6

| V ( Ai ) | 8 | E ( Ai ) | 4

(6 partisi)

SF7

SF7  A1  A2  A3  A4 

Ai  4 K 2

A5  A6  A7

| V ( Ai ) | 8 | E ( Ai ) | 4

(7 partisi)

SF8

SF8  A1  A2  A3  A4 

Ai  4 K 2

A5  A6  A7  A8

| V ( Ai ) | 8 | E ( Ai ) | 4

(8 partisi)

SF9

SF9  A1  A2  A3  A4 

Ai  4 K 2

A5  A6  A7  A8  A9

| V ( Ai ) | 8 | E ( Ai ) | 4

(9 partisi) :

:

:

:

:

:

:

:

Ai  4 K 2

| V ( Ai ) | 8

SFn (untuk

n  5)

SFn  A1  A2  A3  A4  A5  A6  A7  A8  A9 

| E ( Ai ) | 4

...  An (n partisi)

Berdasarkan Tabel 2 maka diperoleh teorema sebagai berikut : Teorema: Graf bunga matahari SFn , dengan n  5 dan SFn  A1  A2  A3  ...  An merupakan 4K 2 - dekomposisi. Bukti Ambil sebarang graf bunga matahari SFn Misal V (SFn )  v1 , v2 , v3 ,..., v2n1 , v2n , v2n1 E (SFn )  e1 , e2 , e3 ,..., e3n1 , e4 n 

Partisi graf graf bunga matahari SFn menjadi subgraf Ai  Ei yang berupa 4K2 , dimana i  j maka Ai  Aj   . Misalkan SFn  A1  A2  A3  ...  An . Partisi graf bunga matahari SFn sebagai berikut :

12

Untuk i  1, 2,3,..., n . Subgraf Ai  (vi , vi  n ), (vi 1 , v2 n 1 ), (vi  2 , vi 3 ), (vi  4 , vi 3 n ) ,

dimana

setiap

i  1, i  2, i  3, i  4  n . Jika i  1, i  2, i  3, i  4  n , maka i  1 , i  2 , i  3 , dan i  4 dinyatakan sebagai bilangan bulat 1, 2,3,..., n(mod n) . Akan ditunjukkan bahwa setiap subgraf tersebut saling lepas. Setiap subgraf dikatakan saling lepas jika i  j maka Ai  Aj   , dimana

i  1, 2,3,..., n dan j  1, 2,3,..., n . Akan dibuktikan melalui kontraposisinya. Pernyataan jika i  j maka Ai  Aj   ekuivalen dengan mengatakan jika

Ai  Aj   maka i  j , dimana i  1, 2,3,..., n dan j  1, 2,3,..., n . Diketahui Ai  Aj   , maka ek  Ai  Aj , k  N . Hal ini berarti bahwa ek  Ai dan ek  Aj . Berdasarkan definisi, jika ek  Ai maka ek   vi , vi n  atau

 vi 2 , vi 3 

 vi 1 , v2n1  atau

atau  vi  4 , vi 3 n  .

Begitu pula jika ek  Aj maka ek   v j , v j  n  atau  v j 1 , v2 n 1  atau  v j  2 , v j 3  atau  v j  4 , v j 3 n  . Akibatnya,

v

j2

 vi , vi n  =  v j , v j  n  ,  vi 1 , v2n1  =  v j 1 , v2 n 1  ,  vi 2 , vi 3 

=

, v j  3  , dan  vi  4 , vi 3 n  =  v j  4 , v j 3 n  .

Sehingga diperoleh i  j . Jadi, terbukti bahwa jika Ai  Aj   maka i  j , dimana i  1, 2,3,..., n dan

j  1, 2,3,..., n . Hal ini juga membuktikkan bahwa, pernyataan jika i  j maka Ai  Aj   , dimana i  1, 2,3,..., n dan j  1, 2,3,..., n bernilai benar. Karena dapat dibuktikan jika i  j maka Ai  Aj   , berarti tidak ada sisi yang sama pada setiap subgraf.

13

Dengan

demikian,

terbukti

bahwa

untuk

setiap

i  1, 2,3,..., n ,

dan

SFn  A1  A2  A3  ...  An dimana n  5 , maka graf bunga matahari SFn merupakan 4K 2 - dekomposisi.

3. Misalkan diambil graf bunga matahari SFn dengan n  3 , kemudian graf bunga matahari SFn dipartisi menjadi subgraf Ai berupa P3 . Tabel 3. Dekomposisi dari graf bunga matahari Graf Bunga

Dekomposisi

A-dekomposisi

SF3  A1  A2  A3  A4 

Ai  P3

Matahari

SF3

SFn Banyaknya titik dan sisi

| V ( Ai ) | 3 | E ( Ai ) | 2

A5  A6 (6 partisi)

SF4

SF4  A1  A2  A3  A4 

Ai  P3

| V ( Ai ) | 3 | E ( Ai ) | 2

A5  A6  A7  A8 (8 partisi)

SF5

SF5  A1  A2  A3  A4 

Ai  P3

| V ( Ai ) | 3 | E ( Ai ) | 2

A5  A6  A7  ...  A10 (10 partisi)

SF6

SF6  A1  A2  A3  A4 

Ai  P3

| V ( Ai ) | 3 | E ( Ai ) | 2

A5  A6  A7  ...  A12 (12 partisi)

SF7

SF7  A1  A2  A3  A4 

Ai  P3

| V ( Ai ) | 3 | E ( Ai ) | 2

A5  A6  A7  ...  A14 (14 partisi)

SF8

SF8  A1  A2  A3  A4 

Ai  P3

| V ( Ai ) | 3 | E ( Ai ) | 2

A5  A6  A7  ...  A16 (16 partisi)

SF9

SF9  A1  A2  A3  A4 

Ai  P3

| V ( Ai ) | 3 | E ( Ai ) | 2

A5  A6  A7  ...  A18 (18 partisi) :

:

:

:

:

:

:

:

Ai  P3

| V ( Ai ) | 3

SFn

SFn  A1  A2  A3  A4  A5  A6  A7  ...  A2 n

| E ( Ai ) | 2

(2n partisi)

14

Berdasarkan Tabel 3 maka diperoleh teorema sebagai berikut : Teorema: Graf bunga matahari SFn , dengan n  3 dan SFn  A1  A2  A3  ...  A2 n merupakan P3 - dekomposisi. Bukti Ambil sebarang graf bunga matahari SFn Misal V (SFn )  v1 , v2 , v3 ,..., v2n1 , v2n , v2n1 E (SFn )  e1 , e2 , e3 ,..., e3n1 , e4 n 

Partisi graf bunga matahari SFn menjadi subgraf Ai  Ei

yang berupa P3 ,

dimana i  j maka Ai  Aj   . Misalkan SFn  A1  A2  A3  ...  A2 n . Partisi graf bunga matahari SFn sebagai berikut :  Untuk i  1, 2,3,..., n . Subgraf Ai  (vi , vi  n , vi 1 ) , dimana setiap i  1  n . Jika i  1  n , maka i  1 dinyatakan sebagai bilangan bulat 1, 2,3,..., n(mod n) . Akan ditunjukkan bahwa setiap subgraf tersebut saling lepas. Setiap subgraf dikatakan saling lepas jika i  j maka Ai  Aj   , dimana

i  1, 2,3,..., n dan j  1, 2,3,..., n . Akan dibuktikan melalui kontraposisinya. Pernyataan jika i  j maka Ai  Aj   ekuivalen dengan mengatakan jika

Ai  Aj   maka i  j , dimana i  1, 2,3,..., n dan j  1, 2,3,..., n . Diketahui Ai  Aj   , maka ek  Ai  Aj , k  N . Hal ini berarti bahwa ek  Ai dan ek  Aj . Berdasarkan definisi, jika ek  Ai maka ek  (vi , vi  n , vi 1 ) . Begitu pula jika ek  Aj maka ek  (v j , v j  n , v j 1 ) . Akibatnya, (vi , vi  n , vi 1 ) = (v j , v j  n , v j 1 ) . Sehingga diperoleh i  j .

15

Jadi, terbukti bahwa jika Ai  Aj   maka i  j , dimana i  1, 2,3,..., n dan

j  1, 2,3,..., n . Hal ini juga membuktikkan bahwa, pernyataan jika i  j maka Ai  Aj   , dimana i  1, 2,3,..., n dan j  1, 2,3,..., n bernilai benar. Karena dapat dibuktikan jika i  j maka Ai  Aj   , berarti tidak ada sisi yang sama pada setiap subgraf.  Untuk i  n  1, n  2, n  3,..., 2n . Subgraf Ai  (vi n , vi 1n , v2 n1 ) , dimana setiap i  1  n  n . Jika

i 1 n  n ,

maka

i 1 n

dinyatakan

sebagai

bilangan

bulat

1, 2,3,..., n(mod n) . Akan ditunjukkan bahwa setiap subgraf tersebut saling lepas. Setiap subgraf dikatakan saling lepas jika i  j maka Ai  Aj   , dimana

i  n  1, n  2, n  3,..., 2n dan j  n  1, n  2, n  3,..., 2n . Akan dibuktikan melalui kontraposisinya. Pernyataan jika i  j maka Ai  Aj   ekuivalen dengan mengatakan jika

Ai  Aj  

maka

i  j,

dimana

i  n  1, n  2, n  3,..., 2n

dan

j  n  1, n  2, n  3,..., 2n . Diketahui Ai  Aj   , maka ek  Ai  Aj , k  N . Hal ini berarti bahwa ek  Ai dan ek  Aj . Berdasarkan definisi, jika ek  Ai maka ek  (vi n , vi 1n , v2n 1 ) . Begitu pula jika ek  Aj maka ek  (v j n , v j 1n , v2n1 ) . Akibatnya, (vi n , vi 1n , v2n1 ) = (v j n , v j 1n , v2n 1 ) . Sehingga diperoleh i  j . Jadi,

terbukti

bahwa

jika

Ai  Aj  

maka

i  j,

dimana

i  n  1, n  2, n  3,..., 2n dan j  n  1, n  2, n  3,..., 2n .

16

Hal ini juga membuktikkan bahwa, pernyataan jika i  j maka Ai  Aj   , dimana i  n  1, n  2, n  3,..., 2n dan

j  n  1, n  2, n  3,..., 2n bernilai

benar. Karena dapat dibuktikan jika i  j maka Ai  Aj   , berarti tidak ada sisi yang sama pada setiap subgraf. Dengan

demikian,

terbukti

bahwa

untuk

setiap

i  1, 2,3,..., 2n , dan

SFn  A1  A2  A3  ...  A2 n dimana n  3 , maka graf bunga matahari SFn merupakan P3 - dekomposisi.

4. Misalkan diambil graf bunga matahari SFn dengan n  3 , kemudian graf bunga matahari SFn dipartisi menjadi subgraf Ai berupa 2P3 . Tabel 4. Dekomposisi dari graf bunga matahari Graf Bunga

Dekomposisi

A-dekomposisi

SF3  A1  A2  A3  A4 

Ai  P3

Matahari

SF3

SFn Banyaknya titik dan sisi

| V ( Ai ) | 3 | E ( Ai ) | 2

A5  A6 (6 partisi)

SF4

SF4  A1  A2  A3  A4

Ai  2 P3

| E ( Ai ) | 4

(4 partisi)

SF5

SF5  A1  A2  A3  A4 

| V ( Ai ) | 6

Ai  2 P3

| V ( Ai ) | 6 | E ( Ai ) | 4

A5 (5 partisi)

SF6

SF6  A1  A2  A3  A4 

Ai  2 P3

| V ( Ai ) | 6 | E ( Ai ) | 4

A5  A6 (6 partisi)

SF7

SF7  A1  A2  A3  A4 

Ai  2 P3

| V ( Ai ) | 6 | E ( Ai ) | 4

A5  A6  A7 (7 partisi)

SF8

SF8  A1  A2  A3  A4  A5  A6  A7  A8

Ai  2 P3

| V ( Ai ) | 6 | E ( Ai ) | 4

(8 partisi)

17

SF9

SF9  A1  A2  A3  A4 

Ai  2 P3

| V ( Ai ) | 6 | E ( Ai ) | 4

A5  A6  A7  A8  A9 (9 partisi) :

:

:

:

:

:

:

:

Ai  2 P3

| V ( Ai ) | 6

SFn

SFn  A1  A2  A3  A4  A5  A6  A7  ...  An

| E ( Ai ) | 4

(n partisi)

Berdasarkan Tabel 4 maka diperoleh teorema sebagai berikut : Teorema: Graf bunga matahari SFn , dengan n  3 dan SFn  A1  A2  A3  ...  An merupakan 2P3 - dekomposisi. Bukti Ambil sebarang graf bunga matahari SFn Misal V (SFn )  v1 , v2 , v3 ,..., v2n1 , v2n , v2n1 E (SFn )  e1 , e2 , e3 ,..., e3n1 , e4 n 

Partisi graf bunga matahari SFn menjadi subgraf Ai  Ei

yang berupa 2P3 ,

dimana i  j maka Ai  Aj   . Misalkan SFn  A1  A2  A3  ...  An . Partisi graf bunga matahari SFn sebagai berikut : Untuk i  1, 2,3,..., n . Subgraf Ai  (vi , vi  n , vi 1 ), (vi  2 , vi 3 , v2 n 1 , dimana setiap i  1, i  2, i  3  n . Jika i  1, i  2, i  3  n , maka i  1 , i  2 , dan i  3 dinyatakan sebagai bilangan bulat 1, 2,3,..., n(mod n) . Akan ditunjukkan bahwa setiap subgraf tersebut saling lepas. Setiap subgraf dikatakan saling lepas jika i  j maka Ai  Aj   , dimana

i  1, 2,3,..., n dan j  1, 2,3,..., n . Akan dibuktikan melalui kontraposisinya.

18

Pernyataan jika i  j maka Ai  Aj   ekuivalen dengan mengatakan jika

Ai  Aj   maka i  j , dimana i  1, 2,3,..., n dan j  1, 2,3,..., n . Diketahui Ai  Aj   , maka ek  Ai  Aj , k  N . Hal ini berarti bahwa ek  Ai dan ek  Aj . Berdasarkan definisi, jika ek  Ai maka ek   vi , vi n , vi 1  atau  vi  2 , vi 3 , v2n1  . Begitu pula jika ek  Aj maka ek   v j , v j  n , v j 1  atau  v j  2 , v j 3 , v2 n 1  . Akibatnya,  vi , vi  n , vi 1  =  v j , v j  n , v j 1  dan  vi  2 , vi 3 , v2n1  =  v j  2 , v j 3 , v2 n 1  . Sehingga diperoleh i  j . Jadi, terbukti bahwa jika Ai  Aj   maka i  j , dimana i  1, 2,3,..., n dan

j  1, 2,3,..., n . Hal ini juga membuktikkan bahwa, pernyataan jika i  j maka Ai  Aj   , dimana i  1, 2,3,..., n dan j  1, 2,3,..., n bernilai benar. Karena dapat dibuktikan jika i  j maka Ai  Aj   , berarti tidak ada sisi yang sama pada setiap subgraf. Dengan

demikian,

terbukti

bahwa

untuk

setiap

i  1, 2,3,..., n ,

dan

SFn  A1  A2  A3  ...  An dimana n  3 , maka graf bunga matahari SFn merupakan 2P3 - dekomposisi.

D. Kesimpulan Dari pembahasan diatas, dapat diambil kesimpulan bahwa: 1. Graf bunga matahari SFn , dengan n  3 , dapat di partisi menjadi subgraf

Ai  Ei

yang berupa 2K2 dimana SFn  A1  A2  A3  ...  A2 n . Sehingga

graf bunga matahari SFn dengan n  3 merupakan 2K 2 - dekomposisi. 2. Graf bunga matahari SFn , dengan n  5 dapat di partisi menjadi subgraf

Ai  Ei yang berupa 4K2 dimana SFn  A1  A2  A3  ...  An . Sehingga graf bunga matahari SFn dengan n  5 merupakan 4K 2 - dekomposisi.

19

3. Graf bunga matahari SFn , dengan n  3 dapat di partisi menjadi subgraf

Ai  Ei yang berupa P3 dimana SFn  A1  A2  A3  ...  A2 n . Sehingga graf bunga matahari SFn dengan n  3 merupakan P3 - dekomposisi. 4. Graf bunga matahari SFn , dengan n  3 dapat di partisi menjadi subgraf

Ai  Ei yang berupa 2P3 dimana SFn  A1  A2  A3  ...  An . Sehingga graf bunga matahari SFn dengan n  3 merupakan 2P3 - dekomposisi.

Daftar Pustaka Chartrand, Gery dan Lesniak, Linda. (1986). Graphs and Digraphs Second Edition. California : a Division of Wadsworth, Inc. Munir, Rinaldi. (2012). Matematika Diskrit. Bandung: Informatika Bandung. Rahmawati, Nur dan Rahajeng, Budi. (2014). Dekomposisi Graf Sikel, Graf Roda, Graf Gir, dan Graf Persahabatan. Dalam http://jurnalmahasiswa.unesa.ac. id/index.php/mathunesa/article/view/9365/12427. Diunduh pada tanggal 25 Februari 2018. Munawaroh, Rina. (2009). Dekomposisi Graf Komplit. Dalam http://etheses.uinmalang.ac.id/6393/1/04510046.pdf. Diunduh pada tanggal 25 Februari 2018. Sidiq, Muhamad. (2014). Pemberian Nomor Vertex Pada Topologi Jaringan Graf Wheel, Graf Helm Dan Graf Lollipop. UNS Surakarta : Skripsi, tidak diterbitkan. Qonaah, Khunti, dkk. (2016). Pelabelan Selimut Total Anti Ajaib Super pada Graf Bunga Matahari, Graf Broken Fan, dan Graf Generalized Fan. Dalam https://digilib.uns.ac.id/dokumen/detail/48521/Pelabelan-Selimut-CycleAjaib-Super-Pada-Graf-Bunga-Matahari-Graf-Grid-Dan-Graf-K1n-_-K2. Diunduh pada 16 Juli 2018. Addinnitya, Arief. (2012). Pelabelan Jumlah Eksklusif pada Graf Matahari, Graf Korona, dan Graf Hairycycle dengan Banyak Simpul Lingkaran Genap. Hlm. 8-10. LIB UI. Fatkhiyah, Lutfiana. (2010). Bilangan Clique dan Faktorisasi pada Perkalian Graf Komplit. Hlm. 10. ETHESES UIN Malang.

20

Mandailina, Vera. (2009). Faktorisasi pada Graf Komplit. Hlm. 18. ETHESES UIN Malang.

21